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
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(489.4KB)

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.