Approximation algorithms for minimum weight connected 3-path vertex cover

DOI10.1016/J.AMC.2018.11.045MaRDI QIDQ2008557zbMATH OpenOpenAlexFDO

Authors Yingli Ran, Zhao Zhang, X. Li, Du Ding-Zhu, Xiaohui Huang

Publication date 26 November 2019

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2018.11.045

zbMATH Keywords

approximation algorithmweightconnected \(k\)-path vertex covernon-submodular potential function

Mathematics Subject Classification ID

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

Recommendations

• Approximation algorithm for minimum connected 3-path vertex cover
• Approximation algorithms for minimum (weight) connected k-path vertex cover
• Approximation algorithm for the minimum connected \(k\)-path vertex cover problem
• An approximation algorithm for the minimum weighted vertex-cover problem
• On approximability of connected path vertex cover
• Approximation algorithms for covering a graph by vertex-disjoint paths of maximum total weight
• Approximation algorithm for the minimum weight connected k-subgraph cover problem
• Approximation algorithm for minimum weight connected-\(k\)-subgraph cover
• Parameterized algorithm for 3-path vertex cover
• On computing the minimum 3-path vertex cover and dissociation number of graphs

Cites work

• A 2-approximation algorithm for the vertex cover \(P_{4}\) problem in cubic graphs
• A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks
• A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• A faster FPT algorithm for 3-path vertex cover
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network
• A unified approximation algorithm for node-deletion problems
• Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem
• Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
• Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• Fixed-parameter algorithms for Vertex Cover \(P_3\)
• Minimum \(k\)-path vertex cover
• Node-Deletion NP-Complete Problems
• On approximability of connected path vertex cover
• On approximability of the independent/connected edge dominating set problems
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• On the \(k\)-path vertex cover of some graph products
• On the weighted \(k\)-path vertex cover problem
• PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
• Partitioning a graph into small pieces with applications to path transversal
• The node-deletion problem for hereditary properties is NP-complete
• The vertex cover \(P_3\) problem in cubic graphs

Cited in

(19)

• Approximation algorithm for the minimum connected \(k\)-path vertex cover problem
• On approximability of connected path vertex cover
• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• An improved approximation algorithm for the minimum 3-path partition problem
• A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
• Improved approximation algorithm for minimum weight \(k\)-subgraph cover problem
• Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem
• Approximation algorithm for minimum weight connected-\(k\)-subgraph cover
• The k‐path vertex cover: General bounds and chordal graphs
• A faster FPT algorithm for 3-path vertex cover
• The weighted \(k\)-path vertex cover problem on series-parallel graphs
• Computing connected-\(k\)-subgraph cover with connectivity requirement
• Approximation algorithm for minimum connected 3-path vertex cover
• Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• Improved approximation algorithms for path vertex covers in regular graphs
• A multi-start iterated greedy algorithm for the minimum weight vertex cover \(P_3\) problem
• Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
• On the weighted \(k\)-path vertex cover problem

This page was built for publication: Approximation algorithms for minimum weight connected 3-path vertex cover

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