Spanning cactus: Complexity and extensions

作者：Datta Alak Kumar^*; Debnath Chinmay

来源：Discrete Applied Mathematics, 2017, 233: 19-28.

DOI：10.1016/j.dam.2017.08.020

• Approximation algorithms
• Minimum spanning cactus
• NP-Completeness
• Minimum spanning tree

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(n(3)) algorithm to compute all minimum cost monotone paths with respect to a spanning tree.

• 出版日期2017-12-31