Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874228 | Information Processing Letters | 2018 | 5 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Irena Rusu,