Tree decompositions of small diameter

DOI10.1007/BFB0055821MaRDI QIDQ4218147zbMATH OpenFDO

Authors Torben Hagerup, Hans L. Bodlaender

Publication date 11 November 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0055821

zbMATH Keywords

diametertree decompositionwidth

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

Let \(G\) be an undirected graph. The paper investigates the interrelations between the width and the diameter of tree decompositions of \(G\). For all integers \(n,k\) and \(K\) with \(1\leq k\leq K\leq n-1\), \(D(n,k,K)\) denote the maximum, over all graphs \(G\) with \(n\) vertices and of treewidth \(k\), of the smallest diameter of a tree decomposition of \(G\) with width \(K\). The paper determines the quantity \(D(n,k,K)\) up to a constant factor. For the entire collection see [Zbl 0895.00049].

Recommendations

• Some results on tree decomposition of graphs
• Diameter and treewidth in minor-closed graph families
• Diameter and treewidth in minor-closed graph families, revisited
• On the tree-width of planar graphs

Cited in

(10)

• On tradeoffs between width- and fill-like graph parameters
• Tree-decompositions with bags of small diameter
• scientific article; zbMATH DE number 4087704 (Why is no real title available?)
• Some results on tree decomposition of graphs
• The complexity of minimum-length path decompositions
• scientific article; zbMATH DE number 1420905 (Why is no real title available?)
• Tree-decompositions of small pathwidth
• Bounded-diameter tree-decompositions
• Monotone bounded-depth complexity of homomorphism polynomials
• Faithful universal graphs for minor-closed classes

This page was built for publication: Tree decompositions of small diameter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4218147)