Vertex and edge covers with clustering properties: Complexity and algorithms

DOI10.1016/j.jda.2008.09.007zbMath1187.68342OpenAlexW2062366051MaRDI QIDQ1026225

David F. Manlove, Henning Fernau

Publication date: 24 June 2009

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2008.09.007

zbMATH Keywords

approximation algorithmNP-completenesspolynomial-time algorithmFPT algorithmconnected vertex cover\(t\)-total edge cover\(t\)-total vertex cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (27)

Some observations on holographic algorithms ⋮ On approximating (connected) 2-edge dominating set by a tree ⋮ The \(k\)-hop connected dominating set problem: hardness and polyhedra ⋮ Boundary classes for graph problems involving non-local properties ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity ⋮ Extension of some edge graph problems: standard, parameterized and approximation complexity ⋮ The connected vertex cover problem in \(k\)-regular graphs ⋮ Complexity and Approximation Results for the Connected Vertex Cover Problem ⋮ On complementary coverage of \({\Omega}_n(T)\) ⋮ An efficient heuristic algorithm for solving connected vertex cover problem ⋮ On Complexity of Total Vertex Cover on Subcubic Graphs ⋮ Connected Vertex Covers in Dense Graphs ⋮ Enumerate and expand: Improved algorithms for connected vertex cover and tree cover ⋮ On the parameterized complexity of vertex cover and edge cover with connectivity constraints ⋮ Parameterized measure \& conquer for problems with no small kernels ⋮ On Approximating (Connected) 2-Edge Dominating Set by a Tree ⋮ Kernels for packing and covering problems ⋮ Parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover ⋮ Enumerate and Measure: Improving Parameter Budget Management ⋮ Connected vertex cover for \((sP_1+P_5)\)-free graphs ⋮ Metabolic networks are NP-hard to reconstruct ⋮ Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers ⋮ On cycle transversals and their connected variants in the absence of a small linear forest ⋮ Nonseparating independent sets of Cartesian product graphs ⋮ Extension and its price for the connected vertex cover problem ⋮ Parameterized complexity of multi-node hubs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating the tree and tour covers of a graph
• On the hardness of approximating minimum vertex cover
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• The parameterized complexity of the induced matching problem
• 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
• Optimization, approximation, and complexity classes
• Some simplified NP-complete graph problems
• On the algorithmic complexity of twelve covering and independence parameters of graphs
• Maximum bounded \(H\)-matching is Max SNP-complete
• Approximation algorithms for the test cover problem
• The Turing way to parameterized complexity
• Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
• Complexity of approximating bounded variants of optimization problems
• Dynamic programming for minimum Steiner trees
• Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
• An Efficient Exact Algorithm for Constraint Bipartite Vertex Cover
• An Algorithm for a Minimum Cover of a Graph
• Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• Kernels: Annotated, Proper and Induced
• Complexity and Approximation Results for the Connected Vertex Cover Problem
• Connected Vertex Covers in Dense Graphs
• Fourier meets M\"{o}bius: fast subset convolution
• Enumerate and Expand: New Runtime Bounds for Vertex Cover Variants
• Total domination in graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Algorithms and Data Structures
• On the completeness of a generalized matching problem
• A Faster Algorithm for the Steiner Tree Problem
• A Parameterized Perspective on Packing Paths of Length Two
• Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph
• The steiner problem in graphs
• Network Analysis
• STACS 2005
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Vertex and edge covers with clustering properties: Complexity and algorithms