Math-Sci Seminar

Speaker: Týnaz Ekim (Ecole Polytechnique Fédérale de Lausanne)

Title: Generalized vertex colorings and their applications to permutation graphs
        (ATTENTION TO UNUSUAL TIME, DAY AND PLACE)

Date: Wed 6 Sep, 2006
Time: 15:00
Place: Science Building, Room Z42

Abstract:

The vertex coloring problem (Min Coloring) is one of the most
extensively studied problems in graph theory and combinatorial
optimization. The reason is that Min Coloring has a wide range of
applications (telecommunications, timetabling, scheduling, etc.), but in
the meanwhile, it is extremely hard to solve it in an efficient way. Min
Coloring is the problem of covering the vertices of a given graph with a
minimum number of stable sets. In the literature, there are several
generalizations of Min Coloring. On one hand, they aim at covering an
even wider domain of applications. On the other hand, they give very
interesting combinatorial optimization problems.

We consider two generalizations of Min Coloring, namely Min
Split-coloring and Min Cocoloring, where the vertices of a given graph
are covered not only with stable sets but also with cliques. We first
define these problems and illustrate them on graphs. Also, we shortly
discuss their complexity situation. Then, we focus on two applications
of Min Cocoloring and Min Split-coloring on permutation graphs. The
first application occurs on a railway net. There are cars with different
labels on an input track and we want to rearrange them on an output
track in the order of increasing labels. To do so, we use parallel
tracks between the input and the output track. The objective is to use a
minimum number of parallel tracks to rearrange the cars. Min Coloring on
a permutation graph appropriately constructed is known to solve this
problem in an efficient way. We show that a slightly modified version of
this problem can be solved using Min Split-coloring on permutation
graphs. The second application concerns robotics. There are items of
different sizes on a corridor. A robot is collecting these items
respecting the constraint that a large item can not be put on a small
item (to ensure the stability of the pile). At the end of each trip
along the corridor, the robot unloads its charge to one of the storage
areas being situated at both ends of the corridor. The objective is to
minimize the number of trips along the corridor in order to collect all
the items. We model this problem as Min Split-coloring on a permutation
graph. Although it is NP-hard to solve it in an optimal way, we propose
polynomial time algorithms for some related questions.

Please visit http://home.ku.edu.tr/~sci-math for a schedule of
upcoming Science -Math seminars at Koc University.