Computing the cutwidth of bipartite permutation graphs in linear time

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

doi:10.1137/110830514

Computing the cutwidth of bipartite permutation graphs in linear time

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

Research output: Contribution to journal › Article › Academic › peer-review

7 Citations (Scopus)

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.

Original language	English
Pages (from-to)	1008-1021
Number of pages	14
Journal	SIAM journal on discrete mathematics
Volume	26
Issue number	3
Early online date	19 Jul 2012
DOIs	https://doi.org/10.1137/110830514
Publication status	Published - 2012
Externally published	Yes

Access to Document

10.1137/110830514

Computing the cutwidth of bipartite permutation graphs in linear time
Heggernes, P., van 't Hof, P., Lokshtanov, D. & Nederlof, J., 2010, Graph Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010 Revised Papers. Thilikos, D. M. (ed.). p. 75-87 13 p. (Lecture Notes in Computer Science; vol. 6410).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
5 Link opens in a new tab Citations (Scopus)

Cite this

@article{ee5946f6af6c4f5480ce6b6c274e56a6,

title = "Computing the cutwidth of bipartite permutation graphs in linear time",

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.",

author = "Pinar Heggernes and \{van 't Hof\}, Pim and Daniel Lokshtanov and Jesper Nederlof",

year = "2012",

doi = "10.1137/110830514",

language = "English",

volume = "26",

pages = "1008--1021",

journal = "SIAM journal on discrete mathematics",

issn = "0895-4801",

publisher = "SIAM",

number = "3",

}

TY - JOUR

T1 - Computing the cutwidth of bipartite permutation graphs in linear time

AU - Heggernes, Pinar

AU - van 't Hof, Pim

AU - Lokshtanov, Daniel

AU - Nederlof, Jesper

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

U2 - 10.1137/110830514

DO - 10.1137/110830514

M3 - Article

SN - 0895-4801

VL - 26

SP - 1008

EP - 1021

JO - SIAM journal on discrete mathematics

JF - SIAM journal on discrete mathematics

IS - 3

ER -

Computing the cutwidth of bipartite permutation graphs in linear time

Abstract

Access to Document

Fingerprint

Research output

Computing the cutwidth of bipartite permutation graphs in linear time

Cite this