Fixed-parameter tractability of treewidth and pathwidth

H.L. Bodlaender

doi:10.1007/978-3-642-30891-8_12

Fixed-parameter tractability of treewidth and pathwidth

H.L. Bodlaender

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

19 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 language	English
Title of host publication	The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday
Publisher	Springer
Pages	196-227
Number of pages	32
ISBN (Print)	9783642308901
DOIs	https://doi.org/10.1007/978-3-642-30891-8_12
Publication status	Published - 2012
Externally published	Yes

Publication series

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

Access to Document

10.1007/978-3-642-30891-8_12

Cite this

Bodlaender, H. L. (2012). Fixed-parameter tractability of treewidth and pathwidth. In The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday (pp. 196-227). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7370). Springer. https://doi.org/10.1007/978-3-642-30891-8_12

@inbook{2fba93b1d5ea45e68ec489db81c88ab6,

title = "Fixed-parameter tractability of treewidth and pathwidth",

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.",

author = "H.L. Bodlaender",

year = "2012",

doi = "10.1007/978-3-642-30891-8_12",

language = "English",

isbn = "9783642308901",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "196--227",

booktitle = "The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday",

address = "Germany",

}

Bodlaender, HL 2012, Fixed-parameter tractability of treewidth and pathwidth. in The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7370, Springer, pp. 196-227. https://doi.org/10.1007/978-3-642-30891-8_12

Fixed-parameter tractability of treewidth and pathwidth. / Bodlaender, H.L.
The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. Springer, 2012. p. 196-227 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7370).

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

TY - CHAP

T1 - Fixed-parameter tractability of treewidth and pathwidth

AU - Bodlaender, H.L.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84864148769&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-30891-8_12

DO - 10.1007/978-3-642-30891-8_12

M3 - Chapter

AN - SCOPUS:84864148769

SN - 9783642308901

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 196

EP - 227

BT - The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday

PB - Springer

ER -

Bodlaender HL. Fixed-parameter tractability of treewidth and pathwidth. In The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. Springer. 2012. p. 196-227. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-30891-8_12

Fixed-parameter tractability of treewidth and pathwidth

Abstract

Publication series

Access to Document

Other files and links

Fingerprint

Cite this