Optimal labelling schemes for adjacency, comparability, and reachability
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...
Main Authors: | , , , |
---|---|
Format: | Conference item |
Language: | English |
Published: |
Association for Computing Machinery
2021
|