Steiner trees and polyhedra (Q5946818)
From MaRDI portal
scientific article; zbMATH DE number 1660375
Language | Label | Description | Also known as |
---|---|---|---|
English | Steiner trees and polyhedra |
scientific article; zbMATH DE number 1660375 |
Statements
Steiner trees and polyhedra (English)
0 references
30 July 2002
0 references
The authors introduce a new class of valid inequalities of the Steiner tree polytope (STP) and give sufficient conditions for these inequalities to define facets. They present a counterexample to a conjecture of \textit{S. Chopra} and \textit{M. R. Rao} [Math. Programming 64, 209-229 and 231-246 (1994; Zbl 0821.90124 and Zbl 0831.90115)] and describe the dominant of the STP and the Steiner connected subgraph polytope on special classes of graphs (in particular, series--parallel graphs).
0 references
graph
0 references
network
0 references
Steiner tree
0 references
Steiner connected subgraph
0 references
polytope
0 references
facet
0 references
series-parallel graph
0 references
0 references