Fixed-parameter tractability of treewidth and pathwidth

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

13 Citations (Scopus)

Abstract

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
Pages196-227
Number of pages32
Volume7370
DOIs
Publication statusPublished - 2012
Externally publishedYes

Publication series

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

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

Cite this