Computing the cutwidth of bipartite permutation graphs in linear time

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

doi:10.1007/978-3-642-16926-7_9

Computing the cutwidth of bipartite permutation graphs in linear time

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

5 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, non-trivial polynomial-time cutwidth algorithms were known only for subclasses of graphs of bounded treewidth. In WG 2008, Heggernes et al. 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
Title of host publication	Graph Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010 Revised Papers
Editors	Dimitrios M. Thilikos
Pages	75-87
Number of pages	13
ISBN (Electronic)	978-3-642-16926-7
DOIs	https://doi.org/10.1007/978-3-642-16926-7_9
Publication status	Published - 2010
Externally published	Yes
Event	36th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2010 - Zaros, Crete, Greece Duration: 28 Jun 2010 → 30 Jun 2010 Conference number: 36

Publication series

Name	Lecture Notes in Computer Science
Volume	6410

Conference

Conference	36th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2010
Abbreviated title	WG 2010
Country/Territory	Greece
City	Zaros, Crete
Period	28/06/10 → 30/06/10

Access to Document

10.1007/978-3-642-16926-7_9

Cite this

Heggernes, P., van 't Hof, P., Lokshtanov, D., & Nederlof, J. (2010). Computing the cutwidth of bipartite permutation graphs in linear time. In D. M. Thilikos (Ed.), Graph Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010 Revised Papers (pp. 75-87). (Lecture Notes in Computer Science; Vol. 6410). https://doi.org/10.1007/978-3-642-16926-7_9

@inproceedings{1e652a349ca34719a7c4d1ef613b5d97,

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, non-trivial polynomial-time cutwidth algorithms were known only for subclasses of graphs of bounded treewidth. In WG 2008, Heggernes et al. 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 = "2010",

doi = "10.1007/978-3-642-16926-7_9",

language = "English",

isbn = "978-3-642-16925-0",

series = "Lecture Notes in Computer Science",

pages = "75--87",

editor = "Thilikos, {Dimitrios M.}",

booktitle = "Graph Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Zar{\'o}s, Crete, Greece, June 28-30, 2010 Revised Papers",

note = "36th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2010, WG 2010 ; Conference date: 28-06-2010 Through 30-06-2010",

}

Heggernes, P, van 't Hof, P, Lokshtanov, D & Nederlof, J 2010, Computing the cutwidth of bipartite permutation graphs in linear time. in DM Thilikos (ed.), Graph Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010 Revised Papers. Lecture Notes in Computer Science, vol. 6410, pp. 75-87, 36th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2010, Zaros, Crete, Greece, 28/06/10. https://doi.org/10.1007/978-3-642-16926-7_9

Computing the cutwidth of bipartite permutation graphs in linear time. / Heggernes, Pinar; van 't Hof, Pim; Lokshtanov, Daniel et al.
Graph Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010 Revised Papers. ed. / Dimitrios M. Thilikos. 2010. p. 75-87 (Lecture Notes in Computer Science; Vol. 6410).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

N1 - Conference code: 36

PY - 2010

Y1 - 2010

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, non-trivial polynomial-time cutwidth algorithms were known only for subclasses of graphs of bounded treewidth. In WG 2008, Heggernes et al. 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, non-trivial polynomial-time cutwidth algorithms were known only for subclasses of graphs of bounded treewidth. In WG 2008, Heggernes et al. 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.1007/978-3-642-16926-7_9

DO - 10.1007/978-3-642-16926-7_9

M3 - Conference contribution

SN - 978-3-642-16925-0

T3 - Lecture Notes in Computer Science

SP - 75

EP - 87

BT - Graph Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010 Revised Papers

A2 - Thilikos, Dimitrios M.

T2 - 36th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2010

Y2 - 28 June 2010 through 30 June 2010

ER -

Heggernes P, van 't Hof P, Lokshtanov D, Nederlof J. Computing the cutwidth of bipartite permutation graphs in linear time. In Thilikos DM, editor, Graph Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010 Revised Papers. 2010. p. 75-87. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-16926-7_9

Computing the cutwidth of bipartite permutation graphs in linear time

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this