He, M, Ian Munro, J, Nekrich, Y, Wild, S 
ORCID: 0000-0002-6061-9177 and Wu, K
(2020)
Distance oracles for interval graphs via breadth-first rank/select in succinct trees.
In: The 31st International Symposium on Algorithms and Computation (ISAAC'20), 2020-12-14 - 2020-9-18.
Abstract
We present the first succinct distance oracles for (unweighted) interval graphs and related classes of graphs, using a novel succinct data structure for ordinal trees that supports the mapping between preorder (i.e., depth-first) ranks and level-order (breadth-first) ranks of nodes in constant time. Our distance oracles for interval graphs also support navigation queries – testing adjacency, computing node degrees, neighborhoods, and shortest paths – all in optimal time. Our technique also yields optimal distance oracles for proper interval graphs (unit-interval graphs) and circular-arc graphs. Our tree data structure supports all operations provided by different approaches in previous work, as well as mapping to and from level-order ranks and retrieving the last (first) internal node before (after) a given node in a level-order traversal, all in constant time.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 15 Oct 2020 12:26 |
| Last Modified: | 18 Jan 2023 23:28 |
| DOI: | 10.4230/LIPIcs.ISAAC.2020.25 |
| Open Access URL: | https://drops.dagstuhl.de/opus/volltexte/2020/1336... |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3104278 |
Dimensions
Dimensions
