publication . Article . 2012

succinct representations of weighted trees supporting path queries

Patil, Manish; Shah, Rahul; Thankachan, Sharma V.;
Restricted
  • Published: 01 Dec 2012 Journal: Journal of Discrete Algorithms, volume 17, pages 103-108 (issn: 1570-8667, Copyright policy)
  • Publisher: Elsevier BV
Abstract
We consider the problem of succinctly representing a given vertex-weighted tree of n vertices, whose vertices are labeled by integer weights from {1,2,...,@s} and supporting the following path queries efficiently:*Path median query: Given two vertices i, j, return the median weight on the path from i to j. *Path selection query: Given two vertices i, j and a positive integer k, return the kth smallest weight on the path from i to j. *Path counting/reporting query: Given two vertices i, j and a range [a,b], count/report the vertices on the path from i to j whose weights are in this range. The previous best data structure supporting these queries takes O(nlogn) bi...
Subjects
ACM Computing Classification System: MathematicsofComputing_DISCRETEMATHEMATICSTheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY
free text keywords: Theoretical Computer Science, Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Longest path problem, Induced path, Shortest path problem, Integer, Combinatorics, Discrete mathematics, Distance, Vertex (geometry), Path graph, Mathematics, Succinct data structure, Succinct data structures
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Article . 2012

succinct representations of weighted trees supporting path queries

Patil, Manish; Shah, Rahul; Thankachan, Sharma V.;