Computing the cutwidth of bipartite permutation graphs in linear time

DOI10.1137/110830514MaRDI QIDQ4899040zbMATH OpenOpenAlexFDO

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

Publication date 4 January 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/110830514

zbMATH Keywords

graph algorithmscutwidthgraph layout problemsbipartite permutation graphs

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

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

Cited in

(15)

• Vertex deletion into bipartite permutation graphs
• A polynomial algorithm for recognizing bounded cutwidth in hypergraphs
• Strong SDP based bounds on the cutwidth of a graph
• scientific article; zbMATH DE number 3958752 (Why is no real title available?)
• Cutwidth: obstructions and algorithmic aspects
• 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
• Vertex deletion into bipartite permutation graphs
• scientific article; zbMATH DE number 1875430 (Why is no real title available?)
• The cutwidth of trees with diameters at most 4
• Bandwidth of Bipartite Permutation Graphs in Polynomial Time
• Treewidth and pathwidth of permutation graphs
• Algorithms for maximum internal spanning tree problem for some graph classes

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 Q4899040)