Distance conserving reductions for nonoriented networks

Summary

We describe a procedure for reducing the number of edges of a given nonoriented network in such a way, that the shortest distances between the original vertices are conserved. It is based on the triangle condition and on generating additional vertices. For a network optimization problem, such as the travelling salesman problem, the procedure achieves an essential reduction of the number of variables and of the solution effort. The computational results show that the reduced number of edges depends about linearly on the number of vertices.

Zusammenfassung

Es wird ein Verfahren beschrieben, das die Anzahl der Kanten eines gegebenen ungerichteten Netzwerkes in der Weise verringert, daß die kürzesten Entfernungen zwischen den ursprünglichen Knoten erhalten bleiben. Es beruht auf der Anwendung der Dreiecksungleichung und der Erzeugung zusätzlicher Knoten. Das Verfahren bewirkt für Netzwerk-Optimierungsprobleme, etwa für das Rundreiseproblem, eine wesentliche Reduzierung der Anzahl der Variablen und des Lösungsaufwands. Die Rechenergebnisse zeigen, daß die reduzierte Anzahl der Kanten etwa linear von der Anzahl der Knoten des Netzwerks abhängt.