B O S T O N   U N I V E R S I T Y
                      Computer Science Department
                          C O L L O Q U I U M
                     Wednesday, November 20, 3:00 PM
                       (Coffee served at 2:45 PM)
                         Seminar Room / MCS 135
 
            Conflict-Free Colorings of Simple Geometric Regions 

                             Zvika Lotker
                          Tel-Aviv University

We introduce and study a new coloring problem that we call Minimum
Conflict-Free Coloring (Min-CF-Coloring).

Cellular networks are heterogeneous networks with two different
types of nodes: base-stations (that act as static servers) and
clients (which are mobile). The base stations are interconnected
by an external fixed backbone network, clients are connected only
to base-stations; links between clients and base-stations are
implemented by radio links. Fixed frequencies are assigned to
base-stations to enable links to clients. Clients, on the other
hand, continuously scan frequencies in search of a base-station
with good reception. This scanning takes place automatically and
enables smooth transitions between links when a client is mobile.
Consider a client that is within the reception range of two
base-stations. If these two base-stations are assigned the same
frequency, then mutual interference occurs, and the links between
the client and each of these conflicting base-stations are
rendered too noisy to be used. A base-station may serve a client
provided that the reception is strong enough and interference from
other base stations is weak enough. The fundamental problem of
frequency assignment in cellular networks is to assign frequencies
to base-stations so that every client is served by some
base-station.  The goal is to minimize the number of assigned
frequencies since the spectrum is limited and costly. We call this
problem Min-CF-Coloring. In my talk I will present some new
results concerning Min-CF-Coloring.

This is a joint work with Guy Even Zvi Lotker Dana Ron Shakhar
Smorodinsky.

Host: Boaz Patt-Shamir

-------------------------------------------------------------------------
For colloquium info, including directions, see
http://www.cs.bu.edu/colloquium
-------------------------------------------------------------------------