Optimal labelling schemes for adjacency, comparability, and reachability

2020/12/03 by Bonamy, Marthe, Esperet, Louis, Groenland, Carla +1 · 1 citation
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2012.01764

Abstract

We construct asymptotically optimal adjacency labelling schemes for every hereditary class containing 2^Ω(n2) n-vertex graphs as n→ ∞. This regime contains many classes of interest, for instance perfect graphs or comparability graphs, for which we obtain an adjacency labelling scheme with labels of n/4+o(n) bits per vertex. This implies the existence of a reachability labelling scheme for digraphs with labels of n/4+o(n) bits per vertex and comparability labelling scheme for posets with labels of n/4+o(n) bits per element. All these results are best possible, up to the lower order term.

Cited by

• Smaller universal posets

Related

• Adjacency labeling schemes and induced-universal graphs
• Tight bounds on adjacency labels for monotone graph classes
• A Complexity Theory for Labeling Schemes
• Shorter Labeling Schemes for Planar Graphs
• Near-optimal adjacency labeling scheme for power-law graphs