An edge elimination test for the Steiner problem in graphs
type: Item
instance of: scholarly article
title: An edge elimination test for the Steiner problem in graphs
zbMATH Open document ID: 0665.90093
DOI: 10.1016/0167-6377(89)90005-9
author: A. Volgenant
author: Cees Duin
published in: Operations Research Letters
publication date: 1989-01-01T00:00:00Z
review text: 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 notion 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.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 4089350
zbMATH Keywords: graph reduction
zbMATH Keywords: bottleneck length
zbMATH Keywords: Steiner Problem in graphs
zbMATH Keywords: reduction tests
zbMATH Keywords: Least Cost test
zbMATH Keywords: shortest path
zbMATH Keywords: special distance
zbMATH Keywords: minimum spanning trees
MaRDI profile type: Publication
full work available at URL: 0167-6377(89)90005-9
OpenAlex ID: W2004092973
cites work: Problem reduction methods and a tree generation algorithm for the steiner network problem
cites work: An algorithm for the steiner problem in graphs
cites work: An SST-based algorithm for the steiner problem in graphs
cites work: A note on two problems in connexion with graphs
cites work: Reduction tests for the steiner problem in grapsh
cites work: Some generalizations of the steiner problem in graphs
cites work: Reducing the hierarchical network design problem
cites work: Steiner's problem in graphs and its implications
cites work: Q3760270
cites work: Steiner problem in networks: A survey
description: scientific article; zbMATH DE number 4089350