Journal
OPTIMIZATION LETTERS
Volume 17, Issue 6, Pages 1435-1454Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s11590-022-01939-w
Keywords
Approximation algorithms; Maximum 2-packing set; Linear programming; Planar graphs
Ask authors/readers for more resources
This paper proposes an approximation algorithm for the maximum 2-packing set problem for planar graphs. By decomposing the graph into smaller subgraphs and improving the solution by adding some vertices, the algorithm computes a near-optimal 2-packing set.
Given an undirected graph G = (V, E), a subset S subset of V is a 2-packing set if, for any pair of vertices u, v is an element of S, the shortest path between them is at least three-edge long. Finding a 2-packing set of maximum cardinality is an NP-hard problem for arbitrary graphs. This paper proposes an approximation algorithm for the maximum 2-packing set problem for planar graphs. We show that our algorithm is at least lambda-2/lambda of the optimal (i.e. the approximation ratio is lambda/lambda-2), where lambda is a constant related to how the proposed algorithm decomposes the input graph into smaller subgraphs. Then, we improve the solution given by our approximation algorithm by adding some vertices to the solution. Experimentally, we show that our improved algorithm computes a near-optimal 2-packing set. This algorithm is the first approximation algorithm for the maximum 2-packing set to the best of our knowledge.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available