Algorithms for Shortest Paths and d-cycle ProblemsAbstract: Let G be a weighted graph with n vertices and m edges. We address the d-cycle problem, i.e., the problem of finding a subgraph of minimum weight with given cyclomatic number d. Hartvigsen [1] presented an algorithm with running time O(n^2m) and O(n^{2d-1}m^2) for the cyclomatic numbers d=1 and d\ge 2, respectively. Using a (d+1)-shortest-paths algorithm, we develop a new more efficient algorithm for the d-cycle problem with running time O(n^{2d-1}+n^2m+n^3\log n). [1] D. Hartvigsen, Minimum path bases. Journal of Algorithms, 15 (1993) 125-142. @article{bk-asp-03 , author = "S. Bespamyatnikh and A. Kelarev" , title = "Algorithms for Shortest Paths and {$d$}-cycle Problems" , journal = "Journal of Discrete Algorithms" , volume = 1 , pages = "1--9" , year = 2003 } |