ISSN:
1436-4646
Keywords:
Steiner tree
;
Polyhedron
;
Facets
;
Projection
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract In this paper we give some integer programming formulations for the Steiner tree problem on undirected and directed graphs and study the associated polyhedra. We give some families of facets for the undirected case along with some compositions and extensions. We also give a projection that relates the Steiner tree polyhedron on an undirected graph to the polyhedron for the corresponding directed graph. This is used to show that the LP-relaxation of the directed formulation is superior to the LP-relaxation of the undirected one.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01582573
Permalink