Treewidth and Pathwidth Parameterized by the Vertex Cover Number

Abstract : After the number of vertices, Vertex Cover Number is the largest of the classical graph parameters and has more and more frequently been used as a separate parameter in parameterized problems, including problems that are not directly related to the Vertex Cover Number. Here we consider the treewidth and pathwidth problems parameterized by k, the size of a minimum vertex cover of the input graph. We show that the pathwidth and treewidth can be computed in O *(3 k ) time. This complements recent polynomial kernel results for treewidth and pathwidth parameterized by the Vertex Cover Number.
Document type :
Conference papers
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00848369
Contributor : Mathieu Chapelle <>
Submitted on : Friday, July 26, 2013 - 10:21:16 AM
Last modification on : Thursday, January 17, 2019 - 3:06:04 PM

Links full text

Identifiers

Citation

Mathieu Chapelle, Mathieu Liedloff, Ioan Todinca, Yngve Villanger. Treewidth and Pathwidth Parameterized by the Vertex Cover Number. WADS 2013, Aug 2013, London, Ontario, Canada. pp.232-243, ⟨10.1007/978-3-642-40104-6_21⟩. ⟨hal-00848369⟩

Share

Metrics

Record views

227