(Department of Computer Science, University of Manitoba)
Labeling Graphs For Broadcast In Radio Networks
|Date||Friday, November 30, 2018|
Performing tasks in radio networks can be difficult due to signal interference that can occur due to simultaneous transmissions, made worse by the fact that nodes in a network behave without knowledge of the network topology. By modeling the network as a graph and assuming that each node has been assigned a unique integer label, a lot of progress has been made in designing algorithms for important tasks. This is because the labels can be used to coordinate the behaviour of the nodes, in particular, to break symmetries that might exist in the underlying graph. The question is: do we really need the labels to be distinct? Given a graph G, what is the fewest number of different labels we can assign to the nodes of G such that a given task is still algorithmically solvable? In this talk, I'll consider this question for the Broadcast task in radio networks. No prior knowledge about these topics will be assumed.