Labeling schemes for bounded degree graphs
Noy Rotbart
20 September 2013, 14:00 - 20 September 2013, 15:00 Salle/Bat : 455/PCRI-N
Contact : noyro@diku.dk
Activités de recherche :
Résumé :
Labeling schemes, a subject closely related to induced and induced universal graphs, have been studied extensively in the theoretical computer science community over the last 2 decades.
In my talk I will introduce the concept and present new results for graphs of bounded degree ∆. In particular I will present the following results:
1. An optimal log n + O( log ∆) adjacency labeling scheme for bounded degree trees.
2. An optimal (⌊∆⌋/2+1)logn adjacency labeling scheme for general bounded degree graphs.
3. An improved adjacency labeling scheme for general graphs with bounded degree √(n) < ∆ ≤ n/5 (using combinatorial number system).
The talk will conclude with a survey of open problems in the field.
