Facets of two Steiner arborescence polyhedra

DOI10.1007/BF01586946zbMath0744.90090MaRDI QIDQ1181904

Matteo Fischetti

Publication date: 27 June 1992

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

NP-hardfacet-inducing inequalitiesfacial structure of two polyhedralifting and composition of facetsSteiner arborescenceSteiner directed tree problemSteiner polyhedra

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Related Items (11)

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

This page was built for publication: Facets of two Steiner arborescence polyhedra