On cutwidth parameterized by vertex cover

DOI10.1007/s00453-012-9707-6zbMath1303.05185WikidataQ59397976 ScholiaQ59397976MaRDI QIDQ476444

Marek Cygan, Marcin Pilipczuk, Saket Saurabh, Michał Pilipczuk, Daniel Lokshtanov

Publication date: 2 December 2014

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9707-6

zbMATH Keywords

cutwidth; parameterized complexity; polynomial kernel; composition algorithms; vertex cover parameterization

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

05C35: Extremal problems in graph theory

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)