Forskning ved Københavns Universitet - Københavns Universitet

Forside

Adjacency Labeling Schemes and Induced-Universal Graphs

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningfagfæ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 tidsskriftTidsskriftartikelForskningfagfællebedømt

Harvard

Alstrup, S, Kaplan, H, Thorup, M & Zwick, U 2019, 'Adjacency Labeling Schemes and Induced-Universal Graphs', SIAM Journal on Discrete Mathematics, bind 33, nr. 1, s. 116-137. https://doi.org/10.1137/16M1105967

APA

Alstrup, S., Kaplan, H., Thorup, M., & Zwick, U. (2019). Adjacency Labeling Schemes and Induced-Universal Graphs. SIAM Journal on Discrete Mathematics, 33(1), 116-137. https://doi.org/10.1137/16M1105967

Vancouver

Alstrup S, Kaplan H, Thorup M, Zwick U. Adjacency Labeling Schemes and Induced-Universal Graphs. SIAM Journal on Discrete Mathematics. 2019;33(1):116-137. https://doi.org/10.1137/16M1105967

Author

Alstrup, Stephen ; Kaplan, Haim ; Thorup, Mikkel ; Zwick, Uri. / Adjacency Labeling Schemes and Induced-Universal Graphs. I: SIAM Journal on Discrete Mathematics. 2019 ; Bind 33, Nr. 1. s. 116-137.

Bibtex

@article{99e63553d8f74449838cd83f1330ffd3,
title = "Adjacency Labeling Schemes and Induced-Universal Graphs",
abstract = "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",
author = "Stephen Alstrup and Haim Kaplan and Mikkel Thorup and Uri Zwick",
year = "2019",
doi = "10.1137/16M1105967",
language = "English",
volume = "33",
pages = "116--137",
journal = "S I A M Journal on Discrete Mathematics",
issn = "0895-4801",
publisher = "Society for Industrial and Applied Mathematics",
number = "1",

}

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 - S I A M Journal on Discrete Mathematics

JF - S I A M Journal on Discrete Mathematics

SN - 0895-4801

IS - 1

ER -

ID: 212131248