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.
|Title of host publication||The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday|
|Number of pages||32|
|Publication status||Published - 2012|
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|