Gagie, Travis and Wild, Sebastian ORCID: 0000-0002-6061-9177
(2021)
Succinct Euler-Tour Trees.
In: 33rd Canadian Conference on Computational Geometry (CCCG 2021).
Text
2105.04965v2.pdf - Author Accepted Manuscript Download (478kB) | Preview |
Abstract
We show how a collection of Euler-tour trees for a forest on $n$ vertices can be stored in $2 n + o (n)$ bits such that simple queries take constant time, more complex queries take logarithmic time and updates take polylogarithmic amortized time.
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Uncontrolled Keywords: | cs.DS, cs.DS |
Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
Depositing User: | Symplectic Admin |
Date Deposited: | 04 Oct 2021 08:02 |
Last Modified: | 18 Jan 2023 21:27 |
Open Access URL: | https://projects.cs.dal.ca/cccg2021/wordpress/wp-c... |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3138942 |
Share
CORE (COnnecting REpositories)