Graph separators: A parameterized view

DOI10.1016/S0022-0000(03)00072-2zbMath1091.68075OpenAlexW2077357506MaRDI QIDQ1877710

Henning Fernau, Jochen Alber, Rolf Niedermeier

Publication date: 19 August 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(03)00072-2

zbMATH Keywords

Parameterized complexityDivide-and-conquer algorithmsFixed parameter tractabilityGraph separator theoremsPlanar graph problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (4)

Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions ⋮ Linearity of grid minors in treewidth with applications through bidimensionality ⋮ Planar k-Path in Subexponential Time and Polynomial Space ⋮ A refined search tree technique for dominating set on planar graphs

Cites Work

• An application of the planar separator theorem to counting problems
• A partial k-arboretum of graphs with bounded treewidth
• Diameter and treewidth in minor-closed graph families
• Reduced constants for simple cycle graph separation
• Approximation Algorithms for Independent Sets in Map Graphs
• Vertex Cover: Further Observations and Further Improvements
• Map graphs
• Algorithms for maximum independent sets
• A Separator Theorem for Planar Graphs
• Edge Dominating Sets in Graphs
• Applications of a Planar Separator Theorem
• On the Problem of Partitioning Planar Graphs
• A Separator Theorem for Nonplanar Graphs
• Vertex packings: Structural properties and algorithms
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus
• Faster exact algorithms for hard problems: A parameterized point of view
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Graph separators: A parameterized view