Tata Institute of Fundamental Research
The Space Complexity of Sum Labelling
STCS Student Seminar
Speaker:
Kshitij Gajjar (National University of Singapore)
Organiser:
Neha Sangwan
Date:
Friday, 1 Oct 2021, 17:15 to 18:15
Venue:
(Scan to add to calendar)
Abstract:
How does one store a graph in the database? Typically the vertices are labelled by a set {1, 2, ..., n}. The edges can be denoted in many different ways: adjacency matrix, incidence matrix, adjacency list, to name a few. But what if the vertices are labelled in a more creative way, such that the labels of the vertices themselves denote their adjacencies? This eliminates the need for storing the edges! This topic is part of a heavily researched field called graph labelling, with connections to coding theory and information theory. In this talk, we will explore a type of graph labelling known as sum labelling. This is joint work with Henning Fernau (https://eccc.weizmann.ac.il/report/2021/114).
Zoom Link: https://zoom.us/j/93889521556pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09
| Speaker: | Kshitij Gajjar (National University of Singapore) |
| Organiser: | Neha Sangwan |
| Date: | Friday, 1 Oct 2021, 17:15 to 18:15 |
| Venue: |
(Scan to add to calendar)
Abstract:
How does one store a graph in the database? Typically the vertices are labelled by a set {1, 2, ..., n}. The edges can be denoted in many different ways: adjacency matrix, incidence matrix, adjacency list, to name a few. But what if the vertices are labelled in a more creative way, such that the labels of the vertices themselves denote their adjacencies? This eliminates the need for storing the edges! This topic is part of a heavily researched field called graph labelling, with connections to coding theory and information theory. In this talk, we will explore a type of graph labelling known as sum labelling. This is joint work with Henning Fernau (https://eccc.weizmann.ac.il/report/2021/114).
Zoom Link: https://zoom.us/j/93889521556pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09
Zoom Link: https://zoom.us/j/93889521556pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09