A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network

DOI10.1007/S10878-018-0283-9zbMath1402.90139OpenAlexW2794918889WikidataQ130058266 ScholiaQ130058266MaRDI QIDQ724732

Lina Chen, Zhao Zhang, Xiao-hui Huang

Publication date: 26 July 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-018-0283-9

zbMATH Keywords

approximation algorithmPTASconnected \(k\)-path vertex coverunit disk graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (5)

The k‐path vertex cover: General bounds and chordal graphs ⋮ 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 ⋮ Approximation algorithms for minimum weight connected 3-path vertex cover

Cites Work

• Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
• PTAS for minimum \(k\)-path vertex cover in ball graph
• A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• An inequality in the geometry of numbers
• A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
• Fixed-parameter algorithms for Vertex Cover \(P_3\)
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• A PTAS for minimum \(d\)-hop connected dominating set in growth-bounded graphs
• Minimum \(k\)-path vertex cover
• PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
• Narrow sieves for parameterized paths and packings
• A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
• A NEW PROOF FOR ZASSENHAUS–GROEMER–OLER INEQUALITY
• A PTAS FOR MINIMUM d-HOP UNDERWATER SINK PLACEMENT PROBLEM IN 2-D UNDERWATER SENSOR NETWORKS
• Approximation schemes for covering and packing problems in image processing and VLSI
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks

This page was built for publication: A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network