Graph separators: a parameterized view

2003/11/20 by Jochen Alber, Henning Fernau, Rolf Niedermeier · 18 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Graph #Graph Theory and Algorithms #Graph property #Line graph #Mathematics #Null graph #Parameterized complexity #Planar graph #Theoretical computer science #Voltage graph

paper · pdf · doi:10.1016/s0022-0000(03)00072-2

published in Journal of Computer and System Sciences 67(4), 808-832 (Elsevier BV)

openalex publication_date 2003/11/20 · crossref created 2003/11/20 · crossref issued 2003/12/01 · crossref published 2003/12/01 · crossref published-print 2003/12/01 · crossref deposited 2020/03/27 · crossref indexed 2024/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Citations

• Applications of a Planar Separator Theorem
• Efficiently four-coloring planar graphs
• Reduced constants for simple cycle graph separation
• Local Tree-Width, Excluded Minors, and Approximation Algorithms
• Vertex Cover: Further Observations and Further Improvements
• A Separator Theorem for Planar Graphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Diameter and Treewidth in Minor-Closed Graph Families
• Algorithms for maximum independent sets
• A separator theorem for graphs with an excluded minor and its applications
• A partial k-arboretum of graphs with bounded treewidth
• A separator theorem for nonplanar graphs
• Parameterized Complexity

Cited by

• A Fixed-Parameter Algorithm for the Minimum Weight Triangulation Problem Based on Small Graph Separators
• Engineering planar separator algorithms
• Planar separator theorem [wikipedia]