PTAS for the minimum k-path connected vertex cover problem in unit disk graphs

DOI10.1007/S10898-011-9831-XMaRDI QIDQ2392763zbMATH OpenOpenAlexFDO

Authors Xianliang Liu, Hongliang Lu, Wei Wang, Weili Wu

Publication date 2 August 2013

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10898-011-9831-x

zbMATH Keywords

PTASunit disk graph\(k\)-path connected vertex cover

Mathematics Subject Classification ID

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

Recommendations

• A simpler PTAS for connected k-path vertex cover in homogeneous wireless sensor network
• Approximation algorithms for minimum (weight) connected k-path vertex cover
• Approximation algorithm for the minimum connected \(k\)-path vertex cover problem
• PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs
• Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 954401 (Why is no real title available?)
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• An approximation scheme for some Steiner tree problems in the plane
• Computer Aided Systems Theory – EUROCAST 2005
• Formal analysis of security protocols for wireless sensor networks
• Minimum \(k\)-path vertex cover
• PTAS for connected vertex cover in unit disk graphs

Cited in

(23)

• Approximation algorithm for the minimum connected \(k\)-path vertex cover problem
• Theory and application of reciprocal transformation of “path problem” and “time float problem”
• A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
• A PTAS for the Weighted Unit Disk Cover Problem
• PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs
• Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem
• A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
• Approximation algorithm for minimum weight connected-\(k\)-subgraph cover
• Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph
• Solving the multistage PMU placement problem by integer programming and equivalent network design model
• PTAS for connected vertex cover in unit disk graphs
• A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network
• The weighted \(k\)-path vertex cover problem on series-parallel graphs
• Approximation algorithm for minimum connected 3-path vertex cover
• Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs
• Approximation algorithms for minimum weight connected 3-path vertex cover
• PTAS for minimum \(k\)-path vertex cover in ball graph
• A PTAS for the cardinality constrained covering with unit balls
• Approximation and Online Algorithms
• A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks
• Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
• PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
• On the weighted \(k\)-path vertex cover problem

This page was built for publication: PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs

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