A comparison of Steiner tree relaxations

DOI10.1016/S0166-218X(00)00318-8zbMath0984.90051MaRDI QIDQ5946825

Tobias Polzin, Siavash Vahdati Daneshmand

Publication date: 27 February 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

flow-class relaxation; linear programming relaxations; Steiner problem in networks; Steiner tree relaxations; tree-class relaxation

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C05: Trees

Related Items

Steiner trees and polyhedra, Improved algorithms for the Steiner problem in networks, On Steiner trees and minimum spanning trees in hypergraphs, Approaches to the Steiner Problem in Networks

Uses Software

• SteinLib

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Survivable networks, linear programming relaxations and the parsimonious property
• The Steiner tree problem
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• The Steiner tree problem. II: Properties and classes of facets
• Integer Programming Formulation of Traveling Salesman Problems
• A dual ascent approach for steiner tree problems on a directed graph
• Problem reduction methods and a tree generation algorithm for the steiner network problem
• An SST-based algorithm for the steiner problem in graphs
• An integer linear programming approach to the steiner problem in graphs
• A catalog of steiner tree formulations
• Matroids and the greedy algorithm
• Improved algorithms for the Steiner problem in networks