File(s) not publicly available
Algorithms for shortest paths and d-cycle problems
journal contribution
posted on 2023-05-16, 14:23 authored by Bespamyatnikh, S, Kelarev, AVLet 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(n2 m) and O(n2-1 m) 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 +n2 m + n3 logn). © 2003 Elsevier B.V. All rights reserved.
History
Publication title
Journal of Discrete AlgorithmsPagination
1-9ISSN
1570-8667Department/School
School of Information and Communication TechnologyPublisher
Elsevier Science BVPlace of publication
Amsterdam, NetherlandsRepository Status
- Restricted