Improving linear programming approaches for the Steiner tree problem

DOI10.1007/3-540-44867-5_1MaRDI QIDQ4426341zbMATH OpenFDO

Authors Ernst Althaus, Tobias Polzin, Siavash Vahdati Daneshmand

Publication date 16 September 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2647/26470001.htm, http://hdl.handle.net/11858/00-001M-0000-0014-6BB9-F

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Linear programming (90C05) Combinatorial optimization (90C27)

Recommendations

• Solving Steiner tree problems in graphs to optimality
• Improved algorithms for the Steiner problem in networks
• Using multiflow formulations to solve the Steiner tree problem in graphs
• Implications, conflicts, and reductions for Steiner trees
• An improved LP-based approximation for Steiner tree

Cited in

(11)

• Local cuts revisited
• A branch-and-cut algorithm for the Steiner tree problem with delays
• Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday)
• Local cuts for mixed-integer programming
• Approaches to the Steiner Problem in Networks
• Transformations for the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to sap
• Solving the quorumcast routing problem by constraint programming
• The Steiner tree problem with delays: a compact formulation and reduction procedures
• A new Integer Linear Program for the Steiner Tree Problem with Revenues, Budget and Hop Constraints
• Linear Programming Hierarchies Suffice for Directed Steiner Tree
• Implications, conflicts, and reductions for Steiner trees

Describes a project that uses

Uses Software

• GeoSteiner
• TSPLIB

This page was built for publication: Improving linear programming approaches for the Steiner tree problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4426341)