Connected Vertex Covers in Dense Graphs

DOI10.1007/978-3-540-85363-3_4zbMath1159.68044OpenAlexW2296656187MaRDI QIDQ3541785

Eythan Levy, Jean Cardinal

Publication date: 27 November 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85363-3_4

zbMATH Keywords

approximation algorithmvertex coverconnected vertex coverdense graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (2)

An efficient heuristic algorithm for solving connected vertex cover problem ⋮ Vertex and edge covers with clustering properties: Complexity and algorithms

Cites Work

• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• Facet defining inequalities among graph invariants: The system graphedron
• Vertex and edge covers with clustering properties: Complexity and algorithms
• Depth-first search and the vertex cover problem
• Approximating the dense set-cover problem
• An approximation of the minimum vertex cover in a graph
• A 2-approximation NC algorithm for connected vertex cover and tree cover
• Parameterized complexity of Vertex Cover variants
• Principles of cost minimisation in wireless networks
• Complexity and Approximation Results for the Connected Vertex Cover Problem
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Improved Approximation Bounds for Edge Dominating Set in Dense Graphs
• Computing and Combinatorics
• Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
• Unnamed Item
• Unnamed Item

This page was built for publication: Connected Vertex Covers in Dense Graphs