Premium
Reduction tests for the steiner problem in grapsh
Author(s) -
Duin C. W.,
Volgenant A.
Publication year - 1989
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230190506
Subject(s) - bottleneck , steiner tree problem , mathematics , combinatorics , euclidean geometry , enhanced data rates for gsm evolution , reduction (mathematics) , graph , random graph , algorithm , computer science , discrete mathematics , mathematical optimization , artificial intelligence , geometry , embedded system
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.