zbMATH — the first resource for mathematics

Dynamic path counting and reporting in linear space. (English) Zbl 1432.68092
Ahn, Hee-Kap (ed.) et al., Algorithms and computation. 25th international symposium, ISAAC 2014, Jeonju, Korea, December 15–17, 2014. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 8889, 565-577 (2014).
Summary: In the path reporting problem, we preprocess a tree on \(n\) nodes each of which is assigned a weight, such that given an arbitrary path and a weight range, we can report the nodes whose weights are within the range. We consider this problem in dynamic settings, and propose the first non-trivial linear-space solution that supports path reporting in \(O((\lg n / \lg \lg n)^2 + \mathrm{occ} \lg n / \lg \lg n)\) time, where occ is the output size, and the insertion and deletion of a node of an arbitrary degree in \(O(\lg ^{2+\epsilon} n)\) amortized time, for any constant \(\epsilon \in (0, 1)\). Obvious solutions based on directly dynamizing solutions to the static version of this problem all require \(\Omega ((\lg n / \lg \lg n)^2)\) time for each node reported, and thus our query time is much faster. For the counting version of this problem, we design a structure that supports path counting in \(O((\lg n / \lg \lg n)^2)\) time, and insertion and deletion in \(O((\lg n / \lg \lg n)^2)\) amortized time. This matches the current best result for 2D dynamic range counting, which can be viewed as a special case of path counting.
For the entire collection see [Zbl 1318.68007].

68P05 Data structures
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI