Diameter and treewidth in minor-closed graph families, revisited

DOI10.1007/S00453-004-1106-1MaRDI QIDQ1762990zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Erik D. Demaine, Mohammad T. Hajiaghayi

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

Apex graphsApproximation algorithmsBounded local treewidthGraph algorithmsGraph minors

Mathematics Subject Classification ID

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

Recommendations

• Diameter and treewidth in minor-closed graph families
• To approximate treewidth, use treelength!
• Equivalence of local treewidth and linear local treewidth and its algorithmic applications
• Dominating sets and local treewidth
• Graph minors. II. Algorithmic aspects of tree-width

Cited in

(20)

• Diameter and treewidth in minor-closed graph families
• 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
• The complexity of two graph orientation problems
• scientific article; zbMATH DE number 1222605 (Why is no real title available?)
• The degree-diameter problem for sparse graph classes
• Vertex-bipartition method for colouring minor-closed classes of graphs
• Equivalence of local treewidth and linear local treewidth and its algorithmic applications
• To approximate treewidth, use treelength!
• Exact distance oracles for planar graphs
• Implicit branching and parameterized partial cover problems
• Minimal classes of graphs of unbounded clique-width
• Grid minors and products
• 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

This page was built for publication: Diameter and treewidth in minor-closed graph families, revisited

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