Optimal labelling schemes for adjacency, comparability, and reachability

Conference paper (2021)

Authors

Marthe Bonamy ENS-PSL Research University & CNRS, CEA, Labri

Louis Esperet ENS-PSL Research University & CNRS, Université Grenoble Alpes, G-SCOP

C.E. Groenland University of Oxford

Alex Scott University of Oxford

Affiliation

External organisation

Adjacency labelling Dense graph classes Graph labelling Reachability labelling

More Info

expand_more

To reference this document use:

http://resolver.tudelft.nl/uuid:c4a56f86-08f0-4a2b-aeb4-59d09ff5cc97

Published Date

2021

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Affiliation

External organisation

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.