Dynamic Steiner Tree Problem

DOI10.1137/0404033zbMATH Open0739.05030OpenAlexW2029437526MaRDI QIDQ3977293FDOQ3977293

Authors: 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

Recommendations

• Dynamic programming for minimum Steiner trees
• Steiner tree problems
• Steiner tree problems
• The Steiner tree problem
• scientific article; zbMATH DE number 1182759
• The Steiner tree problem with hop constraints
• A constrained Steiner tree problem
• Diameter-constrained Steiner tree
• Solving Steiner tree problems in graphs to optimality

zbMATH Keywords

communication networksSteiner tree problempolynomial time algorithmmultipoint routingworst- case performance

Mathematics Subject Classification ID

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

Cited In (78)

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

This page was built for publication: Dynamic Steiner Tree Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3977293)