The search functionality is under construction.
The search functionality is under construction.

Path Maximum Query and Path Maximum Sum Query in a Tree

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

  • Full Text Views

    0

  • Cite this

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