Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Informatica e Sistemistica - DIS
via Salaria 113, piano secondo
Aula C2

Abstract:
La L(h,1)-colorazione, h=0, 1, 2, e' una classe di problemi di colorazione che nasce dal problema dell'assegnamento di frequenze in reti radio multihop, in cui nodi adiacenti devono essere colorati con colori (etichette numeriche) che distino di almeno h mentre nodi a distanza 2 devono ricevere colori diversi. Questo problema e' noto essere NP-completo, anche se limitato a grafi planari. Ha quindi senso studiare delle sottoclassi di grafi: qui ci focalizziamo sulla L(h,1)-colorazione di grafi outerplanar e di tasselazioni regolari del piano. In particolare, in merito alla tasselazione, diamo un unico algoritmo parametrico per colorare in modo ottimo una qualunque tasselazione regolare. Per quello che riguarda i grafi outerplanar di massimo grado D, mostriamo un algoritmo che migliora le limitazioni superiori precedentemente note: passiamo da D+9, D+5 e D +3 a D + 3, D +1 e D colori per i valori di h pari a 2, 1 e 0 rispettivamente. Infine, studiamo il caso speciale D=3, dando luogo a risultati inattesi.