ISSN:
1436-4646
Schlagwort(e):
Steiner trees
;
arborescences
;
polyhedral theory
;
facets
;
lifting and composition of facets
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
Abstract The Steiner arborescence (or Steiner directed tree) problem concerns the connection of a set of target vertices of a digraph to a given root vertex. This problem is known to be NP-hard. In the present paper we study the facial structure of two polyhedra associated with the problem. Several classes of valid inequalities are considered, and a new class with arbitrarily large coefficients is introduced. All these inequalities are shown to define distinct facets of both the Steiner polyhedra considered. This is achieved by exploiting two lifting theorems which also allow generalization of the new inequalities. Composition theorems are finally given and used to derive large families of new facet-inducing inequalities with exponentially large coefficients.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01586946
Permalink
