An algorithm for the determination of longest distances in a graph |
| |
Authors: | Hartmut Noltemeier |
| |
Institution: | (1) University of Göttingen, Göttingen, West Germany |
| |
Abstract: | This paper presents an algorithm for ranking the vertices of a directed graph. Its space and time requirements are bounded byc
1
n
2 +c
2, wheren is the number of vertices of the graph andc
1,c
2 are positive constants which are independent of the size or other properties of the graph.The algorithm can be easily modified to solve the problem of determining longest distances from a vertex to all other vertices in a positive real valued graph with at mostc
1
n
2 +c
2 elementary operations; the same result holds for shortest distances in negative real valued graphs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|