Diameter and treewidth in minor-closed graph families, revisited

DOI10.1007/s00453-004-1106-1zbMath1082.05086OpenAlexW2015974056WikidataQ29031208 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 algorithmsGraph algorithmsApex graphsBounded local treewidthGraph minors

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

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