Reduction tests for the steiner problem in grapsh
Cees W. Duin, Anton Volgenant · Networks · 1989
Abstract Before actually solving the Steiner problem in graphs, it is knwon that recution tests may reduce the problem size, e. g., by eliminating vertices from the graph. We improve existing tests and develop new techniques based on a bottleneck approach. The latter include optimal edge detection, edge elimination, and node elimination because of degree considerations. We give computational results of a recution algorithm on a large number of test problem. These problems have up to 200 vertices; their edge densities vary from sparse to complete with Euclidean weights as well as unifirmly random. The algorithm solves the majority of the test problems by recution tests only, and reduces the size of the remaining problems to at most one fourth of the original size.