Pagina Radice del Progetto: Timetabling

Dato un grafo bipartito G=(V,E), vogliamo assegnare ad ogni arco un colore, in modo che ogni due archi con un estremo in comune abbiano colore diverso. Se il grado massimo di G è $\Delta$, è noto che è sempre possibile colorare gli archi di G utilizzando al più $\Delta$ colori. Vorremmo codificare in noweb e c++ gli algoritmi con i migliori limiti asintotici di complessità per questo problema.

Come riferimento, potete partire dai seguenti lavori qui disponibili in formato .ps:

Kapoor, Ajai; Rizzi, Romeo
Edge-coloring bipartite graphs.
J. Algorithms 34 (2000), no. 2, 390--396.

Rizzi, Romeo
Finding $1$-factors in bipartite regular graphs, and edge-coloring bipartite graphs.
to appear on SIAM Journal on Discrete Mathematics.

created: 30 Aprile 2001
updated: 30 Aprile 2001