Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
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.

Pour en savoir plus :
Séminaires
Refining Transitive and Pseudo-Transitive Relation
Web data management
Monday 24 January 2022 - 13:00
Salle : 455 - PCRI-N
Shuai Wang .............................................

Discovering Causal Rules in Knowledge Graphs using
Integration of Data and Knowledge
Monday 10 January 2022 - 15:00
Salle : 455 - PCRI-N
Lucas Simonne .............................................

Meta-Learning for Few-Shot Link Prediction in Know
Integration of Data and Knowledge
Monday 13 December 2021 - 13:00
Salle : 455 - PCRI-N
Taha Halal .............................................

Knowledge Graph Refinement based on Triplet BERT-N
Web data management
Monday 29 November 2021 - 13:00
Salle : 455 - PCRI-N
Armita Khajeh Nassiri .............................................

A Hyper-graph Approach for Computing EL+-Ontology
Automated Reasoning
Monday 15 November 2021 - 13:00
Salle : 445 - PCRI-N
Hui Yang .............................................