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 proceedingConference contributionAcademicpeer-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 languageEnglish
Title of host publicationGraph Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010 Revised Papers
EditorsDimitrios M. Thilikos
Pages75-87
Number of pages13
ISBN (Electronic)978-3-642-16926-7
DOIs
Publication statusPublished - 2010
Externally publishedYes
Event36th International Workshop on Graph Theoretic Concepts in Computer Science, WG 2010 - Zaros, Greece
Duration: 28 Jun 201030 Jun 2010
Conference number: 36

Publication series

NameLecture Notes in Computer Science
Volume6410

Conference

Conference36th International Workshop on Graph Theoretic Concepts in Computer Science, WG 2010
Abbreviated titleWG 2010
CountryGreece
CityZaros
Period28/06/1030/06/10

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