Connected Vertex Covers in Dense Graphs

DOI10.1007/978-3-540-85363-3_4MaRDI QIDQ3541785zbMATH OpenOpenAlexFDO

Authors Jean Cardinal, Eythan Levy

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 algorithmconnected vertex coverdense graphvertex cover

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)

Recommendations

• Connected vertex covers in dense graphs
• Approximating vertex cover on dense graphs
• Approximating vertex cover in dense hypergraphs
• scientific article; zbMATH DE number 861353
• Covering a graph with densest subgraphs
• Deterministic parameterized connected vertex cover
• On the cover time of dense graphs
• The connected vertex cover problem in \(k\)-regular graphs
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Complexity and Approximation Results for the Connected Vertex Cover Problem

Cites work

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

Cited in

(7)

• Vertex and edge covers with clustering properties: Complexity and algorithms
• An efficient heuristic algorithm for solving connected vertex cover problem
• Approximating vertex cover on dense graphs
• Complexity and Approximation Results for the Connected Vertex Cover Problem
• The price of connectivity for vertex cover
• Connected vertex cover for \((sP_1+P_5)\)-free graphs
• Connected vertex covers in dense graphs

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

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