Approximation algorithms for minimum weight connected 3-path vertex cover

DOI10.1016/j.amc.2018.11.045zbMath1428.05297OpenAlexW2903563585MaRDI QIDQ2008557

Xiaosong Li, Yingli Ran, Zhao Zhang, Ding-Zhu Du, Xiao-hui 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 algorithmweightnon-submodular potential functionconnected \(k\)-path vertex cover

Mathematics Subject Classification ID

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

Related Items (5)

The k‐path vertex cover: General bounds and chordal graphs ⋮ Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs ⋮ Approximation algorithm for minimum weight connected-\(k\)-subgraph cover ⋮ Approximation algorithm for minimum connected 3-path vertex cover

Cites Work

• Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
• On the weighted \(k\)-path vertex cover problem
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• 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 faster FPT algorithm for 3-path vertex cover
• The node-deletion problem for hereditary properties is NP-complete
• A unified approximation algorithm for node-deletion problems
• On approximability of the independent/connected edge dominating set problems
• On approximability of connected path vertex cover
• Fixed-parameter algorithms for Vertex Cover \(P_3\)
• On the \(k\)-path vertex cover of some graph products
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Minimum \(k\)-path vertex cover
• Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
• PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
• The vertex cover \(P_3\) problem in cubic graphs
• Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem
• A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
• A 2-approximation algorithm for the vertex coverP₄problem in cubic graphs
• Node-Deletion NP-Complete Problems
• Partitioning a Graph into Small Pieces with Applications to Path Transversal

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