Algorithms for shortest paths and d-cycle problems

AbstractLet 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 [Minimum path bases, J. Algorithms 15 (1993) 125–142] presented an algorithm with running time O(n2m) and O(n2d−1m2) for the cyclomatic numbers d=1 and d⩾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(n2d−1+n2m+n3logn)