La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Path Maximum Query and Path Maximum Sum Query in a Tree Requête de chemin maximum et requête de somme maximale de chemin dans une arborescence

Sung Kwon KIM, Jung-Sik CHO, Soo-Cheol KIM

  • Vues en texte intégral

    0

  • Citer

Résumé:

Laisser nous T être un arbre pondéré par les nœuds avec n nœuds, et soit π(u,v) désigne le chemin entre deux nœuds u et à la v in T. Nous abordons deux problèmes : (i) Requête maximale de chemin : prétraitement T de sorte que, pour une paire de nœuds de requête u et à la v, le poids maximum sur π(u,v) peut être trouvé rapidement. (ii) Requête de somme maximale de chemin : prétraitement T de sorte que, pour une paire de nœuds de requête u et à la v, le sous-chemin de la somme de poids maximale de π(u,v) peut être trouvé rapidement. Pour les problèmes avec lesquels nous présentons des solutions O(1) temps de requête et O(n enregistrer n) temps de prétraitement.

Publication
IEICE TRANSACTIONS on Information Vol.E92-D No.2 pp.166-171
Date de publication
2009/02/01
Publicisé
ISSN en ligne
1745-1361
DOI
10.1587/transinf.E92.D.166
Type de manuscrit
Special Section PAPER (Special Section on Foundations of Computer Science)
Catégories

Auteurs

Mots-clés

Table des matières