Extension of Vertex Cover and Independent Set in some classes of graphs

DOI10.1007/978-3-030-17402-6_11MaRDI QIDQ2294045zbMATH OpenOpenAlexFDO

Authors Katrin Casel, Henning Fernau, Mehdi Khosravian Ghadikoalei, Jérôme Monnot, Florian Sikora

Publication date 6 February 2020

Full work available at URL https://arxiv.org/abs/1810.04629, https://basepub.dauphine.fr/handle/123456789/19243

zbMATH Keywords

approximation algorithmsNP-completenessspecial graph classesextension problems

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Extension and its price for the Connected Vertex Cover problem
• Extension and its price for the connected vertex cover problem
• On the complexity of solution extension of optimization problems
• Extension of some edge graph problems: standard, parameterized and approximation complexity
• Extension of some edge graph problems: standard and parameterized complexity

Cited in

(10)

• On the complexity of solution extension of optimization problems
• Extension and its price for the connected vertex cover problem
• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• Geodesic packing in graphs
• On locally optimal independent sets and vertex covers
• Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
• Can local optimality be used for efficient data reduction?
• Invited talks
• Extension of some edge graph problems: standard, parameterized and approximation complexity
• A characterization of König-Egerváry graphs with extendable vertex covers

This page was built for publication: Extension of Vertex Cover and Independent Set in some classes of graphs

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