Algorithms for Shortest Paths and d-cycle Problems

Abstract: 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
}