The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems

DOI10.1016/0020-0190(93)90142-VzbMath0787.68084MaRDI QIDQ1313740

Ying Teh Tsai, Chuan Yi Tang

Publication date: 19 May 1994

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

competitive analysison-line spanning treeon-line Steiner treerandomized on-line algorithms

Mathematics Subject Classification ID

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

Related Items (2)

Average competitive ratios of on-line spanning trees ⋮ Online Minimum Spanning Tree with Advice

Cites Work

• The Average Complexity of Deterministic and Randomized Parallel Comparison-Sorting Algorithms
• Dynamic Steiner Tree Problem
• An Analysis of Several Heuristics for the Traveling Salesman Problem

This page was built for publication: The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems