Average competitive ratios of on-line spanning trees

DOI10.1016/S0020-0190(97)00064-1zbMath1337.68198MaRDI QIDQ287071

Yoshihide Igarashi, Aohan Mei, Feng Bao

Publication date: 26 May 2016

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

zbMATH Keywords

analysis of algorithmsaverage-case analysisminimum spanning treescompetitive ratios

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Cites Work

• The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems
• Dynamic Steiner Tree Problem

This page was built for publication: Average competitive ratios of on-line spanning trees