Algorithms for shortest paths and d-cycle problems |
| |
Authors: | Sergei Bespamyatnikh Andrei Kelarev |
| |
Institution: | a Department of Computer Science, University of British Columbia, Vancouver, BC, Canada V6T 1Z4;b Faculty of Science and Engineering, University of Tasmania, GPO Box 252-37, Hobart, Tasmania 7001, Australia |
| |
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(n2m) and O(n2d−1m2) for the cyclomatic numbers d=1 and d2, 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). |
| |
Keywords: | Shortest path Cyclomatic number d-cycle problem |
本文献已被 ScienceDirect 等数据库收录! |
|