Computing the cutwidth of bipartite permutation graphs in linear time

P. Heggernes, P. Hof, van 't, D. Lokshtanov, J. Nederlof

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
37 Downloads (Pure)

Abstract

The problem of determining the cutwidth of a graph is a notoriously hard problem which remains NP-complete under severe restrictions on input graphs. Until recently, nontrivial polynomial-time cutwidth algorithms were known only for subclasses of graphs of bounded treewidth. Very recently, Heggernes et al. (SIAM J. Discrete Math., 25 (2011), pp. 1418--1437) initiated the study of cutwidth on graph classes containing graphs of unbounded treewidth and showed that a greedy algorithm computes the cutwidth of threshold graphs. We continue this line of research and present the first polynomial-time algorithm for computing the cutwidth of bipartite permutation graphs. Our algorithm runs in linear time. We stress that the cutwidth problem is NP-complete on bipartite graphs and its computational complexity is open even on small subclasses of permutation graphs, such as trivially perfect graphs. Keywords: graph algorithms, graph layout problems, cutwidth, bipartite permutation graphs
Original languageEnglish
Pages (from-to)1008-1021
JournalSIAM Journal on Discrete Mathematics
Volume26
Issue number3
DOIs
Publication statusPublished - 2012
Externally publishedYes

Fingerprint Dive into the research topics of 'Computing the cutwidth of bipartite permutation graphs in linear time'. Together they form a unique fingerprint.

  • Cite this