Adjacency labeling schemes and induced-universal graphs

Stephen Alstrup; Haim Kaplan; Mikkel Thorup; Uri Zwick

doi:10.1145/2746539.2746545

Adjacency labeling schemes and induced-universal graphs

Stephen Alstrup, Haim Kaplan, Mikkel Thorup, Uri Zwick

Department of Computer Science

22 Citations (Scopus)

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.

Original language	English
Title of host publication	Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015 : STOC '15
Number of pages	10
Publisher	Association for Computing Machinery
Publication date	14 Jun 2015
Pages	625-634
ISBN (Print)	978-1-4503-3536-2
DOIs	https://doi.org/10.1145/2746539.2746545
Publication status	Published - 14 Jun 2015
Event	Annual ACM Symposium on the Theory of Computing 2015 - Portland, United States Duration: 15 Jun 2015 → 17 Jun 2015 Conference number: 47

Conference

Conference	Annual ACM Symposium on the Theory of Computing 2015
Number	47
Country/Territory	United States
City	Portland
Period	15/06/2015 → 17/06/2015

Access to Document

10.1145/2746539.2746545

Adjacency Labeling Schemes and Induced-Universal GraphsFinal published version, 887 KB

Cite this

Adjacency labeling schemes and induced-universal graphs. / Alstrup, Stephen; Kaplan, Haim; Thorup, Mikkel et al.

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015: STOC '15. Association for Computing Machinery, 2015. p. 625-634.

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Alstrup, S, Kaplan, H, Thorup, M & Zwick, U 2015, Adjacency labeling schemes and induced-universal graphs. in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015: STOC '15. Association for Computing Machinery, pp. 625-634, Annual ACM Symposium on the Theory of Computing 2015, Portland, United States, 15/06/2015. https://doi.org/10.1145/2746539.2746545

@inproceedings{775240d2a46c494ebe26777ee6599530,

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(2n/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.",

author = "Stephen Alstrup and Haim Kaplan and Mikkel Thorup and Uri Zwick",

year = "2015",

month = jun,

day = "14",

doi = "10.1145/2746539.2746545",

language = "English",

isbn = "978-1-4503-3536-2",

pages = "625--634",

booktitle = "Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015",

publisher = "Association for Computing Machinery",

note = "Annual ACM Symposium on the Theory of Computing 2015, STOC '15 ; Conference date: 15-06-2015 Through 17-06-2015",

}

TY - GEN

T1 - Adjacency labeling schemes and induced-universal graphs

AU - Alstrup, Stephen

AU - Kaplan, Haim

AU - Thorup, Mikkel

AU - Zwick, Uri

N1 - Conference code: 47

PY - 2015/6/14

Y1 - 2015/6/14

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(2n/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.

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(2n/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.

U2 - 10.1145/2746539.2746545

DO - 10.1145/2746539.2746545

M3 - Article in proceedings

SN - 978-1-4503-3536-2

SP - 625

EP - 634

BT - Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015

PB - Association for Computing Machinery

T2 - Annual ACM Symposium on the Theory of Computing 2015

Y2 - 15 June 2015 through 17 June 2015

ER -

Adjacency labeling schemes and induced-universal graphs

Abstract

Conference

Access to Document

Fingerprint

Cite this