Labeling schemes for bounded degree graphs

David Adjiashvili; Noy Galil Rotbart

doi:10.1007/978-3-662-43951-7_32

Labeling schemes for bounded degree graphs

David Adjiashvili, Noy Galil Rotbart

Department of Computer Science

10 Citations (Scopus)

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.

Original language	English
Title of host publication	Automata, languages, and programming : 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II
Editors	Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, Elias Koutsoupias
Number of pages	12
Publisher	Springer
Publication date	2014
Pages	375-386
ISBN (Print)	978-3-662-43950-0
ISBN (Electronic)	978-3-662-43951-7
DOIs	https://doi.org/10.1007/978-3-662-43951-7_32
Publication status	Published - 2014
Event	International Colloquium on Automata, Languages, and Programming 2014 - Copenhagen, Denmark Duration: 8 Jul 2014 → 11 Jul 2014 Conference number: 41

Conference

Conference	International Colloquium on Automata, Languages, and Programming 2014
Number	41
Country/Territory	Denmark
City	Copenhagen
Period	08/07/2014 → 11/07/2014
Sponsor	CWI Amsterdam, EATCS, Springer-Verlag, Statens Kunstfond

Series	Lecture notes in computer science
Volume	8573
ISSN	0302-9743

Access to Document

10.1007/978-3-662-43951-7_32

Cite this

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_32

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

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_32

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). doi: 10.1007/978-3-662-43951-7_32

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).

@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",

note = "International Colloquium on Automata, Languages, and Programming 2014 ; Conference date: 08-07-2014 Through 11-07-2014",

}

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

T2 - International Colloquium on Automata, Languages, and Programming 2014

Y2 - 8 July 2014 through 11 July 2014

ER -

Labeling schemes for bounded degree graphs

Abstract

Conference

Access to Document

Fingerprint

Cite this