Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Succinct Permutation Graphs   We present a succinct, i.e., asymptotically space-optimal, data structure for
permutation graphs that supports distance, adjacency, neighborhood and
shortest-path queries in optimal time; a variant of our data structure also
supports degree queries in time independent of the neighborhood's size at the
expense of an $O(\log n/\log \log n)$-factor overhead in all running times. We
show how to generalize our data structure to the class of circular permutation
graphs with asymptotically no extra space, while supporting the same queries in
optimal time. Furthermore, we develop a similar compact data structure for the
special case of bipartite permutation graphs and conjecture that it is succinct
for this class. We demonstrate how to execute algorithms directly over our
succinct representations for several combinatorial problems on permutation
graphs: Clique, Coloring, Independent Set, Hamiltonian Cycle, All-Pair Shortest
Paths, and others.
  Moreover, we initiate the study of semi-local graph representations; a
concept that "interpolates" between local labeling schemes and standard
"centralized" data structures. We show how to turn some of our data structures
into semi-local representations by storing only $O(n)$ bits of additional
global information, beating the lower bound on distance labeling schemes for
permutation graphs.

20
The categories of this paper are: acc-phys
4
The categories of this paper are: cond-mat
2
The categories of this paper are: math
31
The categories of this paper are: ao-sci
12
The categories of this paper are: nucl-th
6
The categories of this paper are: astro-ph
10
The categories of this paper are: q-bio
23
The categories of this paper are: solv-int
0
The categories of this paper are: hep-ph
24
The categories of this paper are: dg-ga
37
The categories of this paper are: supr-con
22
The categories of this paper are: chao-dyn
8
The categories of this paper are: hep-ex
11
The categories of this paper are: hep-lat
16
The categories of this paper are: stat
33
The categories of this paper are: plasm-ph