Succinct Euler-Tour Trees


Gagie, Travis and Wild, Sebastian ORCID: 0000-0002-6061-9177 (2021) Succinct Euler-Tour Trees. In: 33rd Canadian Conference on Computational Geometry (CCCG 2021).

Access the full-text of this item by clicking on the Open Access link.
[img] 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
CORE (COnnecting REpositories)