Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time
DOI10.1007/978-3-642-16926-7_9zbMATH Open1310.05199OpenAlexW1863509856MaRDI QIDQ3057614FDOQ3057614
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
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph Classes: A Survey
- Bipartite permutation graphs
- Optimal labelling of unit interval graphs
- A polynomial algorithm for the min-cut linear arrangement of trees
- Optimal Linear Ordering
- Cutwidth I: A linear time fixed parameter algorithm
- Approximating layout problems on random geometric graphs
- Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
- Cutwidth II: Algorithms for partial w-trees of bounded degree
- Graph-Theoretic Concepts in Computer Science
- Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs
Cited In (3)
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)
