Solving Steiner trees: Recent advances, challenges, and perspectives

DOI10.1002/net.22005OpenAlexW3106892521MaRDI QIDQ6087073

Ivana Ljubić

Publication date: 11 December 2023

Published in: Networks (Search for Journal in Brave)

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

zbMATH Keywords

heuristicsinteger programmingcombinatorial optimizationSteiner tree problemexact methods

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (2)

Optimal connected subgraphs: Integer programming formulations and polyhedra ⋮ Approximation algorithms for solving the line-capacitated minimum Steiner tree problem

Cites Work

• Steiner problem in networks: A survey
• An SST-based algorithm for the steiner problem in graphs
• Send-and-Split Method for Minimum-Concave-Cost Network Flows
• Reduction tests for the steiner problem in grapsh
• The prize collecting traveling salesman problem
• An integer linear programming approach to the steiner problem in graphs
• Solving the Steiner Tree Problem on a Graph Using Branch and Cut
• A tabu search heuristic for the Steiner Tree Problem
• Weighted k‐cardinality trees: Complexity and polyhedral structure
• Euclidean Steiner minimum trees: An improved exact algorithm
• Efficient path and vertex exchange in steiner tree algorithms
• A strong lower bound for the Node Weighted Steiner Tree Problem
• A branch and cut algorithm for the Steiner problem in graphs
• The maximum-leaf spanning tree problem: Formulations and facets
• A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
• Solving Steiner tree problems in graphs to optimality
• Restricted swap-based neighborhood search for the minimum connected dominating set problem
• 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
• An inexact sample average approximation approach for the stochastic connected facility location problem
• Algorithms for node‐weighted Steiner tree and maximum‐weight connected subgraph
• Preprocessing Steiner problems from VLSI layout
• A General Approximation Technique for Constrained Forest Problems
• Computing near‐optimal solutions to the steiner problem in a graph using a genetic algorithm
• Reductions for the rectilinear steiner tree problem
• The Rooted Maximum Node-Weight Connected Subgraph Problem
• Approximation Algorithms for Directed Steiner Problems
• A Heuristic Method for the Set Covering Problem
• Reducibility among Combinatorial Problems
• A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems
• Imposing Connectivity Constraints in Forest Planning Models
• A distributed dual ascent algorithm for Steiner problems in multicast routing
• Directed Steiner Tree Problem On A Graph: Models, Relaxations And Algorithms
• Fast Local Search for Steiner Trees in Graphs
• The Maximum Weight Connected Subgraph Problem
• A catalog of steiner tree formulations
• Solving the Graphical Steiner Tree Problem Using Genetic Algorithms
• Practical Partitioning-Based Methods for the Steiner Problem
• Tighter Bounds for Graph Steiner Tree Approximation
• Steiner Tree Approximation via Iterative Randomized Rounding
• Obtaining optimal k -cardinality trees fast
• Fast local search for the steiner problem in graphs
• Matroids and integrality gaps for hypergraphic steiner tree relaxations
• A graph theory approach for designing conservation reserve networks with minimal fragmentation
• Steiner's problem in graphs and its implications
• The steiner problem in graphs
• Computational Science - ICCS 2004
• A lower bound for the steiner tree problem in directed graphs
• Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs
• An algorithm for the steiner problem in graphs
• Algorithms - ESA 2003
• A faster approximation algorithm for the Steiner problem in graphs
• A note on distributed multicast routing in point-to-point networks
• Steiner trees and polyhedra
• A comparison of Steiner tree relaxations
• Improved algorithms for the Steiner problem in networks
• Sharing the cost of multicast transmissions
• Steiner tree problems
• Steiner Tree Problems With Profits
• Stronger path‐based extended formulation for the Steiner tree problem
• A linear programming based approach to the Steiner tree problem with a fixed number of terminals
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximate robust optimization for the connected facility location problem
• Hop constrained Steiner trees with multiple root nodes
• Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem
• ILP heuristics and a new exact method for bi-objective 0/1 ILPs: application to fttx-network design
• On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree
• Wildlife corridors as a connected subgraph problem
• A partition-based relaxation for Steiner trees
• A note on the prize collecting traveling salesman problem
• MIP models for connected facility location: a theoretical and computational study
• Lagrangian decompositions for the two-level FTTx network design problem
• Non delayed relax-and-cut algorithms
• Computational methods in systems biology. 7th international conference, CMSB 2009, Bologna, Italy, August 31--September 1, 2009. Proceedings
• An exact algorithm for the node weighted Steiner tree problem
• The Steiner tree problem on graphs: inapproximability results
• Reformulations and solution algorithms for the maximum leaf spanning tree problem
• A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs
• The Steiner problem with edge lengths 1 and 2
• A constrained Steiner tree problem
• Facets of two Steiner arborescence polyhedra
• Steiner's problem in graphs: Heuristic methods
• The Steiner tree problem
• Minimal spanning trees with a constraint on the number of leaves
• The Steiner tree polytope and related polyhedra
• Tree polytope on 2-trees
• Arborescence polytopes for series-parallel graphs
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• The Steiner tree problem. II: Properties and classes of facets
• New approximation algorithms for the Steiner tree problems
• Rectilinear group Steiner trees and applications in VLSI design
• Solving Steiner tree problems in graphs with Lagrangian relaxation
• Solving group Steiner problems as Steiner problems.
• Local branching
• Layered graph approaches for combinatorial optimization problems
• The \(p\)-arborescence star problem: formulations and exact solution approaches
• A robust and scalable algorithm for the Steiner problem in graphs
• A relax-and-cut framework for large-scale maximum weight connected subgraph problems
• The connected facility location polytope
• A node-based layered graph approach for the Steiner tree problem with revenues, budget and hop-constraints
• 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
• Swap-vertex based neighborhood for Steiner tree problems
• The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study
• Decomposition methods for the two-stage stochastic Steiner tree problem
• An algorithmic framework for the exact solution of tree-star problems
• A faster approximation algorithm for the Steiner tree problem in graphs
• Parallel local search for Steiner trees in graphs
• On Steiner trees and minimum spanning trees in hypergraphs
• Improved Steiner tree algorithms for bounded treewidth
• Faster algorithm for optimum Steiner trees
• A note on the generalized Steiner tree polytope
• Advances in Steiner trees
• Insight into the computation of Steiner minimal trees in Euclidean space of general dimension
• On the history of the Euclidean Steiner tree problem
• Enhanced formulations and branch-and-cut for the two level network design problem with transition facilities
• A MIP-based approach to solve the prize-collecting local access network design problem
• A distributed dual ascent algorithm for the Hop-constrained Steiner tree problem
• The incremental connected facility location problem
• Optimal interconnection trees in the plane. Theory, algorithms and applications
• Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Exact approaches for solving robust prize-collecting Steiner tree problems
• An 11/6-approximation algorithm for the network Steiner problem
• A survey of combinatorial optimization problems in multicast routing
• A cutting plane algorithm for the capacitated connected facility location problem
• The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches
• Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem
• Dynamic programming for minimum Steiner trees
• Reduction tests for the prize-collecting Steiner problem
• The multi-weighted Steiner tree problem: A reformulation by intersection
• Worst-case performance of Wong's Steiner tree heuristic
• A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem
• Towards optimizing the deployment of optical access networks
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• Locating leak detecting sensors in a water distribution network by solving prize-collecting Steiner arborescence problems
• A Hybrid GRASP with Perturbations for the Steiner Problem in Graphs
• Dual-Based Local Search for the Connected Facility Location and Related Problems
• Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem
• Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
• The regenerator location problem
• Contraction-Based Steiner Tree Approximations in Practice
• Reduction techniques for the prize collecting Steiner tree problem and the maximum-weight connected subgraph problem
• A dual ascent approach for steiner tree problems on a directed graph
• Optimal Selection of a Connected Reserve Network
• The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
• An approach for solving singular two point boundary value problems: analytical and numerical treatment
• The Influence of Preprocessing on Steiner Tree Approximations
• Fourier meets M\"{o}bius: fast subset convolution
• Hypergraphic LP Relaxations for Steiner Trees
• Solving Connected Subgraph Problems in Wildlife Conservation
• Polylogarithmic inapproximability
• Connections in Networks: Hardness of Feasibility Versus Optimality
• Approaches to the Steiner Problem in Networks
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
• Some generalizations of the steiner problem in graphs
• The node-weighted steiner tree problem

This page was built for publication: Solving Steiner trees: Recent advances, challenges, and perspectives