Approximation algorithm for minimum connected 3-path vertex cover

DOI10.1016/J.DAM.2020.08.008MaRDI QIDQ2004079zbMATH OpenOpenAlexFDO

Authors Pengcheng Liu, Zhao Zhang, Xianyue Li, Weili Wu

Publication date 14 October 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2020.08.008

zbMATH Keywords

approximation algorithmconnected \(k\)-path vertex cover

Mathematics Subject Classification ID

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

Recommendations

• Approximation algorithm for the minimum connected \(k\)-path vertex cover problem
• Approximation algorithms for minimum (weight) connected k-path vertex cover
• Approximation algorithms for minimum weight connected 3-path vertex cover
• Approximation algorithm for the minimum weight connected k-subgraph cover problem
• On approximability of connected path vertex cover

Cites work

• scientific article; zbMATH DE number 2192124 (Why is no real title available?)
• A 2-approximation algorithm for the vertex cover \(P_{4}\) problem in cubic graphs
• A factor 2 approximation algorithm for the vertex cover P₃ problem
• A faster FPT algorithm for 3-path vertex cover
• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• 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
• Approximation algorithms for minimum weight connected 3-path vertex cover
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Connected vertex covers in dense graphs
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• Fixed-parameter algorithms for Vertex Cover \(P_3\)
• Hitting subgraphs in \(P_4\)-tidy graphs
• Independent packings in structured graphs
• Minimum \(k\)-path vertex cover
• Node-Deletion NP-Complete Problems
• On approximability of connected path vertex cover
• 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 minimum \(k\)-path vertex cover in ball graph
• 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 complexity of dissociation set problems in graphs
• The node-deletion problem for hereditary properties is NP-complete
• The vertex cover \(P_3\) problem in cubic graphs

Cited in

(9)

• The k‐path vertex cover: General bounds and chordal graphs
• Approximation algorithms for minimum (weight) connected k-path vertex cover
• Approximation algorithms for minimum weight connected 3-path vertex cover
• On approximability of connected path vertex cover
• Approximation algorithm for the minimum connected \(k\)-path vertex cover problem
• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• Algorithm for online 3-path vertex cover
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• A faster FPT algorithm for 3-path vertex cover

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

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