Dynamic Steiner Tree Problem

DOI10.1137/0404033zbMath0739.05030OpenAlexW2029437526MaRDI QIDQ3977293

Publication date: 25 June 1992

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://openscholarship.wustl.edu/cgi/viewcontent.cgi?article=1725&context=cse_research

zbMATH Keywords

Steiner tree problem communication networks polynomial time algorithm multipoint routing worst- case performance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Network design and communication in computer systems (68M10)

Related Items (73)

Constructing competitive tours from local information ⋮ Constructing competitive tours from local information ⋮ Average competitive ratios of on-line spanning trees ⋮ Tight bounds for online weighted tree augmentation ⋮ New results for online page replication ⋮ On-line generalized Steiner problem ⋮ From Cost Sharing Mechanisms to Online Selection Problems ⋮ Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors ⋮ Simultaneously load balancing for every p-norm, with reassignments ⋮ When ignorance helps: graphical multicast cost sharing games ⋮ On the convergence of multicast games in directed networks ⋮ Greedy algorithms for the on-line steiner tree and generalized steiner problems ⋮ Online Priority Steiner Tree Problems ⋮ The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online ⋮ A survey of combinatorial optimization problems in multicast routing ⋮ Online network design with outliers ⋮ Online load balancing with general reassignment cost ⋮ Pushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy cases ⋮ Non-greedy online Steiner trees on outerplanar graphs ⋮ An average case analysis of a greedy algorithm for the on-line Steiner tree problem ⋮ Online Buy-at-Bulk Network Design ⋮ Growing Half-Balls: Minimizing Storage and Communication Costs in Content Delivery Networks ⋮ A super-stabilizing \(\log(n)\)-approximation algorithm for dynamic Steiner trees ⋮ Lower Bounds for Insertion Methods for TSP ⋮ Group parking permit problems ⋮ The Performance of greedy algorithms for the on-line steiner tree and related problems ⋮ Thresholded covering algorithms for robust and max-min optimization ⋮ Timing matters: online dynamics in broadcast games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Online knapsack with removal and recourse ⋮ Swap-vertex based neighborhood for Steiner tree problems ⋮ Online Spanners in Metric Spaces ⋮ Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem ⋮ Approximation algorithms for priority Steiner tree problems ⋮ Non-greedy Online Steiner Trees on Outerplanar Graphs ⋮ A fast distributed approximation algorithm for minimum spanning trees ⋮ Unnamed Item ⋮ Volume in general metric spaces ⋮ Competitive distributed file allocation. ⋮ A Near-Tight Bound for the Online Steiner Tree Problem in Graphs of Bounded Asymmetry ⋮ A Local-Search Algorithm for Steiner Forest ⋮ A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms ⋮ The Bursty Steiner Tree Problem ⋮ An O(logn)-Competitive Algorithm for Online Constrained Forest Problems ⋮ On the competitive ratio for online facility location ⋮ Concurrent multicast in weighted networks ⋮ On-line Steiner trees in the Euclidean plane ⋮ Heuristics for the Steiner problem in graphs ⋮ THE EFFECT OF ASYMMETRY ON THE ON-LINE MULTICAST ROUTING PROBLEM ⋮ Online constrained forest and prize-collecting network design ⋮ Online Node-weighted Steiner Forest and Extensions via Disk Paintings ⋮ Concurrent multicast in weighted networks ⋮ Bayesian ignorance ⋮ Effective multicasting algorithm for dynamic membership with delay constraint ⋮ Spider Covering Algorithms for Network Design Problems ⋮ Equilibria in Online Games ⋮ A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem ⋮ Minimization of multicast traffic and ensuring its fault tolerance in software-defined networks ⋮ The Power of Recourse for Online MST and TSP ⋮ On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\) ⋮ Hallucination Helps: Energy Efficient Virtual Circuit Routing ⋮ Relaxing the irrevocability requirement for online graph algorithms ⋮ Oblivious Buy-at-Bulk in Planar Graphs ⋮ Designing Networks with Good Equilibria under Uncertainty ⋮ Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs ⋮ AN OPTIMAL REBUILDING STRATEGY FOR AN INCREMENTAL TREE PROBLEM ⋮ Tight Bounds for Online Weighted Tree Augmentation ⋮ Combinatorial optimization in system configuration design ⋮ Parameterized analysis of the online priority and node-weighted Steiner tree problems ⋮ \(1\)-line minimum rectilinear Steiner trees and related problems ⋮ The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems ⋮ Not all insertion methods yield constant approximate tours in the Euclidean plane

This page was built for publication: Dynamic Steiner Tree Problem