Extension and its price for the Connected Vertex Cover problem

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

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

Publication date: 25 February 2020

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

Recommendations

• Extension and its price for the connected vertex cover problem
• Extension of Vertex Cover and Independent Set in some classes of graphs
• The price of connectivity for vertex cover
• Price of connectivity for the vertex cover problem and the dominating set problem: conjectures and investigation of critical graphs
• Complexity and Approximation Results for the Connected Vertex Cover Problem

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)