scientific article; zbMATH DE number 1424551
The Steiner Problem in Graphs (SPG) is well-known to be NP hard. In order to tackle it with branch-and-bound or branch-and-cut methods it is therefore of vital importance to find good formulations by applying a set of preprocessing rules. In this paper the author describes the idea of preprocessing, in general and then with emphasis on the SPG. Four different ideas for preprocessing concepts are developed which improve upon preprocessing used for SPG so far. Further improvements can be obtained for each by exploiting vertex implied Steiner edges. The power of the theoretical results is confirmed by numerical tests which are reported at the end of the paper. For the entire collection see [Zbl 0932.00010].
- Thinning out Steiner trees: a node-based model for uniform edge costs
- scientific article; zbMATH DE number 4164200 (Why is no real title available?)
- Automated knowledge source selection and service composition
- Preprocessing Steiner problems from VLSI layout
- The edge-disjoing steiner problem in graphs
- Implications, conflicts, and reductions for Steiner trees
- Implications, conflicts, and reductions for Steiner trees
- Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View
- Solving Steiner trees: Recent advances, challenges, and perspectives
- An optimal algorithm for the stacker crane problem on fixed topologies
- On reductions for the Steiner problem in graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4945800)