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

DOI10.1007/S10898-011-9831-XzbMATH Open1275.90118OpenAlexW2003830843MaRDI QIDQ2392763FDOQ2392763

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (23)

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

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)