A Linear Time Algorithm for Finding Tree-decompositions of Small Treewidth

Hans L. Bodlaender

doi:10.1145/167088.167161

A Linear Time Algorithm for Finding Tree-decompositions of Small Treewidth

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

Abstract

In this paper, we give, for constant k, a linear time algorithm, that given a graph G = (V, E), determines whether the treewidth of G is at most k, and if so, finds a treedecomposition of G with treewidth at most k. A consequence is that every minor-closed class of graphs that does not contain all planar graphs has a linear time recognition algorithm.

Original language	English
Title of host publication	Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing
Subtitle of host publication	STOC'93
Place of Publication	New York, NY, USA
Publisher	Association for Computing Machinery
Pages	226-234
Number of pages	9
DOIs	https://doi.org/10.1145/167088.167161
Publication status	Published - 1993

Publication series

Name	STOC '93
Publisher	ACM

Keywords

graph algorithms, graph minors, partial k-trees, pathwidth, treewidth

Access to Document

10.1145/167088.167161

http://doi.acm.org/10.1145/167088.167161

Cite this

@inproceedings{b588170f4b8b4a0c8fee5c49a6eaa621,

title = "A Linear Time Algorithm for Finding Tree-decompositions of Small Treewidth",

abstract = "In this paper, we give, for constant k, a linear time algorithm, that given a graph G = (V, E), determines whether the treewidth of G is at most k, and if so, finds a treedecomposition of G with treewidth at most k. A consequence is that every minor-closed class of graphs that does not contain all planar graphs has a linear time recognition algorithm.",

keywords = "graph algorithms, graph minors, partial k-trees, pathwidth, treewidth",

author = "Bodlaender, {Hans L.}",

year = "1993",

doi = "10.1145/167088.167161",

language = "English",

series = "STOC '93",

publisher = "Association for Computing Machinery",

pages = "226--234",

booktitle = "Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing",

address = "United States",

}

A Linear Time Algorithm for Finding Tree-decompositions of Small Treewidth. / Bodlaender, Hans L.
Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing: STOC'93. New York, NY, USA: Association for Computing Machinery, 1993. p. 226-234 (STOC '93).

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

TY - GEN

T1 - A Linear Time Algorithm for Finding Tree-decompositions of Small Treewidth

AU - Bodlaender, Hans L.

PY - 1993

Y1 - 1993

N2 - In this paper, we give, for constant k, a linear time algorithm, that given a graph G = (V, E), determines whether the treewidth of G is at most k, and if so, finds a treedecomposition of G with treewidth at most k. A consequence is that every minor-closed class of graphs that does not contain all planar graphs has a linear time recognition algorithm.

AB - In this paper, we give, for constant k, a linear time algorithm, that given a graph G = (V, E), determines whether the treewidth of G is at most k, and if so, finds a treedecomposition of G with treewidth at most k. A consequence is that every minor-closed class of graphs that does not contain all planar graphs has a linear time recognition algorithm.

KW - graph algorithms, graph minors, partial k-trees, pathwidth, treewidth

U2 - 10.1145/167088.167161

DO - 10.1145/167088.167161

M3 - Conference contribution

T3 - STOC '93

SP - 226

EP - 234

BT - Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing

PB - Association for Computing Machinery

CY - New York, NY, USA

ER -

A Linear Time Algorithm for Finding Tree-decompositions of Small Treewidth

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this