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
APA
Vancouver
Author
Bibtex
}
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