On reduction algorithms for graphs with small treewidth

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review


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 languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science
Subtitle of host publication19th International Workshop, WG '93 Utrecht, The Netherlands, June 16–18, 1993 Proceedings
EditorsJan van Leeuwen
Number of pages12
ISBN (Electronic)978-3-540-48385-4
ISBN (Print)978-3-540-57899-4
Publication statusPublished - 1994

Publication series

NameLecture Notes in Computer Science


Dive into the research topics of 'On reduction algorithms for graphs with small treewidth'. Together they form a unique fingerprint.

Cite this