A robust and scalable algorithm for the Steiner problem in graphs

DOI10.1007/S12532-017-0123-4zbMath1390.05227arXiv1412.2787OpenAlexW2963552748MaRDI QIDQ1646683

Renato F. Werneck, Eduardo Uchoa, Thomas Pajor

Publication date: 25 June 2018

Published in: Mathematical Programming Computation (Search for Journal in Brave)

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

zbMATH Keywords

metaheuristicslocal searchSteiner treesdual ascent

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (11)

The Influence of Preprocessing on Steiner Tree Approximations ⋮ The rainbow Steiner tree problem ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ SCIP-Jack -- a solver for STP and variants with parallelization extensions ⋮ Swap-vertex based neighborhood for Steiner tree problems ⋮ Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem ⋮ Strong Steiner Tree Approximations in Practice ⋮ Decomposition methods for the two-stage stochastic Steiner tree problem ⋮ Implications, conflicts, and reductions for Steiner trees ⋮ Implications, conflicts, and reductions for Steiner trees ⋮ Integer programming formulations for the shared multicast tree problem

Uses Software

• Unnamed Item
• SteinLib
• CPLEX
• OR-Library
• GeoSteiner
• DIMACS
• SCIP-Jack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• SCIP: solving constraint integer programs
• Steiner's problem in graphs: Heuristic methods
• Rectilinear group Steiner trees and applications in VLSI design
• Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm
• Thinning out Steiner trees: a node-based model for uniform edge costs
• SCIP-Jack -- a solver for STP and variants with parallelization extensions
• The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study
• A hybrid heuristic for the \(p\)-median problem
• Measuring the impact of primal heuristics
• The pilot method: A strategy for heuristic repetition with application to the Steiner problem in graphs
• A Hybrid GRASP with Perturbations for the Steiner Problem in Graphs
• Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem
• A dual ascent approach for steiner tree problems on a directed graph
• Reduction tests for the steiner problem in grapsh
• A Comparison of Two Simulated Annealing Algorithms Applied to the Directed Steiner Problem on Networks
• Solving the Steiner Tree Problem on a Graph Using Branch and Cut
• On Finding and Updating Spanning Trees and Shortest Paths
• Efficient path and vertex exchange in steiner tree algorithms
• Solving Steiner tree problems in graphs to optimality
• Preprocessing Steiner problems from VLSI layout
• Reducibility among Combinatorial Problems
• Tighter Bounds for Graph Steiner Tree Approximation
• Steiner Tree Approximation via Iterative Randomized Rounding
• Fast local search for the steiner problem in graphs
• Matroids and integrality gaps for hypergraphic steiner tree relaxations
• Efficient Greedy Heuristics For Steiner Tree Problems Using Reolptimization And Super Modularity
• A faster approximation algorithm for the Steiner problem in graphs
• Improved algorithms for the Steiner problem in networks

This page was built for publication: A robust and scalable algorithm for the Steiner problem in graphs