The Maximum Edge q-Coloring Problem

Talk announcement
HIIT Seminar Kumpula, Friday December 2, Exactum B222

SPEAKER:
Alex Popa
Aalto University

TITLE:
The Maximum Edge q-Coloring Problem

ABSTRACT:
We consider the problem of coloring edges of a graph subject to the
following constraint: for every vertex v, all the edges incident to v
have to be colored with at most q colors. The goal is to find a coloring
satisfying the above constraint and using the maximum number of colors.

This problem has been studied in the past from the combinatorial and
algorithmic point of view. The optimal coloring is known for some
special classes of graphs. There is also an approximation algorithm for
general graphs, which in the case q=2 gives a 2-approximation. However,
the complexity of finding the optimal coloring was not known.

In this talk we present hardness results and approximation algorithms
for this problem. On the algorithmic side, we restrict to the case q=2,
since this is the most important in practice. We show a
5/3-approximation algorithm for graphs which have a perfect matching and
a 49/25-approximation algorithm for general graphs.

(joint work with Anna Adamaszek and Ola Svensson)

BIO:
I am a postdoctoral researcher at Aalto University in the group of Prof. 
Patric Östergård (started in October 2011). I have recently completed my
PhD at the University of Bristol, UK. I have done my undergraduate
studies at the University of Bucharest, Romania.

My research interests include (but are not limited to): classification 
problems for codes and designs, approximation algorithms and pattern
matching problems, and interactive systems and parallel computing.

You can find more information about publications, talks, academic and 
non-academic interests on my web page: www.cs.bris.ac.uk/~popa