Adjacency Labeling Schemes and Induced-Universal Graphs
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
Adjacency Labeling Schemes and Induced-Universal Graphs. / Alstrup, Stephen; Kaplan, Haim; Thorup, Mikkel; Zwick, Uri.
I: SIAM Journal on Discrete Mathematics, Bind 33, Nr. 1, 2019, s. 116-137.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Adjacency Labeling Schemes and Induced-Universal Graphs
AU - Alstrup, Stephen
AU - Kaplan, Haim
AU - Thorup, Mikkel
AU - Zwick, Uri
PY - 2019
Y1 - 2019
N2 - We describe a way of assigning labels to the vertices of any undirected graph on up to $n$ vertices, each composed of $n/2+O(1)$ bits, such that given the labels of two vertices, and no other information regarding the graph, it is possible to decide whether or not the vertices are adjacent in the graph. This is optimal, up to an additive constant, and constitutes the first improvement in almost 50 years of an $n/2+O(\log n)$ bound of Moon. As a consequence, we obtain an induced-universal graph for $n$-vertex graphs containing only $O(2^{n/2})$ vertices, which is optimal up to a multiplicative constant, solving an open problem of Vizing from 1968. We obtain similar tight results for directed graphs, tournaments, and bipartite graphs.Read More: https://epubs.siam.org/doi/10.1137/16M1105967
AB - We describe a way of assigning labels to the vertices of any undirected graph on up to $n$ vertices, each composed of $n/2+O(1)$ bits, such that given the labels of two vertices, and no other information regarding the graph, it is possible to decide whether or not the vertices are adjacent in the graph. This is optimal, up to an additive constant, and constitutes the first improvement in almost 50 years of an $n/2+O(\log n)$ bound of Moon. As a consequence, we obtain an induced-universal graph for $n$-vertex graphs containing only $O(2^{n/2})$ vertices, which is optimal up to a multiplicative constant, solving an open problem of Vizing from 1968. We obtain similar tight results for directed graphs, tournaments, and bipartite graphs.Read More: https://epubs.siam.org/doi/10.1137/16M1105967
U2 - 10.1137/16M1105967
DO - 10.1137/16M1105967
M3 - Journal article
VL - 33
SP - 116
EP - 137
JO - SIAM Journal on Discrete Mathematics
JF - SIAM Journal on Discrete Mathematics
SN - 0895-4801
IS - 1
ER -
ID: 212131248