Dynamic Steiner Tree Problem
From MaRDI portal
Publication:3977293
DOI10.1137/0404033zbMath0739.05030OpenAlexW2029437526MaRDI QIDQ3977293
Makoto Imase, Bernard M. Waxman
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
Steiner tree problemcommunication networkspolynomial time algorithmmultipoint routingworst- case performance
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
