Fixed-parameter tractability of treewidth and pathwidth

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureHoofdstukAcademicpeer review

13 Citaten (Scopus)

Samenvatting

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.

Originele taal-2Engels
TitelThe Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday
Pagina's196-227
Aantal pagina's32
Volume7370
DOI's
StatusGepubliceerd - 2012
Extern gepubliceerdJa

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7370
ISSN van geprinte versie03029743
ISSN van elektronische versie16113349

Vingerafdruk Duik in de onderzoeksthema's van 'Fixed-parameter tractability of treewidth and pathwidth'. Samen vormen ze een unieke vingerafdruk.

Citeer dit