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

Datalogisk Institut

10 Citationer (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.

Originalsprog	Engelsk
Titel	Automata, languages, and programming : 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II
Redaktører	Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, Elias Koutsoupias
Antal sider	12
Forlag	Springer
Publikationsdato	2014
Sider	375-386
ISBN (Trykt)	978-3-662-43950-0
ISBN (Elektronisk)	978-3-662-43951-7
DOI	https://doi.org/10.1007/978-3-662-43951-7_32
Status	Udgivet - 2014
Begivenhed	International Colloquium on Automata, Languages, and Programming 2014 - Copenhagen, Danmark Varighed: 8 jul. 2014 → 11 jul. 2014 Konferencens nummer: 41

Konference

Konference	International Colloquium on Automata, Languages, and Programming 2014
Nummer	41
Land/Område	Danmark
By	Copenhagen
Periode	08/07/2014 → 11/07/2014
Sponsor	CWI Amsterdam, EATCS, Springer-Verlag, Statens Kunstfond

Navn	Lecture notes in computer science
Vol/bind	8573
ISSN	0302-9743

Adgang til dokumentet

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

Citationsformater

Adjiashvili, D., & Rotbart, N. G. (2014). Labeling schemes for bounded degree graphs. I J. Esparza, P. Fraigniaud, T. Husfeldt, & E. Koutsoupias (red.), Automata, languages, and programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II (s. 375-386). Springer. Lecture notes in computer science Bind 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. red. / Javier Esparza; Pierre Fraigniaud; Thore Husfeldt; Elias Koutsoupias. Springer, 2014. s. 375-386 (Lecture notes in computer science, Bind 8573).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Adjiashvili, D & Rotbart, NG 2014, Labeling schemes for bounded degree graphs. i J Esparza, P Fraigniaud, T Husfeldt & E Koutsoupias (red), Automata, languages, and programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II. Springer, Lecture notes in computer science, bind 8573, s. 375-386, International Colloquium on Automata, Languages, and Programming 2014, Copenhagen, Danmark, 08/07/2014. https://doi.org/10.1007/978-3-662-43951-7_32

Adjiashvili D, Rotbart NG. Labeling schemes for bounded degree graphs. I Esparza J, Fraigniaud P, Husfeldt T, Koutsoupias E, red., Automata, languages, and programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II. Springer. 2014. s. 375-386. (Lecture notes in computer science, Bind 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. red. / Javier Esparza ; Pierre Fraigniaud ; Thore Husfeldt ; Elias Koutsoupias. Springer, 2014. s. 375-386 (Lecture notes in computer science, Bind 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

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater