# 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].

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