An average case analysis of a greedy algorithm for the on-line Steiner tree problem

DOI10.1016/0898-1221(96)00069-7zbMath0851.68038OpenAlexW2118742652MaRDI QIDQ1921250

Yunn Yen Chen, Ying Teh Tsai, Chuan Yi Tang

Publication date: 10 November 1996

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0898-1221(96)00069-7

zbMATH Keywords

on-line algorithmSteiner treeEuclidean tree

Mathematics Subject Classification ID

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

Related Items (1)

Average performance of a greedy algorithm for the on-line minimum matching problem on Euclidean space

Cites Work

• Unnamed Item
• An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability
• A proof of the Gilbert-Pollak conjecture on the Steiner ratio
• The Average Complexity of Deterministic and Randomized Parallel Comparison-Sorting Algorithms
• An upper bound for the average length of the euclidean minimum spanning tree
• Dynamic Steiner Tree Problem

This page was built for publication: An average case analysis of a greedy algorithm for the on-line Steiner tree problem