Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949463 | Discrete Applied Mathematics | 2017 | 10 Pages |
Abstract
Minimum spanning cactus and minimum spanning cactus extension problems are studied. Both problems are NP-Complete. We present an approximation algorithm for the minimum spanning cactus extension of a forest, a hardness of approximation result of the general minimum spanning cactus problem. For the minimum spanning cactus extension problem, Kabadi and Punnen presented polynomial time algorithms for extending quasi-stars, spanning trees (Kabadi and Punnen, 2013). We present improved analysis of their algorithms in both cases. We further show that their algorithm for the extension of spanning trees can be generalized to extend any connected spanning partial cactus. As a requirement of improved implementation, we have presented a new O(n3) algorithm to compute all minimum cost monotone paths with respect to a spanning tree.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Alak Kumar Datta, Chinmay Debnath,