Monday October 23rd at 4.30pm

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).