eCite Digital Repository
Algorithms for shortest paths and d-cycle problems
Citation
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
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 [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 |
| Downloads: | 0 |
Repository Staff Only: item control page