On reduction algorithms for graphs with small treewidth

Hans Bodlaender

doi:10.1007/3-540-57899-4_40

On reduction algorithms for graphs with small treewidth

Hans Bodlaender

Decision Support Systems

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

Abstract

Some new ideas are presented on graph reduction applied to graphs with bounded treewidth. It is shown that the method can not only be applied to solve decision problems, but also some optimization problems and construction variants of several of these problems on graphs with some constant upper bound on the treewidth.
Also, the existence is shown of finite, safe, complete, and terminating sets of reduction rules, such that on any graph G with treewidth at most some constant k, Ω(n) applications of reduction rules can be applied simultaneously. This result is used to obtain a class of randomized parallel algorithms that solve many problems on graphs with bounded treewidth and bounded degree in O(log n) expected time with O(n) processors on a EREW PRAM. Among others, such an algorithm is obtained to recognize the class of graphs with treewidth at most k and maximum vertex degree at most d, for constant k and d.

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science
Subtitle of host publication	19th International Workshop, WG '93 Utrecht, The Netherlands, June 16–18, 1993 Proceedings
Editors	Jan van Leeuwen
Publisher	Springer
Pages	45-56
Number of pages	12
Volume	790
ISBN (Electronic)	978-3-540-48385-4
ISBN (Print)	978-3-540-57899-4
DOIs	https://doi.org/10.1007/3-540-57899-4_40
Publication status	Published - 1994

Publication series

Name	Lecture Notes in Computer Science

Access to Document

10.1007/3-540-57899-4_40

http://dx.doi.org/10.1007/3-540-57899-4_40

Cite this

@inbook{aea2bc28bca34d58bd36c3af61649c52,

title = "On reduction algorithms for graphs with small treewidth",

abstract = "Some new ideas are presented on graph reduction applied to graphs with bounded treewidth. It is shown that the method can not only be applied to solve decision problems, but also some optimization problems and construction variants of several of these problems on graphs with some constant upper bound on the treewidth.Also, the existence is shown of finite, safe, complete, and terminating sets of reduction rules, such that on any graph G with treewidth at most some constant k, Ω(n) applications of reduction rules can be applied simultaneously. This result is used to obtain a class of randomized parallel algorithms that solve many problems on graphs with bounded treewidth and bounded degree in O(log n) expected time with O(n) processors on a EREW PRAM. Among others, such an algorithm is obtained to recognize the class of graphs with treewidth at most k and maximum vertex degree at most d, for constant k and d.",

author = "Hans Bodlaender",

year = "1994",

doi = "10.1007/3-540-57899-4_40",

language = "English",

isbn = "978-3-540-57899-4",

volume = "790",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "45--56",

editor = "{van Leeuwen}, Jan",

booktitle = "Graph-Theoretic Concepts in Computer Science",

}

On reduction algorithms for graphs with small treewidth. / Bodlaender, Hans.
Graph-Theoretic Concepts in Computer Science: 19th International Workshop, WG '93 Utrecht, The Netherlands, June 16–18, 1993 Proceedings. ed. / Jan van Leeuwen. Vol. 790 Springer, 1994. p. 45-56 (Lecture Notes in Computer Science).

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

TY - CHAP

T1 - On reduction algorithms for graphs with small treewidth

AU - Bodlaender, Hans

PY - 1994

Y1 - 1994

N2 - Some new ideas are presented on graph reduction applied to graphs with bounded treewidth. It is shown that the method can not only be applied to solve decision problems, but also some optimization problems and construction variants of several of these problems on graphs with some constant upper bound on the treewidth.Also, the existence is shown of finite, safe, complete, and terminating sets of reduction rules, such that on any graph G with treewidth at most some constant k, Ω(n) applications of reduction rules can be applied simultaneously. This result is used to obtain a class of randomized parallel algorithms that solve many problems on graphs with bounded treewidth and bounded degree in O(log n) expected time with O(n) processors on a EREW PRAM. Among others, such an algorithm is obtained to recognize the class of graphs with treewidth at most k and maximum vertex degree at most d, for constant k and d.

AB - Some new ideas are presented on graph reduction applied to graphs with bounded treewidth. It is shown that the method can not only be applied to solve decision problems, but also some optimization problems and construction variants of several of these problems on graphs with some constant upper bound on the treewidth.Also, the existence is shown of finite, safe, complete, and terminating sets of reduction rules, such that on any graph G with treewidth at most some constant k, Ω(n) applications of reduction rules can be applied simultaneously. This result is used to obtain a class of randomized parallel algorithms that solve many problems on graphs with bounded treewidth and bounded degree in O(log n) expected time with O(n) processors on a EREW PRAM. Among others, such an algorithm is obtained to recognize the class of graphs with treewidth at most k and maximum vertex degree at most d, for constant k and d.

U2 - 10.1007/3-540-57899-4_40

DO - 10.1007/3-540-57899-4_40

M3 - Chapter

SN - 978-3-540-57899-4

VL - 790

T3 - Lecture Notes in Computer Science

SP - 45

EP - 56

BT - Graph-Theoretic Concepts in Computer Science

A2 - van Leeuwen, Jan

PB - Springer

ER -

On reduction algorithms for graphs with small treewidth

Abstract

Publication series

Access to Document

Fingerprint

Cite this