Bidimensional Parameters and Local Treewidth

DOI10.1137/S0895480103433410MaRDI QIDQ5317565zbMATH OpenDBLPWikidataFDO

Authors Erik D. Demaine, Fedor V. Fomin, Dimitrios M. Thilikos, Mohammad T. Hajiaghayi

Publication date 16 September 2005

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480103433410

zbMATH Keywords

dominating setgraph minors

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• LATIN 2004: Theoretical Informatics
• Dominating sets and local treewidth
• The Bidimensional Theory of Bounded-Genus Graphs
• Mathematical Foundations of Computer Science 2004
• Bidimensionality and parameterized algorithms (invited talk)

Cited in

(35)

• Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
• Parameterized complexity of the spanning tree congestion problem
• Approximation algorithms via contraction decomposition
• Contraction obstructions for treewidth
• Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
• Layered separators in minor-closed graph classes with applications
• Minimizing the oriented diameter of a planar graph
• Graph minors and parameterized algorithm design
• Chasing a fast robber on planar graphs and random graphs
• Bidimensionality and kernels
• Towards the graph minor theorems for directed graphs
• Contraction Bidimensionality: The Accurate Picture
• The complexity of two graph orientation problems
• Catalan structures and dynamic programming in \(H\)-minor-free graphs
• Subexponential parameterized algorithms
• Orthogonal tree decompositions of graphs
• Confronting intractability via parameters
• Coverability and sub-exponential parameterized algorithms in planar graphs
• Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
• A Retrospective on (Meta) Kernelization
• Hitting weighted even cycles in planar graphs
• Minor-Closed Graph Classes with Bounded Layered Pathwidth
• Structure of graphs with locally restricted crossings
• An algorithmic meta-theorem for graph modification to planarity and FOL
• Dominating sets and local treewidth
• LATIN 2004: Theoretical Informatics
• Optimality program in segment and string graphs
• On \(H\)-topological intersection graphs
• FPT approximation and subexponential algorithms for covering few or many edges
• Spanners in sparse graphs
• An FPT-algorithm for recognizing k-apices of minor-closed graph classes
• An algorithmic meta-theorem for graph modification to planarity and FOL
• Contraction bidimensionality of geometric intersection graphs
• Quickly deciding minor-closed parameters in general graphs
• Linearity of grid minors in treewidth with applications through bidimensionality

This page was built for publication: Bidimensional Parameters and Local Treewidth

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