IEICE TRANSACTIONS on Information
Path Maximum Query and Path Maximum Sum Query in a Tree
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E92-D No.2 pp.166-171
- Publication Date
- 2009/02/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E92.D.166
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
