Approximation algorithms for Steiner forest: An experimental study

DOI10.1002/net.22046zbMath1528.90267OpenAlexW3163365238MaRDI QIDQ6065858

Daniel Grosu, Laleh Ghalami

Publication date: 11 December 2023

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.22046

zbMATH Keywords

performance evaluationapproximation algorithmsSteiner forest

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Signed and weighted graphs (05C22) Mathematical modeling or simulation for problems pertaining to operations research and mathematical programming (90-10)

Cites Work

• Unnamed Item
• Unnamed Item
• The Steiner tree problem on graphs: inapproximability results
• The Steiner problem with edge lengths 1 and 2
• Quadratic \(0/1\) optimization and a decomposition approach for the placement of electronic circuits
• On approximating planar metrics by tree metrics.
• The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study
• Approximation of Steiner forest via the bidirected cut relaxation
• Greedy Algorithms for Steiner Forest
• The Design of Approximation Algorithms
• Designing Network Protocols for Good Equilibria
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game
• An integer linear programming approach to the steiner problem in graphs
• Solving the Steiner Tree Problem on a Graph Using Branch and Cut
• Strong Steiner Tree Approximations in Practice
• Strong formulations for network design problems with connectivity requirements
• A General Approximation Technique for Constrained Forest Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• A Local-Search Algorithm for Steiner Forest
• Reducibility among Combinatorial Problems
• Fast Local Search for Steiner Trees in Graphs
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• Dealing with large hidden constants
• On Steiner’s Problem with Rectilinear Distance
• An algorithm for the steiner problem in graphs
• A tight bound on approximating arbitrary metrics by tree metrics
• Improved algorithms for the Steiner problem in networks

This page was built for publication: Approximation algorithms for Steiner forest: An experimental study