Adjacency labeling schemes and induced-universal graphs

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

Standard

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

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

Harvard

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

APA

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 (pp. 625-634). Association for Computing Machinery. https://doi.org/10.1145/2746539.2746545

Vancouver

Alstrup S, Kaplan H, Thorup M, Zwick U. 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. 2015. p. 625-634 https://doi.org/10.1145/2746539.2746545

Author

Alstrup, Stephen ; Kaplan, Haim ; Thorup, Mikkel ; Zwick, Uri. / Adjacency labeling schemes and induced-universal graphs. 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. pp. 625-634

Bibtex

@inproceedings{775240d2a46c494ebe26777ee6599530,
title = "Adjacency labeling schemes and induced-universal graphs",
abstract = "We show that there exists a graph $G$ with $\Oh(n)$ nodes, where any forest of $n$ nodes is a node-induced subgraph of $G$. Furthermore, for constant arboricity $k$, the result implies the existence of a graph with $\Oh(n^k)$ nodes that contains all $n$-node graphs as node-induced subgraphs, matching a $\Omega(n^k)$ lower bound. The lower bound and previously best upper bounds were presented in Alstrup and Rauhe (FOCS'02). Our upper bounds are obtained through a $\log_2 n +\Oh(1)$ labeling scheme for adjacency queries in forests.We hereby solve an open problem being raised repeatedly over decades, e.g. in Kannan, Naor, Rudich (STOC 1988), Chung (J. of Graph Theory 1990), Fraigniaud and Korman (SODA 2010).",
author = "Stephen Alstrup and Haim Kaplan and Mikkel Thorup and Uri Zwick",
year = "2015",
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",

}

RIS

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

Y1 - 2015

N2 - We show that there exists a graph $G$ with $\Oh(n)$ nodes, where any forest of $n$ nodes is a node-induced subgraph of $G$. Furthermore, for constant arboricity $k$, the result implies the existence of a graph with $\Oh(n^k)$ nodes that contains all $n$-node graphs as node-induced subgraphs, matching a $\Omega(n^k)$ lower bound. The lower bound and previously best upper bounds were presented in Alstrup and Rauhe (FOCS'02). Our upper bounds are obtained through a $\log_2 n +\Oh(1)$ labeling scheme for adjacency queries in forests.We hereby solve an open problem being raised repeatedly over decades, e.g. in Kannan, Naor, Rudich (STOC 1988), Chung (J. of Graph Theory 1990), Fraigniaud and Korman (SODA 2010).

AB - We show that there exists a graph $G$ with $\Oh(n)$ nodes, where any forest of $n$ nodes is a node-induced subgraph of $G$. Furthermore, for constant arboricity $k$, the result implies the existence of a graph with $\Oh(n^k)$ nodes that contains all $n$-node graphs as node-induced subgraphs, matching a $\Omega(n^k)$ lower bound. The lower bound and previously best upper bounds were presented in Alstrup and Rauhe (FOCS'02). Our upper bounds are obtained through a $\log_2 n +\Oh(1)$ labeling scheme for adjacency queries in forests.We hereby solve an open problem being raised repeatedly over decades, e.g. in Kannan, Naor, Rudich (STOC 1988), Chung (J. of Graph Theory 1990), Fraigniaud and Korman (SODA 2010).

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 -

ID: 138930710