The search functionality is under construction.

Keyword Search Result

[Keyword] path maximum sum query(1hit)

1-1hit
  • Path Maximum Query and Path Maximum Sum Query in a Tree

    Sung Kwon KIM  Jung-Sik CHO  Soo-Cheol KIM  

     
    PAPER

      Vol:
    E92-D No:2
      Page(s):
    166-171

    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.