Succinct Permutation Graphs

Tsakalidis, Konstantinos ORCID: 0000-0001-6470-9332, Wild, Sebastian ORCID: 0000-0002-6061-9177 and Zamaraev, Viktor ORCID: 0000-0001-5755-4141 (2023) Succinct Permutation Graphs. Algorithmica, 85 (2). pp. 509-543.

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

Official URL: http://dx.doi.org/10.1007/s00453-022-01039-2

Abstract

We present a succinct data structure for permutation graphs, and their superclass of circular permutation graphs, i.e., data structures using optimal space up to lower order terms. Unlike concurrent work on circle graphs (Acan et al. in Theor Comput Sci, https://doi.org/10.1016/j.tcs.2022.06.022, 2022), our data structure also supports distance and shortest-path queries, as well as adjacency and neighborhood queries, all in optimal time. We present in particular the first succinct exact distance oracle for (circular) permutation graphs. A second succinct data structure also supports degree queries in time independent of the neighborhood’s size at the expense of an O(logn/loglogn)-factor overhead in all running times. Furthermore, we develop a succinct data structure for the class of bipartite permutation graphs. We demonstrate how to run algorithms directly over our succinct representations for several problems on permutation graphs: CLIQUE, COLORING, INDEPENDENT SET, HAMILTONIAN CYCLE, ALL-PAIR SHORTEST PATHS, and others. Finally, we initiate the study of semi-distributed graph representations; a concept that smoothly interpolates between distributed (labeling schemes) and centralized (standard data structures). We show how to turn some of our data structures into semi-distributed representations by storing only O(n) bits of additional global information, circumventing the lower bound on distance labeling schemes for permutation graphs.

Item Type:	Article
Uncontrolled Keywords:	Succinct data structures, Distance oracles, Permutation graphs, Bipartite permutations graphs, Circular permutation graphs, Graph compression, Graph encoding
Depositing User:	Symplectic Admin
Date Deposited:	07 Oct 2022 15:16
Last Modified:	19 Nov 2023 03:48
DOI:	10.1007/s00453-022-01039-2
Open Access URL:	https://doi.org/10.1007/s00453-022-01039-2
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3165254