Extension and its price for the connected vertex cover problem

DOI10.1016/j.tcs.2021.11.028OpenAlexW4225751077MaRDI QIDQ2072064

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

Publication date: 1 February 2022

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

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

zbMATH Keywords

approximation algorithmsspecial graph classesextension problemsconnected vertex cover\( \mathsf{NP} \)-completenessprice of extensionupper connected vertex cover

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

In memory of Jérôme Monnot

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A \(9k\) kernel for nonseparating independent set in planar graphs
• On the max min vertex cover problem
• Domination, independent domination, and duality in strongly chordal graphs
• Weakly triangulated graphs
• Connected vertex covers in dense graphs
• Vertex and edge covers with clustering properties: Complexity and algorithms
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• Depth-first search and the vertex cover problem
• On the algorithmic complexity of twelve covering and independence parameters of graphs
• Enumeration and maximum number of minimal connected vertex covers in graphs
• The many facets of upper domination
• On the approximate compressibility of connected vertex cover
• On the complexity of solution extension of optimization problems
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Complexity of independency and cliquy trees
• Extension of some edge graph problems: standard and parameterized complexity
• Extension of Vertex Cover and Independent Set in some classes of graphs
• Revisiting connected vertex cover: FPT algorithms and lossy kernels
• Polynomial kernels for vertex cover parameterized by small degree modulators
• On the Complexity Landscape of the Domination Chain
• A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs
• Deterministic Parameterized Connected Vertex Cover
• Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs
• On feedback vertex sets and nonseparating independent sets in cubic graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Maximum Minimal Vertex Cover Parameterized by Vertex Cover
• Dual subimplicants of positive Boolean functions
• On the Enumeration of Minimal Dominating Sets and Related Notions
• SOFSEM 2005: Theory and Practice of Computer Science

This page was built for publication: Extension and its price for the connected vertex cover problem