Steiner tree problems

DOI10.1002/net.3230220105zbMath0749.90082OpenAlexW2042492403MaRDI QIDQ5966604

Publication date: 28 June 1992

Published in: Networks (Search for Journal in Brave)

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

zbMATH Keywords

survey Steiner tree problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Related Items (69)

Finding outbreak trees in networks with limited information ⋮ Population-driven urban road evolution dynamic model ⋮ The Steiner cycle polytope ⋮ A primal-dual approximation algorithm for the Steiner forest problem ⋮ On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane \(\mathbb{R}^2\) ⋮ Optimal capacitated ring trees ⋮ Routing algorithm for multicast under multi-tree model in optical networks ⋮ Reoptimization of Steiner trees: changing the terminal set ⋮ Optimal Competitiveness for the Rectilinear Steiner Arborescence Problem ⋮ Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors ⋮ On the Steiner ratio in 3-space ⋮ Steiner minimal trees on regular polygons with centre ⋮ Cut and patch Steiner trees for ladders ⋮ A survey of combinatorial optimization problems in multicast routing ⋮ Looking for edge-equitable spanning trees ⋮ On the set of extreme core allocations for minimal cost spanning tree problems ⋮ A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems ⋮ A heuristic for the Steiner problem in graphs ⋮ Growing Half-Balls: Minimizing Storage and Communication Costs in Content Delivery Networks ⋮ Approximation algorithms for tree alignment with a given phylogeny ⋮ A factoring approach for the Steiner tree problem in undirected networks ⋮ The Steiner tree problem in orientation metrics ⋮ Multicast routing under quality of service constraints for vehicular ad hoc networks: mathematical formulation and a relax‐and‐fix heuristic ⋮ An integer programming formulation of the Steiner problem in graphs ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs ⋮ A node-based layered graph approach for the Steiner tree problem with revenues, budget and hop-constraints ⋮ The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches ⋮ Structural properties of minimum multi-source multi-sink Steiner networks in the Euclidean plane ⋮ New formulations of the hop-constrained minimum spanning tree problem via Miller-Tucker-Zemlin constraints ⋮ Robust optimization for minimizing energy consumption of multicast transmissions in coded wireless packet networks under distance uncertainty ⋮ Steiner problems on directed acyclic graphs ⋮ Approximations for two variants of the Steiner tree problem in the Euclidean plane \(\mathbb R^2\) ⋮ SoMR: a scalable distributed QoS multicast routing protocol ⋮ Tree network design avoiding congestion ⋮ Minimum cost spanning tree problems with indifferent agents ⋮ A note on the generalized Steiner tree polytope ⋮ Unnamed Item ⋮ Steiner minimal trees for three points with one convex polygonal obstacle ⋮ Optimal design of virtual links in AFDX networks ⋮ A Lagrangean-based decomposition approach for the link constrained Steiner tree problem ⋮ On the parameterized complexity of finding separators with non-hereditary properties ⋮ The Steiner tree problem with delays: a compact formulation and reduction procedures ⋮ The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study ⋮ A heuristic for Euclidean and rectilinear Steiner problems ⋮ Heuristics for the Steiner problem in graphs ⋮ Two variations of the minimum Steiner problem ⋮ A note on distributed multicast routing in point-to-point networks ⋮ A branch-and-price algorithm for the Steiner tree packing problem. ⋮ Approximations for Steiner trees with minimum number of Steiner points ⋮ Effective multicasting algorithm for dynamic membership with delay constraint ⋮ Heuristic algorithms for packing of multiple-group multicasting ⋮ Minimization of multicast traffic and ensuring its fault tolerance in software-defined networks ⋮ Towards optimizing the deployment of optical access networks ⋮ On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\) ⋮ Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem ⋮ An Algorithm to Find the Link Constrained Steiner Tree in Undirected Graphs ⋮ A fast and simple Steiner routing heuristic ⋮ Constrained Steiner trees in Halin graphs ⋮ On shortest three-edge-connected Steiner networks with Euclidean distance ⋮ Fixed topology Steiner trees and spanning forests ⋮ How to Infer Ancestral Genome Features by Parsimony: Dynamic Programming over an Evolutionary Tree ⋮ Rectilinear paths among rectilinear obstacles ⋮ \(1\)-line minimum rectilinear Steiner trees and related problems ⋮ Approximation algorithms for solving the line-capacitated minimum Steiner tree problem ⋮ Worst-case performance of some heuristics for Steiner's problem in directed graphs ⋮ Euclidean Steiner minimal trees with obstacles and Steiner visibility graphs ⋮ A neural network for the Steiner minimal tree problem ⋮ Non delayed relax-and-cut algorithms

Cites Work

This page was built for publication: Steiner tree problems