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

DOI10.1007/S10878-018-0283-9zbMATH Open1402.90139OpenAlexW2794918889WikidataQ130058266 ScholiaQ130058266MaRDI QIDQ724732FDOQ724732

Authors: Lina Chen, Zhao Zhang, Xiaohui 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

Recommendations

• A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks
• PTAS for minimum connected dominating set with routing cost constraint in wireless sensor networks
• K-Connected Target Coverage Problem in Wireless Sensor Networks
• An algorithm for minimal connected cover set problem in wireless sensor networks
• Connected \(K\)-target coverage problem in wireless sensor networks with different observation scenarios
• A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
• Simple approximation algorithms and PTASs for various problems in wireless ad hoc networks

zbMATH Keywords

approximation algorithmconnected \(k\)-path vertex coverPTASunit disk graph

Mathematics Subject Classification ID

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

Cites Work

• 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
• Narrow sieves for parameterized paths and packings
• Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• 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
• A PTAS for minimum \(d\)-hop connected dominating set in growth-bounded graphs
• An inequality in the geometry of numbers
• A PTAS FOR MINIMUM d-HOP UNDERWATER SINK PLACEMENT PROBLEM IN 2-D UNDERWATER SENSOR NETWORKS
• A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
• Fixed-parameter algorithms for Vertex Cover \(P_3\)
• A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
• 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 NEW PROOF FOR ZASSENHAUS–GROEMER–OLER INEQUALITY

Cited In (8)

• Approximation algorithm for minimum connected 3-path vertex cover
• Approximation algorithms for minimum weight connected 3-path vertex cover
• Approximation algorithm for minimum weight connected-\(k\)-subgraph cover
• PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
• 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
• The k‐path vertex cover: General bounds and chordal graphs
• Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs

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

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