Labeling schemes for bounded degree graphs

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

David Adjiashvili, Noy Galil Rotbart

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.

OriginalsprogEngelsk
TitelAutomata, languages, and programming : 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II
RedaktørerJavier Esparza, Pierre Fraigniaud, Thore Husfeldt, Elias Koutsoupias
Antal sider12
ForlagSpringer
Publikationsdato2014
Sider375-386
ISBN (Trykt)978-3-662-43950-0
ISBN (Elektronisk)978-3-662-43951-7
DOI
StatusUdgivet - 2014
BegivenhedInternational Colloquium on Automata, Languages, and Programming 2014 - Copenhagen, Danmark
Varighed: 8 jul. 201411 jul. 2014
Konferencens nummer: 41

Konference

KonferenceInternational Colloquium on Automata, Languages, and Programming 2014
Nummer41
LandDanmark
ByCopenhagen
Periode08/07/201411/07/2014
SponsorCWI Amsterdam, EATCS, Springer-Verlag, Statens Kunstfond
NavnLecture notes in computer science
Vol/bind8573
ISSN0302-9743

ID: 161625309