Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time

DOI10.1137/110830514zbMath1256.05213MaRDI QIDQ4899040

Pinar Heggernes, Daniel Lokshtanov, Jesper Nederlof, 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 algorithms; cutwidth; graph layout problems; bipartite permutation graphs

Mathematics Subject Classification ID

05A05: Permutations, words, matrices

68R10: Graph theory (including graph drawing) in computer science

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

05C85: Graph algorithms (graph-theoretic aspects)