Distance oracles for interval graphs via breadth-first rank/select in succinct trees

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.

Access the full-text of this item by clicking on the Open Access link.


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: 11 May 2024 00:42
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