Diameter and treewidth in minor-closed graph families, revisited

DOI10.1007/s00453-004-1106-1zbMath1082.05086WikidataQ29031208 ScholiaQ29031208MaRDI QIDQ1762990

Mohammad Taghi Hajiaghayi, Erik D. Demaine

Publication date: 11 February 2005

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-004-1106-1

zbMATH Keywords

Approximation algorithms; Graph algorithms; Apex graphs; Bounded local treewidth; Graph minors

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C12: Distance in graphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Vertex-Bipartition Method for Colouring Minor-Closed Classes of Graphs, Unnamed Item, The complexity of two graph orientation problems, The degree-diameter problem for sparse graph classes, Implicit branching and parameterized partial cover problems, Minimal classes of graphs of unbounded clique-width, Graphs without large apples and the maximum weight independent set problem, Linearity of grid minors in treewidth with applications through bidimensionality, Recent developments on graphs of bounded clique-width, Approximation algorithms via contraction decomposition, A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families, Succinct certification of monotone circuits, Layered separators in minor-closed graph classes with applications, Boundary Classes of Planar Graphs, The Maximum Independent Set Problem in Planar Graphs