Discrete Mathematics and Optimization Seminar


CHRISTOPHE PAUL
LIRMM - CNRS
Monday October 23rd at 4.30pm
Burnside 1205



Title. Distance labeling schemes.

Abstract. The notion of informative labeling scheme was introduced by Peleg in the context of graph representation and
has applications in network functions such as routing. Let f be a function on a subset of vertices (eg
adjacency). An f labeling scheme labels the vertices of the given graph in such a way that f(W) can be inferred
efficiently for any subset W of vertices by merely inspecting the labels of the vertices of W and wihtout any additional
information. Adjacency function, distance function, routing function and other fits in this framework.

In this talk we review some results on distance labeling schemes. The talk will consider some path-like graph
families (such as AT-free graphs, interval graphs) and tree-like graphs (such as k-chordal graphs, distance hereditary graphs).