Extension and its price for the Connected Vertex Cover problem

DOI10.1007/978-3-030-25005-8_26OpenAlexW2961777252MaRDI QIDQ2301752FDOQ2301752

Nikolaos Melissinos, Mehdi Khosravian Ghadikoalei, Aris Pagourtzis, Jérôme Monnot

Publication date: 25 February 2020

Full work available at URL: https://doi.org/10.1007/978-3-030-25005-8_26

zbMATH Keywords

approximation algorithmsNP-completenessspecial graph classesextension problemsconnected vertex coverprice of extensionupper connected vertex cover

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cited In (5)

• Extension of the Nemhauser and Trotter Theorem to Generalized Vertex Cover with Applications
• On the complexity of solution extension of optimization problems
• Price of connectivity for the vertex cover problem and the dominating set problem: conjectures and investigation of critical graphs
• Can local optimality be used for efficient data reduction?
• Invited talks

This page was built for publication: Extension and its price for the Connected Vertex Cover problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2301752)