Computing the cutwidth of bipartite permutation graphs in linear time

DOI10.1007/978-3-642-16926-7_9MaRDI QIDQ3057614zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Pim Van 't Hof, Daniel Lokshtanov, Jesper Nederlof

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

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

Recommendations

• Computing the cutwidth of bipartite permutation graphs in linear time
• Cutwidth of split graphs and threshold graphs
• Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs
• Bandwidth of bipartite permutation graphs in polynomial time
• Bandwidth of Bipartite Permutation Graphs in Polynomial Time

Cites work

• scientific article; zbMATH DE number 3813518 (Why is no real title available?)
• scientific article; zbMATH DE number 3956440 (Why is no real title available?)
• scientific article; zbMATH DE number 1263176 (Why is no real title available?)
• scientific article; zbMATH DE number 795217 (Why is no real title available?)
• scientific article; zbMATH DE number 2191997 (Why is no real title available?)
• A polynomial algorithm for the min-cut linear arrangement of trees
• Approximating layout problems on random geometric graphs
• Bipartite permutation graphs
• Cutwidth I: A linear time fixed parameter algorithm
• Cutwidth II: Algorithms for partial w-trees of bounded degree
• Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs
• Graph Classes: A Survey
• Graph-Theoretic Concepts in Computer Science
• Optimal Linear Ordering
• Optimal labelling of unit interval graphs
• Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees

Cited in

(8)

• scientific article; zbMATH DE number 1875430 (Why is no real title available?)
• Bandwidth of bipartite permutation graphs in polynomial time
• Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs
• Bandwidth of Bipartite Permutation Graphs in Polynomial Time
• On cutwidth parameterized by vertex cover
• On cutwidth parameterized by vertex cover
• Computing the cutwidth of bipartite permutation graphs in linear time
• Cutwidth of split graphs and threshold graphs

This page was built for publication: Computing the cutwidth of bipartite permutation graphs in linear time

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