TY - GEN

T1 - A polynomial time algorithm for the cutwidth of bounded degree graphs with small treewidth

AU - Thilikos, Dimitrios M.

AU - Serna, Maria J.

AU - Bodlaender, Hans L.

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2001.

PY - 2001

Y1 - 2001

N2 - The cutwidth of a graph G is defined as the smallest integer k such that the vertices of G can be arranged in a vertex ordering [υ1,. .., υn] in a way that, for every i = 1,. .., n − 1, there are at most k edges with the one endpoint in {υ1,. .., υi} and the other in {υi+1,. .., υn}. We examine the problem of computing in polynomial time the cutwidth of a partial w-tree with bounded degree. In particular, we show how to construct an algorithm that, in (formula presented) steps, computes the cutwidth of any partial w-tree with vertices of degree bounded by a fixed constant d. Our algorithm is constructive in the sense that it can be adapted to output the corresponding optimal vertex ordering. Also, it is the main subroutine of an algorithm computing the pathwidth of a bounded degree partial w-tree in (formula presented) steps.

AB - The cutwidth of a graph G is defined as the smallest integer k such that the vertices of G can be arranged in a vertex ordering [υ1,. .., υn] in a way that, for every i = 1,. .., n − 1, there are at most k edges with the one endpoint in {υ1,. .., υi} and the other in {υi+1,. .., υn}. We examine the problem of computing in polynomial time the cutwidth of a partial w-tree with bounded degree. In particular, we show how to construct an algorithm that, in (formula presented) steps, computes the cutwidth of any partial w-tree with vertices of degree bounded by a fixed constant d. Our algorithm is constructive in the sense that it can be adapted to output the corresponding optimal vertex ordering. Also, it is the main subroutine of an algorithm computing the pathwidth of a bounded degree partial w-tree in (formula presented) steps.

UR - http://www.scopus.com/inward/record.url?scp=84943243932&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84943243932&partnerID=8YFLogxK

U2 - 10.1007/3-540-44676-1_32

DO - 10.1007/3-540-44676-1_32

M3 - Conference contribution

AN - SCOPUS:84943243932

SN - 9783540424932

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 380

EP - 390

BT - Algorithms - ESA 2001 - 9th Annual European Symposium, Proceedings

A2 - auf der Heide, Friedhelm Meyer

PB - Springer Verlag

T2 - 9th Annual European Symposium on Algorithms, ESA 2001

Y2 - 28 August 2001 through 31 August 2001

ER -