PTAS for minimum \(k\)-path vertex cover in ball graph

DOI10.1016/j.ipl.2016.11.003zbMath1401.68365OpenAlexW2552909035MaRDI QIDQ503602

Zhao Zhang, Yuqing Zhu, Hongmei Nie, Xiaoting Li, Yishuo Shi

Publication date: 13 January 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2016.11.003

zbMATH Keywords

approximation algorithmsPTAS\(k\)-path vertex coverball graph

Mathematics Subject Classification ID

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

Related Items (7)

Unnamed Item ⋮ Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ Approximation algorithm for minimum weight connected-\(k\)-subgraph cover ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ Approximation algorithm for minimum connected 3-path vertex cover ⋮ A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network ⋮ Vertex cover at distance on \(H\)-free graphs

Cites Work

• Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
• On the weighted \(k\)-path vertex cover problem
• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• Improved results on geometric hitting set problems
• 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 faster FPT algorithm for 3-path vertex cover
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• The node-deletion problem for hereditary properties is NP-complete
• A unified approximation algorithm for node-deletion problems
• 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 vertex cover in ball graphs through local search
• Minimum \(k\)-path vertex cover
• The \(k\)-path vertex cover of rooted product graphs
• PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
• Narrow sieves for parameterized paths and packings
• The vertex cover \(P_3\) problem in cubic graphs
• On the vertex \(k\)-path cover
• 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
• A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion
• Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs
• Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
• Node-Deletion NP-Complete Problems
• Approximation algorithms for maximum independent set of pseudo-disks

This page was built for publication: PTAS for minimum \(k\)-path vertex cover in ball graph