Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time

DOI10.1137/110830514zbMath1256.05213OpenAlexW1973196832MaRDI QIDQ4899040

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

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 theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Vertex deletion into bipartite permutation graphs ⋮ Strong SDP based bounds on the cutwidth of a graph ⋮ Cutwidth: obstructions and algorithmic aspects ⋮ Vertex deletion into bipartite 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