Article ID Journal Published Year Pages File Type
6874228 Information Processing Letters 2018 5 Pages PDF
Abstract
Seeking an O(nlog⁡n) algorithm requires to drop the b addend in the running time formulas, which prevents the choice of a large b. To this end, we propose an implementation of the algorithm whose originality lies in the use of O(log⁡n) aggregate operations allowed by link-cut trees, and by their filiform variant called log-lists. The resulting algorithm has the advantage of reaching a running time of O(n(nblog⁡b)), but also has the drawback of potentially making use of very large numbers, reducing in practice the choices of b.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,