The Performance of greedy algorithms for the on-line steiner tree and related problems

DOI10.1007/BF01185867zbMath0844.68098OpenAlexW2046699917MaRDI QIDQ4850333

Dicky C. K. Yan, Jeffery Westbrook

Publication date: 14 November 1995

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01185867

zbMATH Keywords

Steiner tree problemgreedy on-line algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (7)

Online Priority Steiner Tree Problems ⋮ Non-greedy online Steiner trees on outerplanar graphs ⋮ Non-greedy Online Steiner Trees on Outerplanar Graphs ⋮ A Near-Tight Bound for the Online Steiner Tree Problem in Graphs of Bounded Asymmetry ⋮ Linear bounds for on-line Steiner problems ⋮ THE EFFECT OF ASYMMETRY ON THE ON-LINE MULTICAST ROUTING PROBLEM ⋮ Parameterized analysis of the online priority and node-weighted Steiner tree problems

Cites Work

• On-line Steiner trees in the Euclidean plane
• Competitive algorithms for distributed data management.
• On Steiner trees for bounded point sets
• The simple plant location problem: Survey and synthesis
• The shortest path and the shortest road through n points
• A dual ascent approach for steiner tree problems on a directed graph
• Steiner problem in networks: A survey
• Dynamic Steiner Tree Problem
• The largest minimal rectilinear steiner trees for a set of n points enclosed in a rectangle with given perimeter
• Cost-minimal trees in directed acyclic graphs
• On Steiner’s Problem with Rectilinear Distance
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The Performance of greedy algorithms for the on-line steiner tree and related problems