MFCS 2000
 25th International Symposium on Mathematical Foundations of Computer Science
 August 28 - September 1, 2000
 Bratislava, Slovak Republic, Europe

 Algorithmic Foundations of Communication Networks

### FREQUENCY ALLOCATION ALGORITHMS AND RADIOCOLORING

Speaker: Paul Spirakis

The resource of frequencies is a scarce one and its efficient allocation is an important issue in wireless communications technology. We discuss here recent progress in the Frequency Allocation Problem (FAP), including the important special cases of Radiocoloring (distance two constraints) and Radiolabelling (all frequencies different with avoidance of interference constraints). We discuss the complexity and efficient methods to solve these problems, and their connection to important combinatorial problems in optimization such as TSP, Hamilton lines, Coloring, Cliques in graphs etc.

Speaker: Pierre Fraigniaud

The purpose of compact routing is to provide a labeling of the nodes of a network, and a way to encode the routing tables so that routing can be performed efficiently (e.g., on shortest paths) while keeping the memory-space required to store the routing tables as small as possible. In this paper, we answer a long-standing conjecture by showing that compact routing can also help to perform distributed computations. In particular, we show that a network supporting a shortest path interval routing scheme allows to broadcast with an O(n) message-complexity, where n is the number of nodes of the network.

This is a joint work with Cyril Gavoille, from Univ. Bordeaux, and Bernard Mans, from Mcquarie Univ., Sydney.

### DESIGN ISSUES IN ATM AND OPTICAL NETWORKS

Speaker: Shmuel Zaks

I describe graph-theoretic models for ATM networks and for optical networks. Within these models I describe design problems, describe some results, and discuss future research directions.

Regarding ATM networks, I give a short summary for the virtual path layout problem, and describe in some detail the use of duality, and especially the use of high dimensional spheres, in deriving and analyzing optimal designs for chain and ring networks. The use will be demonstrated in simplifying proofs of known results (like the best average case designs for the shortest paths case), enabling derivation of new results (like the best average case designs for the general paths case), and improving existing results (like for the all-to-all problem). This part is based on works co-authored with Marcelo Feighelstein, Ornan Gerstel, Avishai Wool, Israel Cidon and Yefim Dinitz.

Regarding optical networks, I'll describe the ring partition problem, that stems from a survivability condition in the network. I'll discuss negative results regarding the tractability and approximability of this problem, and an approximation algorithm for it. This part is based on a work co-authored with Tamar Eilam and Shlomo Moran.

### ALGORITHMIC DEVELOPMENTS IN INTERVAL ROUTING

Speaker: Peter Ruzicka

Communication problems are studied as simple path systems satisfying given communication patterns in a point-to-point network. Efficiency parameters of path systems such as congestion, dilation, compactness and buffer-size are considered. We focus on the current algorithmic research directions and the various techniques that are used in the communication schemes design. Special interest is devoted to (multidimensional) interval routing schemes. Open problems related to this line of research and an overview of several related research directions are also given.

### DISTANCE LABELING SCHEMES FOR GRAPHS

Speaker: David Peleg

Distance labeling schemes are schemes for labeling the nodes of a graph in a way that will allow one to efficiently compute the distance between any two nodes directly from their labels (without using any additional information). Our main interest is in the minimal length of labels needed.

The talk will survey recent results concerning distance labeling schemes for graphs, including upper and lower bounds for several interesting graph families. We will also discuss open problems and directions for future research.

Department of Computer Science, Faculty of Mathematics and Physics, Comenius University, Bratislava