Dynamic Steiner Tree Problem

DOI10.1137/0404033MaRDI QIDQ3977293zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(77)

• On the competitive ratio for online facility location
• Parameterized analysis of the online priority and node-weighted Steiner tree problems
• On-line generalized Steiner problem
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings
• When ignorance helps: graphical multicast cost sharing games
• Competitive distributed file allocation.
• Tight bounds for online weighted tree augmentation
• Spider covering algorithms for network design problems
• The power of recourse for online MST and TSP
• Tight bounds for online weighted tree augmentation
• The Push Tree problem
• scientific article; zbMATH DE number 7758339 (Why is no real title available?)
• AN OPTIMAL REBUILDING STRATEGY FOR AN INCREMENTAL TREE PROBLEM
• THE EFFECT OF ASYMMETRY ON THE ON-LINE MULTICAST ROUTING PROBLEM
• Fully dynamic algorithms for Euclidean Steiner tree
• Stable and dynamic minimum cuts
• Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors
• A survey of combinatorial optimization problems in multicast routing
• Bayesian ignorance
• Average competitive ratios of on-line spanning trees
• Hallucination helps: energy efficient virtual circuit routing
• Online constrained forest and prize-collecting network design
• Oblivious buy-at-bulk in planar graphs
• Greedy algorithms for the on-line steiner tree and generalized steiner problems
• Online Buy-at-Bulk Network Design
• scientific article; zbMATH DE number 7651143 (Why is no real title available?)
• An Optimal Rebuilding Strategy for a Decremental Tree Problem
• The power of deferral: maintaining a constant-competitive Steiner tree online
• Non-greedy online Steiner trees on outerplanar graphs
• A fast distributed approximation algorithm for minimum spanning trees
• An \(O(\log n)\)-competitive algorithm for online constrained forest problems
• Thresholded covering algorithms for robust and max-min optimization
• Effective multicasting algorithm for dynamic membership with delay constraint
• Greedy algorithms for online survivable network design
• 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
• Volume in general metric spaces
• Online knapsack with removal and recourse
• Online Priority Steiner Tree Problems
• The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems
• Simultaneously load balancing for every \(p\)-norm, with reassignments
• Pushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy cases
• On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\)
• Lower Bounds for Insertion Methods for TSP
• Constructing competitive tours from local information
• Combinatorial optimization in system configuration design
• On the convergence of multicast games in directed networks
• Online load balancing with general reassignment cost
• Non-greedy online Steiner trees on outerplanar graphs
• Not all insertion methods yield constant approximate tours in the Euclidean plane
• Online network design with outliers
• Minimization of multicast traffic and ensuring its fault tolerance in software-defined networks
• On-line Steiner trees in the Euclidean plane
• Online Spanners in Metric Spaces
• Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem
• An average case analysis of a greedy algorithm for the on-line Steiner tree problem
• Group parking permit problems
• The bursty Steiner tree problem
• Heuristics for the Steiner problem in graphs
• A local-search algorithm for Steiner forest
• Concurrent multicast in weighted networks
• Concurrent multicast in weighted networks
• From cost sharing mechanisms to online selection problems
• 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
• Swap-vertex based neighborhood for Steiner tree problems
• Constructing competitive tours from local information
• Growing Half-Balls: Minimizing Storage and Communication Costs in Content Delivery Networks
• Equilibria in online games
• New results for online page replication
• The dynamic predicate stashing copy problem and the Steiner problem in graphs
• \(1\)-line minimum rectilinear Steiner trees and related problems
• A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms
• Optimal lower bounds for universal and differentially private Steiner trees and TSPs
• A super-stabilizing \(\log(n)\)-approximation algorithm for dynamic Steiner trees
• Designing networks with good equilibria under uncertainty

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)