An edge elimination test for the Steiner problem in graphs

DOI10.1016/0167-6377(89)90005-9MaRDI QIDQ1116902zbMATH OpenOpenAlexFDO

Authors A. Volgenant, Cees Duin

Publication date 1989

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(89)90005-9

zbMATH Keywords

bottleneck lengthgraph reductionLeast Cost testminimum spanning treesreduction testsshortest pathspecial distanceSteiner Problem in graphs

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Programming involving graphs or networks (90C35)

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.

Recommendations

• Reduction tests for the steiner problem in grapsh
• scientific article; zbMATH DE number 1163709
• Publication:3471884
• An SST-based algorithm for the steiner problem in graphs
• On reductions for the Steiner problem in graphs

Cites work

• A note on two problems in connexion with graphs
• An algorithm for the steiner problem in graphs
• An SST-based algorithm for the steiner problem in graphs
• scientific article; zbMATH DE number 4010182 (Why is no real title available?)
• Problem reduction methods and a tree generation algorithm for the steiner network problem
• Reducing the hierarchical network design problem
• Reduction tests for the steiner problem in grapsh
• Some generalizations of the steiner problem in graphs
• Steiner problem in networks: A survey
• Steiner's problem in graphs and its implications

Cited in

(18)

• Reducing the hierarchical network design problem
• The multi-weighted Steiner tree problem
• The role of Steiner hulls in the solution to Steiner tree problems
• Two new criteria for finding Steiner hulls in Steiner tree problems
• Steiner's problem in graphs: Heuristic methods
• The dynamic predicate stashing copy problem and the Steiner problem in graphs
• Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm
• Reduction tests for the prize-collecting Steiner problem
• scientific article; zbMATH DE number 4139520 (Why is no real title available?)
• Reduction tests for the steiner problem in grapsh
• A test problem generator for the Steiner problem in graphs
• scientific article; zbMATH DE number 1163709 (Why is no real title available?)
• The edge-disjoing steiner problem in graphs
• Implications, conflicts, and reductions for Steiner trees
• Implications, conflicts, and reductions for Steiner trees
• An extended formulation with valid inequalities for the capacitated Steiner arborescence problem
• Minimum deviation and balanced optimization: A unified approach
• On reductions for the Steiner problem in graphs

This page was built for publication: An edge elimination test for the Steiner problem in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1116902)