Many instances of NP-hard problems can be solved efficiently if the treewidth of their corresponding graph is small. Finding the optimal tree decompositions is an NP-hard problem and different algorithms have been proposed in the literature for generation of tree decompositions of small width. In this chapter we present a new iterated local search algorithm to find good upper bounds for treewidth of an undirected graph. The iterated local search algorithm consists from the construction phase, and includes the mechanism for perturbation of solutions, and the mechanism for accepting of solutions for the next iteration. In the construction phase the solutions are generated by the heuristics which search for good elimination ordering of nodes of graph based on moving of only vertices that produce the largest clique in the elimination process. We proposed and evaluated different perturbation mechanisms and acceptance criteria. The proposed algorithm is tested on DIMACS instances for vertex colouring, and is compared with the existing approaches in the literature. The described algorithm has a good time performance and for several instances improves the best existing upper bounds for the treewidth.
Weitere Kapitel dieses Buchs durch Wischen aufrufen
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
- An Iterative Heuristic Algorithm for Tree Decomposition
- Springer Berlin Heidelberg
in-adhesives, MKVS, Zühlke/© Zühlke