Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time

DOI10.1007/978-3-642-16926-7_9zbMath1310.05199OpenAlexW1863509856MaRDI QIDQ3057614

Jesper Nederlof, Daniel Lokshtanov, Pim van 't Hof, Pinar Heggernes

Publication date: 16 November 2010

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-642-16926-7_9

Mathematics Subject Classification ID

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

Related Items

On Cutwidth Parameterized by Vertex Cover ⋮ On cutwidth parameterized by vertex cover

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bipartite permutation graphs
• Optimal labelling of unit interval graphs
• Approximating Layout Problems on Random Geometric Graphs
• 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 of Split Graphs, Threshold Graphs, and Proper Interval Graphs
• Cutwidth I: A linear time fixed parameter algorithm
• Cutwidth II: Algorithms for partial w-trees of bounded degree
• Graph-Theoretic Concepts in Computer Science