کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430932 688233 2012 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Succinct representations of weighted trees supporting path queries
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Succinct representations of weighted trees supporting path queries
چکیده انگلیسی

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,…,σ}{1,2,…,σ} 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][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) bits space and can perform path median/selection/counting   in O(logσ) time and path reporting   in O(logσ+occlogσ) time, where occ   represents the number of outputs [M. He, J.I. Munro, G. Zhou, Path queries in weighted trees, in: International Symposium on Algorithms and Computation, 2011, pp. 140–149]. We present a succinct data structure taking nlogσ+6n+o(nlogσ) bits space that can perform the above mentioned queries in O(logσlogn) and O(logσlogn+occlogσ) time respectively.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 17, December 2012, Pages 103–108
نویسندگان
, , ,