| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428841 | Information Processing Letters | 2015 | 5 Pages |
Abstract
•No approximation algorithms are known for computing minimum spanning cactus and bottleneck spanning cactus.•For minimum spanning cactus approximation algorithm with relative error τ is presented.•For Bottleneck spanning cactus approximation algorithm with relative error 2τ−12τ−1 is presented.
We study minimum spanning cactus and bottleneck spanning cactus problems with τ-triangle inequality. Both problems are NP-Complete. No approximation algorithms are known for these problems. We present τ approximation algorithm for the first and 2τ−12τ−1 approximation algorithm for the second problem.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Alak Kumar Datta,