Optimal induced universal graphs and adjacency labeling for trees

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

Optimal induced universal graphs and adjacency labeling for trees. / Alstrup, Stephen; Dahlgaard, Søren; Knudsen, Mathias Bæk Tejs.

In: Journal of the ACM, Vol. 64, No. 4, 27, 09.2017.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Alstrup, S, Dahlgaard, S & Knudsen, MBT 2017, 'Optimal induced universal graphs and adjacency labeling for trees', Journal of the ACM, vol. 64, no. 4, 27. https://doi.org/10.1145/3088513

APA

Alstrup, S., Dahlgaard, S., & Knudsen, M. B. T. (2017). Optimal induced universal graphs and adjacency labeling for trees. Journal of the ACM, 64(4), [27]. https://doi.org/10.1145/3088513

Vancouver

Alstrup S, Dahlgaard S, Knudsen MBT. Optimal induced universal graphs and adjacency labeling for trees. Journal of the ACM. 2017 Sep;64(4). 27. https://doi.org/10.1145/3088513

Author

Alstrup, Stephen ; Dahlgaard, Søren ; Knudsen, Mathias Bæk Tejs. / Optimal induced universal graphs and adjacency labeling for trees. In: Journal of the ACM. 2017 ; Vol. 64, No. 4.

Bibtex

@article{107a8ba0c1404022bc24aa38db345f8d,
title = "Optimal induced universal graphs and adjacency labeling for trees",
abstract = "In this article, we show that there exists a graph G with O(n) nodes such that any forest of n nodes is an induced subgraph of G Furthermore, for constant arboricity k, the result implies the existence of a graph with O(nk) nodes that contains all n-node graphs of arboricity k as node-induced subgraphs, matching a Ω(nk) lower bound of Alstrup and Rauhe. Our upper bounds are obtained through a log2 n + O(1) labeling scheme for adjacency queries in forests. We hereby solve an open problem being raised repeatedly over decades by authors such as Kannan et al., Chung, and Fraigniaud and Korman.",
keywords = "Adjacency labeling, Graph theory, Induced universal graphs, Trees, XML",
author = "Stephen Alstrup and S{\o}ren Dahlgaard and Knudsen, {Mathias B{\ae}k Tejs}",
year = "2017",
month = sep,
doi = "10.1145/3088513",
language = "English",
volume = "64",
journal = "Journal of the ACM",
issn = "0004-5411",
publisher = "Association for Computing Machinery",
number = "4",

}

RIS

TY - JOUR

T1 - Optimal induced universal graphs and adjacency labeling for trees

AU - Alstrup, Stephen

AU - Dahlgaard, Søren

AU - Knudsen, Mathias Bæk Tejs

PY - 2017/9

Y1 - 2017/9

N2 - In this article, we show that there exists a graph G with O(n) nodes such that any forest of n nodes is an induced subgraph of G Furthermore, for constant arboricity k, the result implies the existence of a graph with O(nk) nodes that contains all n-node graphs of arboricity k as node-induced subgraphs, matching a Ω(nk) lower bound of Alstrup and Rauhe. Our upper bounds are obtained through a log2 n + O(1) labeling scheme for adjacency queries in forests. We hereby solve an open problem being raised repeatedly over decades by authors such as Kannan et al., Chung, and Fraigniaud and Korman.

AB - In this article, we show that there exists a graph G with O(n) nodes such that any forest of n nodes is an induced subgraph of G Furthermore, for constant arboricity k, the result implies the existence of a graph with O(nk) nodes that contains all n-node graphs of arboricity k as node-induced subgraphs, matching a Ω(nk) lower bound of Alstrup and Rauhe. Our upper bounds are obtained through a log2 n + O(1) labeling scheme for adjacency queries in forests. We hereby solve an open problem being raised repeatedly over decades by authors such as Kannan et al., Chung, and Fraigniaud and Korman.

KW - Adjacency labeling

KW - Graph theory

KW - Induced universal graphs

KW - Trees

KW - XML

UR - http://www.scopus.com/inward/record.url?scp=85028082133&partnerID=8YFLogxK

U2 - 10.1145/3088513

DO - 10.1145/3088513

M3 - Journal article

AN - SCOPUS:85028082133

VL - 64

JO - Journal of the ACM

JF - Journal of the ACM

SN - 0004-5411

IS - 4

M1 - 27

ER -

ID: 184140122