Name
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.
|
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-16926-7_9 | SIAM Journal on Discrete Mathematics |
Keywords | Field | DocType |
bounded treewidth,hard problem,cutwidth problem,bipartite graph,bipartite permutation graph,graph class,greedy algorithm,linear time,polynomial-time algorithm,non-trivial polynomial-time cutwidth algorithm,input graph,perfect graph,computational complexity,polynomial time,permutation graph | Permutation graph,Discrete mathematics,Combinatorics,Indifference graph,Tree-depth,Partial k-tree,Computer science,Chordal graph,Cograph,Treewidth,Pathwidth | Journal |
Volume | Issue | ISBN |
26 | 3 | 3-642-16925-2 |
Citations | PageRank | References |
2 | 0.37 | 17 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pinar Heggernes | 1 | 845 | 72.39 |
| Pim van 't Hof | 2 | 209 | 20.75 |
| Daniel Lokshtanov | 3 | 1438 | 110.05 |
| Jesper Nederlof | 4 | 294 | 24.22 |