No label defined (Q4945800)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1424551
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1424551 |
Statements
23 March 2000
0 references
Steiner type
0 references
branch-and-cut
0 references
preprocessing
0 references
integer programming
0 references
0.8111203908920288
0 references
0.8108587265014648
0 references
0.8029385209083557
0 references
0.8006771206855774
0 references
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].
0 references