Standard
Labeling schemes for bounded degree graphs. / Adjiashvili, David; Rotbart, Noy Galil.
Automata, languages, and programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II. ed. / Javier Esparza; Pierre Fraigniaud; Thore Husfeldt; Elias Koutsoupias. Springer, 2014. p. 375-386 (Lecture notes in computer science, Vol. 8573).
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
Adjiashvili, D & Rotbart, NG 2014,
Labeling schemes for bounded degree graphs. in J Esparza, P Fraigniaud, T Husfeldt & E Koutsoupias (eds),
Automata, languages, and programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II. Springer, Lecture notes in computer science, vol. 8573, pp. 375-386, International Colloquium on Automata, Languages, and Programming 2014, Copenhagen, Denmark,
08/07/2014.
https://doi.org/10.1007/978-3-662-43951-7_32APA
Adjiashvili, D., & Rotbart, N. G. (2014).
Labeling schemes for bounded degree graphs. In J. Esparza, P. Fraigniaud, T. Husfeldt, & E. Koutsoupias (Eds.),
Automata, languages, and programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II (pp. 375-386). Springer. Lecture notes in computer science Vol. 8573
https://doi.org/10.1007/978-3-662-43951-7_32Vancouver
Adjiashvili D, Rotbart NG.
Labeling schemes for bounded degree graphs. In Esparza J, Fraigniaud P, Husfeldt T, Koutsoupias E, editors, Automata, languages, and programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II. Springer. 2014. p. 375-386. (Lecture notes in computer science, Vol. 8573).
https://doi.org/10.1007/978-3-662-43951-7_32Author
Adjiashvili, David ; Rotbart, Noy Galil. / Labeling schemes for bounded degree graphs. Automata, languages, and programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II. editor / Javier Esparza ; Pierre Fraigniaud ; Thore Husfeldt ; Elias Koutsoupias. Springer, 2014. pp. 375-386 (Lecture notes in computer science, Vol. 8573).
Bibtex
@inproceedings{73350e3a212b4cb9adf6cc95a195813b,
title = "Labeling schemes for bounded degree graphs",
abstract = "We investigate adjacency labeling schemes for graphs of bounded degree Δ = O(1). In particular, we present an optimal (up to an additive constant) log n + O(1) adjacency labeling scheme for bounded degree trees. The latter scheme is derived from a labeling scheme for bounded degree outerplanar graphs. Our results complement a similar bound recently obtained for bounded depth trees [Fraigniaud and Korman, SODA 2010], and may provide new insights for closing the long standing gap for adjacency in trees [Alstrup and Rauhe, FOCS 2002]. We also provide improved labeling schemes for bounded degree planar graphs. Finally, we use combinatorial number systems and present an improved adjacency labeling schemes for graphs of bounded degree Δ with (e + 1) √n <Δ ≤ n/5.",
author = "David Adjiashvili and Rotbart, {Noy Galil}",
year = "2014",
doi = "10.1007/978-3-662-43951-7_32",
language = "English",
isbn = "978-3-662-43950-0",
series = "Lecture notes in computer science",
publisher = "Springer",
pages = "375--386",
editor = "Javier Esparza and Pierre Fraigniaud and Thore Husfeldt and Elias Koutsoupias",
booktitle = "Automata, languages, and programming",
address = "Switzerland",
note = "null ; Conference date: 08-07-2014 Through 11-07-2014",
}
RIS
TY - GEN
T1 - Labeling schemes for bounded degree graphs
AU - Adjiashvili, David
AU - Rotbart, Noy Galil
N1 - Conference code: 41
PY - 2014
Y1 - 2014
N2 - We investigate adjacency labeling schemes for graphs of bounded degree Δ = O(1). In particular, we present an optimal (up to an additive constant) log n + O(1) adjacency labeling scheme for bounded degree trees. The latter scheme is derived from a labeling scheme for bounded degree outerplanar graphs. Our results complement a similar bound recently obtained for bounded depth trees [Fraigniaud and Korman, SODA 2010], and may provide new insights for closing the long standing gap for adjacency in trees [Alstrup and Rauhe, FOCS 2002]. We also provide improved labeling schemes for bounded degree planar graphs. Finally, we use combinatorial number systems and present an improved adjacency labeling schemes for graphs of bounded degree Δ with (e + 1) √n <Δ ≤ n/5.
AB - We investigate adjacency labeling schemes for graphs of bounded degree Δ = O(1). In particular, we present an optimal (up to an additive constant) log n + O(1) adjacency labeling scheme for bounded degree trees. The latter scheme is derived from a labeling scheme for bounded degree outerplanar graphs. Our results complement a similar bound recently obtained for bounded depth trees [Fraigniaud and Korman, SODA 2010], and may provide new insights for closing the long standing gap for adjacency in trees [Alstrup and Rauhe, FOCS 2002]. We also provide improved labeling schemes for bounded degree planar graphs. Finally, we use combinatorial number systems and present an improved adjacency labeling schemes for graphs of bounded degree Δ with (e + 1) √n <Δ ≤ n/5.
U2 - 10.1007/978-3-662-43951-7_32
DO - 10.1007/978-3-662-43951-7_32
M3 - Article in proceedings
AN - SCOPUS:84904188653
SN - 978-3-662-43950-0
T3 - Lecture notes in computer science
SP - 375
EP - 386
BT - Automata, languages, and programming
A2 - Esparza, Javier
A2 - Fraigniaud, Pierre
A2 - Husfeldt, Thore
A2 - Koutsoupias, Elias
PB - Springer
Y2 - 8 July 2014 through 11 July 2014
ER -
