Facets of two Steiner arborescence polyhedra
From MaRDI portal
Publication:1181904
DOI10.1007/BF01586946zbMath0744.90090MaRDI QIDQ1181904
Publication date: 27 June 1992
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
NP-hardfacet-inducing inequalitiesfacial structure of two polyhedralifting and composition of facetsSteiner arborescenceSteiner directed tree problemSteiner polyhedra
Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)
Related Items
Optimal relay node placement in delay constrained wireless sensor network design, Locating leak detecting sensors in a water distribution network by solving prize-collecting Steiner arborescence problems, A branch-and-cut algorithm for the connected max-\(k\)-cut problem, Heuristic and exact algorithms for minimum-weight non-spanning arborescences, Solving Steiner trees: Recent advances, challenges, and perspectives, Algorithmic expedients for the prize collecting Steiner tree problem, A note on the generalized Steiner tree polytope, A fast prize-collecting Steiner forest algorithm for functional analyses in biological networks, Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints, The regenerator location problem, An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
- The Steiner tree problem. II: Properties and classes of facets
- The node-weighted steiner tree problem
- Steiner problem in networks: A survey
- Facets of the Asymmetric Traveling Salesman Polytope
- The Fixed-Outdegree 1-Arborescence Polytope
- Optimum branchings
- A lower bound for the steiner tree problem in directed graphs
