Extension and its price for the Connected Vertex Cover problem

DOI10.1007/978-3-030-25005-8_26MaRDI QIDQ2301752zbMATH OpenOpenAlexFDO

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

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)

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

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)