Optimal induced universal graphs and adjacency labeling for trees
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Optimal induced universal graphs and adjacency labeling for trees. / Alstrup, Stephen; Dahlgaard, Søren; Knudsen, Mathias Bæk Tejs.
2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2015. p. 1311-1326 (Symposium on Foundations of Computer Science. Annual Proceedings).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Optimal induced universal graphs and adjacency labeling for trees
AU - Alstrup, Stephen
AU - Dahlgaard, Søren
AU - Knudsen, Mathias Bæk Tejs
N1 - Conference code: 56
PY - 2015
Y1 - 2015
N2 - We show that there exists a graph G with O(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 O(nk) nodes that contains all n-node graphs as node-induced subgraphs, matching a Ω(nk) 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 log2 n + O(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 O(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 O(nk) nodes that contains all n-node graphs as node-induced subgraphs, matching a Ω(nk) 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 log2 n + O(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.1109/FOCS.2015.84
DO - 10.1109/FOCS.2015.84
M3 - Article in proceedings
T3 - Symposium on Foundations of Computer Science. Annual Proceedings
SP - 1311
EP - 1326
BT - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)
PB - IEEE
Y2 - 18 October 2015 through 20 October 2015
ER -
ID: 159731418