Titre du document / Document title

An inverse-Ackermann style lower bound for the online minimum spanning tree verification problem

Auteur(s) / Author(s)

PETTIE Seth ⁽¹⁾ ;

Affiliation(s) du ou des auteurs / Author(s) Affiliation(s)

⁽¹⁾ Department of Computer Science, The University of Texas at Austin, Austin, TX 78712, ETATS-UNIS

Résumé / Abstract

We consider the problem of preprocessing an edge-weighted tree T in order to quickly answer queries of the following type: does a given edge e belong in the minimum spanning tree of T U {e}? Whereas the offline minimum spanning tree verification problem admits a lovely linear time solution, we demonstrate an inherent inverse-Ackermann type tradeoff in the online MST verification problem. In particular, any scheme that answers queries in t comparisons must invest Ω(n log λ_t(n)) time preprocessing the tree, where λ_t is the inverse of the t^throw of Ackermann's function. This implies a query lower bound of Ω(α(n)) for the case of linear preprocessing time. We also show that our lower bound is tight to within a factor of 2 in the t parameter.

Revue / Journal Title

Annual Symposium on Foundations of Computer Science  

Source / Source

Congrès
FOCS 2002 : foundations of computer science :   ( Vancouver BC, 16-19 November 2002 )
Annual IEEE symposium on foundations of computer science N^o43, Vancouver BC , CANADA (16/11/2002)
2002  , pp. 155-163[Note(s) : XVI, 812 p., ] [Document : 9 p.] (39 ref.) ISBN 0-7695-1822-2 ;  Illustration : Illustration ;

Langue / Language

Anglais

Editeur / Publisher

IEEE, Los Alamitos CA, ETATS-UNIS  (2002) (Monographie)

Mots-clés anglais / English Keywords

Upper bound

;

Lower bound

;

Data structure

;

Edge tree

;

Linear time

;

Spanning tree

;

Mots-clés français / French Keywords

Problème vérification minimum arbre maximal

;

Borne supérieure

;

Borne inférieure

;

Structure donnée

;

Arbre lisière

;

Temps linéaire

;

Arbre maximal

;

Mots-clés espagnols / Spanish Keywords

Cota superior

;

Cota inferior

;

Estructura datos

;

Arbol orilla

;

Tiempo lineal

;

Arbol máximo

;

Localisation / Location

INIST-CNRS, Cote INIST : Y 37959, 35400011775864.0150