School Seminars and Colloquia

Linear and cyclic metric labelling problems for complete m-ary trees

Discrete Structures and Algorithms (Seminar)

by Kelvin Yang Li


Institution: The University of Melbourne
Date: Tue 16th August 2011
Time: 11:00 AM
Location: Russell Love Theatre, Richard Berry Building

Abstract: The frequency assignment problem is concerned with assigning frequency to each transmitter such that the maximum span of the frequency is minimized under some distance constraints. In reality the closer two transmitters are, the larger the separation between their frequencies are required to be. Such problems can be turned into graph labelling problems. Given a positive integer h, an L(h,1,1)-labelling of a graph is an assignment of non-negative integers to its vertices such that adjacent vertices receive labels differing by at least h and vertices with distance 1 or 2 apart receive distinct labels. The span of such a labelling is the difference between the maximum and minimum labels used. The objective is to find the minimum span over all L(h,1,1)-labellings.

In this talk we will discuss recent results on the L(h,1,1)-labelling problem and its cyclic version for complete m-ary trees.