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
|