Fixed-parameter tractability of treewidth and pathwidth

H.L. Bodlaender

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

18 Citations (Scopus)


In this survey, a number of results on the fixed-parameter tractability of treewidth and pathwidth are discussed. Some emphasis is placed on older results, and proofs that show that treewidth and pathwidth are fixed-parameter tractable. Also, a linear-time algorithm for testing if a graph has pathwidth at most some given constant is discussed in more detail.

Original languageEnglish
Title of host publicationThe Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday
Number of pages32
Publication statusPublished - 2012
Externally publishedYes

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)03029743
ISSN (Electronic)16113349


Dive into the research topics of 'Fixed-parameter tractability of treewidth and pathwidth'. Together they form a unique fingerprint.

Cite this