On-line Steiner trees in the Euclidean plane

DOI10.1007/BF02573969zbMath0774.68088MaRDI QIDQ685176

Yossi Azar, Noga Alon

Publication date: 30 September 1993

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131265

zbMATH Keywords

competitive ratiolower boundon-line algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Constructing competitive tours from local information, New results for online page replication, On-line generalized Steiner problem, Optimal Competitiveness for the Rectilinear Steiner Arborescence Problem, Online Priority Steiner Tree Problems, The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online, A degree based approach to find Steiner trees, Non-greedy online Steiner trees on outerplanar graphs, Growing Half-Balls: Minimizing Storage and Communication Costs in Content Delivery Networks, The repeater tree construction problem, Lower Bounds for Insertion Methods for TSP, The Performance of greedy algorithms for the on-line steiner tree and related problems, Online Spanners in Metric Spaces, Non-greedy Online Steiner Trees on Outerplanar Graphs, A Near-Tight Bound for the Online Steiner Tree Problem in Graphs of Bounded Asymmetry, The Power of Recourse for Online MST and TSP, Designing Networks with Good Equilibria under Uncertainty, Parameterized analysis of the online priority and node-weighted Steiner tree problems

Cites Work

• Unnamed Item
• A geometric problem involving the nearest neighbour algorithm
• A problem seminar
• A travelling salesman problem in the \(k\)-dimensional unit cube
• Steiner problem in networks: A survey
• Dynamic Steiner Tree Problem
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Constructing Reliable Communication Networks of Small Weight Online