NOTE the special time

-----------------------------------------------------------------------
                   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
                     Monday, September 9, 10:00 AM
                       (Coffee served at 9:45 AM)
                         Seminar Room / MCS 135

             Routing and Path Coloring in All-Optical Networks

                            Stathis Zachos
                    Brooklyn College of CUNY and NTUA

                              Abstract

The rapid development of optical fiber technology eventually will lead to
networks consisting solely of optical connections, the so called all-optical
networks. Problems arising regarding routing and bandwidth allocation in such
networks can be viewed  as routing and path coloring problems in graphs, the
majority of which are NP-hard. Two of the most widely studied relevant
problems are the path coloring problem (PC) and the maximum path coloring
problem (MaxPC).
     In PC a graph G and a set of paths P are given and the goal is to color
all paths in P with the least possible colors, so that  overlapping paths are
not assigned the same color. The problem is NP-hard and cannot be
approximated within a constant factor for general topologies. However, it is
optimally solvable in chains, and as we show also in bounded degree trees and
generalized trees of bounded degree. On the other hand, there exists a 1.5
approximation algorithm for PC in rings, as well as one that achieves a 1.36-
approximation with high probability. In  trees a 4/3 approximation algorithm
exists, which is also the best possible unless P=NP.  Studying PC in directed
topologies is also interesting. In some cases the problem in a directed
topology can be reduced to an undirected one. This is not possible for
directed trees, and the best approximation factor found so far is 5/3.
    A variation of PC, which  is also widely studied, is RPC, in which
instead of a set of paths a set of connection  requests is given. These
requests must be routed via paths which are to be colored. In acyclic
topologies PC and RPC coincide. In rings a 2-approximation algorithm exists,
as well as one that achieves a 1.68 approximation with high probability.
Furthermore, in trees of rings a combination of the algorithms for trees and
rings can yield a 3-approximation. We also investigate RPC in directed
topologies.
    In MaxPC, in addition to the graph G and the set of paths P,  a number w
of available colors is given. The goal is to color as many paths in P as
possible, using at most w colors, under the restriction that overlapping
paths are not assigned the same color. This problem is also NP-hard and non
approximable within a constant factor for general graphs. In chains it is
optimally solvable, while in rings and trees we obtain 1.5 and 1.58
approximation factors respectively. In directed trees the problem is solved
within a 2.22 approximation factor. As far as the  routing variation of the
problem (MaxRPC) is concerned, we present a 3/2 approximation algorithm for
rings, while in directed rings the best factor we have achieved so far is
11/7.
 Better approximations may be found in the future for many of the topologies
mentioned above. Furthermore, there are several variants of these problems
related to all optical networks. Thus, research around this subject is active
and expanding.

Host: George Kollios

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