On-line Steiner trees in the Euclidean plane

DOI10.1007/BF02573969zbMATH0774.68088MaRDI QIDQ685176FDOQ685176

Authors Noga Alon, Yossi Azar

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

lower boundcompetitive ratioon-line algorithms

Mathematics Subject Classification ID

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

Recommendations

• The Performance of greedy algorithms for the on-line steiner tree and related problems
• Average competitive ratios of on-line spanning trees
• The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems
• An average case analysis of a greedy algorithm for the on-line Steiner tree problem
• Greedy algorithms for the on-line steiner tree and generalized steiner problems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A geometric problem involving the nearest neighbour algorithm
• A problem seminar
• A travelling salesman problem in the \(k\)-dimensional unit cube
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Constructing Reliable Communication Networks of Small Weight Online
• Dynamic Steiner Tree Problem
• Steiner problem in networks: A survey

Cited in

(26)

• Lower Bounds for Insertion Methods for TSP
• On the competitiveness of the online asymmetric and Euclidean Steiner tree problems
• Non-greedy online Steiner trees on outerplanar graphs
• On-line generalized Steiner problem
• Average competitive ratios of on-line spanning trees
• Constructing Reliable Communication Networks of Small Weight Online
• Designing networks with good equilibria under uncertainty
• An average case analysis of a greedy algorithm for the on-line Steiner tree problem
• Growing Half-Balls: Minimizing Storage and Communication Costs in Content Delivery Networks
• Parameterized analysis of the online priority and node-weighted Steiner tree problems
• The power of deferral: maintaining a constant-competitive Steiner tree online
• The power of recourse for online MST and TSP
• A Near-Tight Bound for the Online Steiner Tree Problem in Graphs of Bounded Asymmetry
• Constructing competitive tours from local information
• New results for online page replication
• The power of deferral: maintaining a constant-competitive Steiner tree online
• Online Spanners in Metric Spaces
• The sequential sum problem and performance bounds on the greedy algorithm for the on‐line Steiner problem
• Online Priority Steiner Tree Problems
• A degree based approach to find Steiner trees
• Non-greedy online Steiner trees on outerplanar graphs
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings
• The repeater tree construction problem
• Optimal competitiveness for the rectilinear Steiner arborescence problem
• Online Euclidean Spanners
• The Performance of greedy algorithms for the on-line steiner tree and related problems

This page was built for publication: On-line Steiner trees in the Euclidean plane

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