eCite Digital Repository

Algorithms for shortest paths and d-cycle problems


Bespamyatnikh, S and Kelarev, AV, Algorithms for shortest paths and d-cycle problems, Journal of Discrete Algorithms, 1, (1) pp. 1-9. ISSN 1570-8667 (2003) [Refereed Article]

DOI: doi:10.1016/S1570-8667(03)00002-9


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 [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.

Item Details

Item Type:Refereed Article
Research Division:Information and Computing Sciences
Research Group:Theory of computation
Research Field:Data structures and algorithms
Objective Division:Information and Communication Services
Objective Group:Information systems, technologies and services
Objective Field:Information systems, technologies and services not elsewhere classified
UTAS Author:Kelarev, AV (Dr Andrei Kelarev)
ID Code:27383
Year Published:2003
Deposited By:Computing
Deposited On:2003-08-01
Last Modified:2011-11-04

Repository Staff Only: item control page