Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875522 | Theoretical Computer Science | 2018 | 21 Pages |
Abstract
In this paper, we address the problem of finding a maximum 2-packing set in a cactus. Let G=(VG,EG) be an undirected connected graph; then a subset SâVG is a 2-packing set if for every pair of vertices u,vâS, the shortest path between them is at least three edges long. This type of sets results in a wide range of applications such as the study of molecules, network modeling, allocation of facilities, and frequency assignment. The cactus is a planar graph such that any edge belongs to at most one cycle. Hitherto, to the best of the authors' knowledge, no algorithm finds a maximum 2-packing set in a cactus. This problem is NP-Hard in arbitrary graphs. Our approach to solving this problem was first finding a maximum 2-packing set in a unicyclic graph. Then, we adapted this algorithm to run in a cactus. The time complexity of the resulting algorithm is O(n2), where n=|VG|.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Alejandro Flores-Lamas, José Alberto Fernández-Zepeda, Joel Antonio Trejo-Sánchez,