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
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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Sung Kwon KIM, Jung-Sik CHO, Soo-Cheol KIM, "Path Maximum Query and Path Maximum Sum Query in a Tree" in IEICE TRANSACTIONS on Information,
vol. E92-D, no. 2, pp. 166-171, February 2009, doi: 10.1587/transinf.E92.D.166.
Abstract: Let T be a node-weighted tree with n nodes, and let π(u,v) denote the path between two nodes u and v in T. We address two problems: (i) Path Maximum Query: Preprocess T so that, for a query pair of nodes u and v, the maximum weight on π(u,v) can be found quickly. (ii) Path Maximum Sum Query: Preprocess T so that, for a query pair of nodes u and v, the maximum weight sum subpath of π(u,v) can be found quickly. For the problems we present solutions with O(1) query time and O(n log n) preprocessing time.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E92.D.166/_p
Copier
@ARTICLE{e92-d_2_166,
author={Sung Kwon KIM, Jung-Sik CHO, Soo-Cheol KIM, },
journal={IEICE TRANSACTIONS on Information},
title={Path Maximum Query and Path Maximum Sum Query in a Tree},
year={2009},
volume={E92-D},
number={2},
pages={166-171},
abstract={Let T be a node-weighted tree with n nodes, and let π(u,v) denote the path between two nodes u and v in T. We address two problems: (i) Path Maximum Query: Preprocess T so that, for a query pair of nodes u and v, the maximum weight on π(u,v) can be found quickly. (ii) Path Maximum Sum Query: Preprocess T so that, for a query pair of nodes u and v, the maximum weight sum subpath of π(u,v) can be found quickly. For the problems we present solutions with O(1) query time and O(n log n) preprocessing time.},
keywords={},
doi={10.1587/transinf.E92.D.166},
ISSN={1745-1361},
month={February},}
Copier
TY - JOUR
TI - Path Maximum Query and Path Maximum Sum Query in a Tree
T2 - IEICE TRANSACTIONS on Information
SP - 166
EP - 171
AU - Sung Kwon KIM
AU - Jung-Sik CHO
AU - Soo-Cheol KIM
PY - 2009
DO - 10.1587/transinf.E92.D.166
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E92-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2009
AB - Let T be a node-weighted tree with n nodes, and let π(u,v) denote the path between two nodes u and v in T. We address two problems: (i) Path Maximum Query: Preprocess T so that, for a query pair of nodes u and v, the maximum weight on π(u,v) can be found quickly. (ii) Path Maximum Sum Query: Preprocess T so that, for a query pair of nodes u and v, the maximum weight sum subpath of π(u,v) can be found quickly. For the problems we present solutions with O(1) query time and O(n log n) preprocessing time.
ER -