0000000000336131
AUTHOR
Aarni Perko
External labeling and algorithms for hierarchic networks
Algorithms for generating internal data structures for networks are given. Data bases for networks can be partitioned hierarchically. Nodes of lower class networks may also be in the interior of a higher class arc which will be split if it is included into the final network. Naming is based either on nodes or on arcs.
Implementation of algorithms forK shortest loopless paths
Implementations of loopless k shortest path algorithms are examined. Efficient storage structures for a large number of paths are given. A fast algorithm for determining the shortest paths in Yen's method is developed. Timing experiments show that a hybrid of Clarke's and Yen's methods is generally the fastest, although not significantly. Using upper bounds for the lengths of paths essentially improves all methods.