On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree
Open Access
- 18 February 2016
- journal article
- research article
- Published by Springer Nature in Mathematical Programming
- Vol. 160 (1-2) , 379-406
Abstract
No abstract availableKeywords
Funding Information
- NWO Veni Grant
- Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada
This publication has 25 references indexed in Scilit:
- Steiner Tree Approximation via Iterative Randomized RoundingJournal of the ACM, 2013
- Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper boundOperations Research Letters, 2010
- On Steiner trees and minimum spanning trees in hypergraphsOperations Research Letters, 2003
- A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3Journal of Algorithms, 2000
- An 11/6-approximation algorithm for the network steiner problemAlgorithmica, 1993
- A catalog of steiner tree formulationsNetworks, 1993
- Steiner tree problemsNetworks, 1992
- A faster approximation algorithm for the Steiner problem in graphsInformation Processing Letters, 1988
- Applying Parallel Computation Algorithms in the Design of Serial AlgorithmsJournal of the ACM, 1983
- Steiner Minimal TreesSIAM Journal on Applied Mathematics, 1968