On-line Steiner trees in the Euclidean plane

DOI10.1007/BF02573969zbMATH Open0774.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

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

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)

Cites Work

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

Cited In (26)

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

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)