On the parameterized complexity of vertex cover and edge cover with connectivity constraints

DOI10.1016/j.tcs.2014.10.035zbMath1315.68150WikidataQ59864899 ScholiaQ59864899MaRDI QIDQ482281

Henning Fernau, Fedor V. Fomin, Saket Saurabh, Geevarghese Philip

Publication date: 22 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.10.035

zbMATH Keywords

edge cover; vertex cover; parameterized complexity; kernel lower bounds; connectivity problems

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

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

05C40: Connectivity