SMART: Today's talk by Emanuele Fusco [Graph Coloring with Distance Constraints - Outerplanar Graphs]

[Giorgio Zanin]

Title           : Graph Coloring with Distance Constraints - Outerplanar Graphs

 

Speaker         : Emanuele Fusco

 

Date            : Monday, June 5, 2006

 

Venue & Time    : Aula Alfa, 113 Via Salaria. 3:00 PM

 

Abstract        : In this talk some slightly modified definitions of node coloring

will be presented. They arise from frenquency assignment problem

in wireless networks, which requires some additional care in order

to address physical interferences between adjacent frequencies and

to avoid hidden collisions.

The problems presented are in general NP-Hard, so much work has

been done to find restricted graph classes for which they are

polynomial time solvable. In particular, outerplanar graphs are one

of those classes. We will see however that exact solutions are not

practical due to huge hidden constant factors, and we therefore

present an approximation algorithm with guaranteed worst case

performance.

 

 

http://www.dsi.uniroma1.it/smart/

 

Please feel free to extend this invitation to other interested people.