Path Maximum Query and Path Maximum Sum Query in a Tree

Sung Kwon KIM  Jung-Sik CHO  Soo-Cheol KIM  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E92-D   No.2   pp.166-171
Publication Date: 2009/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E92.D.166
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
path maximum query,  path maximum sum query,  tree,  

Full Text: PDF(493.3KB)>>
Buy this Article




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.