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

Dimitrios M. Thilikos; Maria J. Serna; Hans L. Bodlaender

doi:10.1007/3-540-44676-1_32

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

Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 [υ₁,. .., υ_n] in a way that, for every i = 1,. .., n − 1, there are at most k edges with the one endpoint in {υ₁,. .., υ_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.

Original language	English (US)
Title of host publication	Algorithms - ESA 2001 - 9th Annual European Symposium, Proceedings
Editors	Friedhelm Meyer auf der Heide
Publisher	Springer Verlag
Pages	380-390
Number of pages	11
ISBN (Print)	9783540424932
DOIs	https://doi.org/10.1007/3-540-44676-1_32
State	Published - 2001
Event	9th Annual European Symposium on Algorithms, ESA 2001 - Arhus, Denmark Duration: Aug 28 2001 → Aug 31 2001

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2161
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th Annual European Symposium on Algorithms, ESA 2001
Country/Territory	Denmark
City	Arhus
Period	8/28/01 → 8/31/01

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-44676-1_32

Cite this

Thilikos, D. M., Serna, M. J., & Bodlaender, H. L. (2001). A polynomial time algorithm for the cutwidth of bounded degree graphs with small treewidth. In F. M. auf der Heide (Ed.), Algorithms - ESA 2001 - 9th Annual European Symposium, Proceedings (pp. 380-390). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2161). Springer Verlag. https://doi.org/10.1007/3-540-44676-1_32

A polynomial time algorithm for the cutwidth of bounded degree graphs with small treewidth. / Thilikos, Dimitrios M.; Serna, Maria J.; Bodlaender, Hans L.
Algorithms - ESA 2001 - 9th Annual European Symposium, Proceedings. ed. / Friedhelm Meyer auf der Heide. Springer Verlag, 2001. p. 380-390 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2161).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Thilikos, DM, Serna, MJ & Bodlaender, HL 2001, A polynomial time algorithm for the cutwidth of bounded degree graphs with small treewidth. in FM auf der Heide (ed.), Algorithms - ESA 2001 - 9th Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2161, Springer Verlag, pp. 380-390, 9th Annual European Symposium on Algorithms, ESA 2001, Arhus, Denmark, 8/28/01. https://doi.org/10.1007/3-540-44676-1_32

Thilikos DM, Serna MJ, Bodlaender HL. A polynomial time algorithm for the cutwidth of bounded degree graphs with small treewidth. In auf der Heide FM, editor, Algorithms - ESA 2001 - 9th Annual European Symposium, Proceedings. Springer Verlag. 2001. p. 380-390. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-44676-1_32

Thilikos, Dimitrios M. ; Serna, Maria J. ; Bodlaender, Hans L. / A polynomial time algorithm for the cutwidth of bounded degree graphs with small treewidth. Algorithms - ESA 2001 - 9th Annual European Symposium, Proceedings. editor / Friedhelm Meyer auf der Heide. Springer Verlag, 2001. pp. 380-390 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e3a100f77aab4bd29d6d8b3825d2e9f7,

title = "A polynomial time algorithm for the cutwidth of bounded degree graphs with small treewidth",

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

author = "Thilikos, {Dimitrios M.} and Serna, {Maria J.} and Bodlaender, {Hans L.}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 9th Annual European Symposium on Algorithms, ESA 2001 ; Conference date: 28-08-2001 Through 31-08-2001",

year = "2001",

doi = "10.1007/3-540-44676-1_32",

language = "English (US)",

isbn = "9783540424932",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "380--390",

editor = "{auf der Heide}, {Friedhelm Meyer}",

booktitle = "Algorithms - ESA 2001 - 9th Annual European Symposium, Proceedings",

}

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.

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 -

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

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this