A linear programming based approach to the Steiner tree problem with a fixed number of terminals

DOI10.1002/net.21913arXiv1812.02237OpenAlexW2980261836WikidataQ127124378 ScholiaQ127124378MaRDI QIDQ6068538

Nemhauser, George I., Unnamed Author, Shabbir Ahmed

Publication date: 13 November 2023

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1812.02237

zbMATH Keywords

linear programminginteger programmingconvex hullSteiner treelaminar familyindependent subproblems

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Related Items

Maximum weighted induced forests and trees: new formulations and a computational comparative review, Solving Steiner trees: Recent advances, challenges, and perspectives, Mixed integer programming formulations for Steiner tree and quality of service multicast tree problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree
• A practical greedy approximation for the directed Steiner tree problem
• A partition-based relaxation for Steiner trees
• The Steiner tree problem on graphs: inapproximability results
• The Steiner problem with edge lengths 1 and 2
• Polynomially solvable special cases of the Steiner problem in planar networks
• Disjunctive programming: Properties of the convex hull of feasible points
• The Steiner tree polytope and related polyhedra
• Geometry of the space of phylogenetic trees
• Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm
• Swap-vertex based neighborhood for Steiner tree problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On Steiner trees and minimum spanning trees in hypergraphs
• Integer Programming
• A dual ascent approach for steiner tree problems on a directed graph
• Polyhedral Characterization of Discrete Dynamic Programming
• Hypergraphic LP Relaxations for Steiner Trees
• Thek-Steiner Ratio in Graphs
• Efficient path and vertex exchange in steiner tree algorithms
• Solving Steiner tree problems in graphs to optimality
• Reducibility among Combinatorial Problems
• A catalog of steiner tree formulations
• Steiner Tree Approximation via Iterative Randomized Rounding
• Matroids and integrality gaps for hypergraphic steiner tree relaxations
• Optimum branchings
• The steiner problem in graphs
• A comparison of Steiner tree relaxations
• Improved algorithms for the Steiner problem in networks