Approximation algorithm for minimum connected 3-path vertex cover
DOI10.1016/J.DAM.2020.08.008zbMATH Open1448.05164OpenAlexW3080897928MaRDI QIDQ2004079FDOQ2004079
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
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
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- The node-deletion problem for hereditary properties is NP-complete
- A unified approximation algorithm for node-deletion problems
- 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
- 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
- Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
- A 2-approximation algorithm for the vertex cover \(P_{4}\) problem in cubic graphs
- Node-Deletion NP-Complete Problems
- On the weighted \(k\)-path vertex cover problem
- A fixed-parameter algorithm for the vertex cover \(P_3\) problem
- 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
- Title not available (Why is that?)
- Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
- Connected vertex covers in dense graphs
- Independent packings in structured graphs
- Fixed-parameter algorithms for Vertex Cover \(P_3\)
- PTAS for minimum \(k\)-path vertex cover in ball graph
- A faster FPT algorithm for 3-path vertex cover
- Approximation algorithms for minimum weight connected 3-path vertex cover
- The complexity of dissociation set problems in graphs
- Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
- A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network
- On approximability of connected path vertex cover
- Partitioning a graph into small pieces with applications to path transversal
- Hitting subgraphs in \(P_4\)-tidy graphs
Cited In (9)
- 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
- The k‐path vertex cover: General bounds and chordal graphs
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)
