Extension and its price for the connected vertex cover problem

DOI10.1016/J.TCS.2021.11.028MaRDI QIDQ2072064zbMATH OpenOpenAlexFDO

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

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

\( \mathsf{NP} \)-completenessapproximation algorithmsconnected vertex coverextension problemsprice of extensionspecial graph classesupper connected vertex cover

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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

Cites work

• A \(9k\) kernel for nonseparating independent set in planar graphs
• A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Complexity of independency and cliquy trees
• Connected vertex covers in dense graphs
• Depth-first search and the vertex cover problem
• Deterministic parameterized connected vertex cover
• Domination, independent domination, and duality in strongly chordal graphs
• Dual subimplicants of positive Boolean functions
• Enumeration and maximum number of minimal connected vertex covers in graphs
• Extension of some edge graph problems: standard and parameterized complexity
• Extension of Vertex Cover and Independent Set in some classes of graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1511711 (Why is no real title available?)
• scientific article; zbMATH DE number 1522921 (Why is no real title available?)
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Maximum minimal vertex cover parameterized by vertex cover
• On feedback vertex sets and nonseparating independent sets in cubic graphs
• On the algorithmic complexity of twelve covering and independence parameters of graphs
• On the approximate compressibility of connected vertex cover
• On the complexity landscape of the domination chain
• On the complexity of solution extension of optimization problems
• On the enumeration of minimal dominating sets and related notions
• On the max min vertex cover problem
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• Polynomial delay algorithm for listing minimal edge dominating sets in graphs
• Polynomial kernels for vertex cover parameterized by small degree modulators
• Revisiting connected vertex cover: FPT algorithms and lossy kernels
• SOFSEM 2005: Theory and Practice of Computer Science
• The many facets of upper domination
• The Rectilinear Steiner Tree Problem is NP-Complete
• Vertex and edge covers with clustering properties: Complexity and algorithms
• Weakly triangulated graphs

Cited in

(6)

• Price of connectivity for the vertex cover problem and the dominating set problem: conjectures and investigation of critical graphs
• In memory of Jérôme Monnot
• Extension of Vertex Cover and Independent Set in some classes of graphs
• Extension and its price for the Connected Vertex Cover problem
• Extension of the Nemhauser and Trotter Theorem to Generalized Vertex Cover with Applications
• Can local optimality be used for efficient data reduction?

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 Q2072064)