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




Related Items (73)

Constructing competitive tours from local informationConstructing competitive tours from local informationAverage competitive ratios of on-line spanning treesTight bounds for online weighted tree augmentationNew results for online page replicationOn-line generalized Steiner problemFrom Cost Sharing Mechanisms to Online Selection ProblemsRectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighborsSimultaneously load balancing for every p-norm, with reassignmentsWhen ignorance helps: graphical multicast cost sharing gamesOn the convergence of multicast games in directed networksGreedy algorithms for the on-line steiner tree and generalized steiner problemsOnline Priority Steiner Tree ProblemsThe Power of Deferral: Maintaining a Constant-Competitive Steiner Tree OnlineA survey of combinatorial optimization problems in multicast routingOnline network design with outliersOnline load balancing with general reassignment costPushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy casesNon-greedy online Steiner trees on outerplanar graphsAn average case analysis of a greedy algorithm for the on-line Steiner tree problemOnline Buy-at-Bulk Network DesignGrowing Half-Balls: Minimizing Storage and Communication Costs in Content Delivery NetworksA super-stabilizing \(\log(n)\)-approximation algorithm for dynamic Steiner treesLower Bounds for Insertion Methods for TSPGroup parking permit problemsThe Performance of greedy algorithms for the on-line steiner tree and related problemsThresholded covering algorithms for robust and max-min optimizationTiming matters: online dynamics in broadcast gamesUnnamed ItemUnnamed ItemOnline knapsack with removal and recourseSwap-vertex based neighborhood for Steiner tree problemsOnline Spanners in Metric SpacesStable Approximation Algorithms for the Dynamic Broadcast Range-Assignment ProblemApproximation algorithms for priority Steiner tree problemsNon-greedy Online Steiner Trees on Outerplanar GraphsA fast distributed approximation algorithm for minimum spanning treesUnnamed ItemVolume in general metric spacesCompetitive distributed file allocation.A Near-Tight Bound for the Online Steiner Tree Problem in Graphs of Bounded AsymmetryA Local-Search Algorithm for Steiner ForestA simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithmsThe Bursty Steiner Tree ProblemAn O(logn)-Competitive Algorithm for Online Constrained Forest ProblemsOn the competitive ratio for online facility locationConcurrent multicast in weighted networksOn-line Steiner trees in the Euclidean planeHeuristics for the Steiner problem in graphsTHE EFFECT OF ASYMMETRY ON THE ON-LINE MULTICAST ROUTING PROBLEMOnline constrained forest and prize-collecting network designOnline Node-weighted Steiner Forest and Extensions via Disk PaintingsConcurrent multicast in weighted networksBayesian ignoranceEffective multicasting algorithm for dynamic membership with delay constraintSpider Covering Algorithms for Network Design ProblemsEquilibria in Online GamesA randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problemMinimization of multicast traffic and ensuring its fault tolerance in software-defined networksThe Power of Recourse for Online MST and TSPOn approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\)Hallucination Helps: Energy Efficient Virtual Circuit RoutingRelaxing the irrevocability requirement for online graph algorithmsOblivious Buy-at-Bulk in Planar GraphsDesigning Networks with Good Equilibria under UncertaintyOptimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPsAN OPTIMAL REBUILDING STRATEGY FOR AN INCREMENTAL TREE PROBLEMTight Bounds for Online Weighted Tree AugmentationCombinatorial optimization in system configuration designParameterized analysis of the online priority and node-weighted Steiner tree problems\(1\)-line minimum rectilinear Steiner trees and related problemsThe competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problemsNot all insertion methods yield constant approximate tours in the Euclidean plane




This page was built for publication: Dynamic Steiner Tree Problem