×

zbMATH — the first resource for mathematics

Finding good tree decompositions by local search. (English) Zbl 1267.05273
Koster, Arie (ed.) et al., DIMAP workshop on algorithmic graph theory. Extended abstracts from the workshop held at the University of Warwick, Coventry, UK, March 23–25, 2009. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 32, 43-50 (2009).
Summary: We present a local search algorithm, for upper bounding the tree-width of graphs. The algorithm exploits a new neighborhood structure that operates directly on a tree decomposition of the input graph, contrary to earlier work that generally used derived notions such as elimination orderings of the vertices. As a side result, we obtain an \(O(f(e+f))\)-algorithm for making tree decompositions (or triangulations) minimal in terms of fill-in.
For the entire collection see [Zbl 1239.05006].

MSC:
05C85 Graph algorithms (graph-theoretic aspects)
05C12 Distance in graphs
PDF BibTeX Cite
Full Text: DOI
References:
[1] Amir, E., Efficient approximation for triangulation of minimum treewidth, (), 7-15
[2] ArnBorg, S.; Corneil, D.G.; Proskurowski, A., Complexity of finding embeddings in a k-tree, SIAM journal on algebraic discrete methods, 8, 277-284, (1987), Society for Industrial and Applied Mathematics · Zbl 0611.05022
[3] Becker, A.; Geiger, D., A sufficiently fast algorithm for finding close to optimal junction trees, (), 81-89
[4] Courcelle, B., The monadic second-order logic of graphs. I. recognizable sets of finite graphs, Information and computation, 85, 12-75, (1990), Academic Press, Inc · Zbl 0722.03008
[5] Koster, A.M.C.A.; Bodlaender, H.L.; van Hoesel, C.P.M., Treewidth: computational experiments, Electronic notes in discrete mathematics, 54-57, (2001), Elsevier Science Publishers · Zbl 1409.05176
[6] Robertson, N.; Seymour, P.D., Graph minors. XIII: the disjoint paths problem, Journal of combinatorial theory series B, 63, 65-110, (1995), Academic Press, Inc · Zbl 0823.05038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.