An edge elimination test for the Steiner Problem in graphs

An edge elimination test for the Steiner Problem in graphs

0.00 Avg rating0 Votes
Article ID: iaor1989648
Country: Netherlands
Volume: 8
Issue: 2
Start Page Number: 79
End Page Number: 83
Publication Date: Apr 1989
Journal: Operations Research Letters
Authors: ,
Abstract:

It is known that before actually solving the Steiner Problem in graphs, reduction tests can considerably reduce the problem size. One of them, the Least Cost test, eliminates an edge (i,j) if its length exceeds the shortest path length between nodes i and j. This test is considerably improved by replacing shortest path length with ‘special distance’, a motion based on a min-max measure. The test also generalizes a reduction method that uses minimum spanning trees. The matrix of special distances can be calculated in the same time complexity order as the matrix of all the shortest path lengths. Computational results on different types of problem graphs show that respectable reduction is attained by the test.

Reviews

Required fields are marked *. Your email address will not be published.