Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs

DOI10.1007/978-3-540-92248-3_20zbMath1202.68283OpenAlexW1516681952MaRDI QIDQ5302057

Pinar Heggernes, Daniel Lokshtanov, Rodica Mihai, Charis Papadopoulos

Publication date: 20 January 2009

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-92248-3_20

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

On Cutwidth Parameterized by Vertex Cover ⋮ Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithmic graph theory and perfect graphs
• Threshold graphs and related topics
• Approximating Layout Problems on Random Geometric Graphs
• Computing the Bandwidth of Interval Graphs
• Single-Edge Monotonic Sequences of Graphs and Linear-Time Algorithms for Minimal Completions and Deletions
• Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
• A polynomial algorithm for the min-cut linear arrangement of trees
• Graph Classes: A Survey
• Optimal Linear Ordering
• Cutwidth I: A linear time fixed parameter algorithm
• Cutwidth II: Algorithms for partial w-trees of bounded degree
• Optimal Linear Arrangement of Interval Graphs
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs