Edge-coloring bipartite graphs,
accepted by Journal of Algorithms
descrizione: Battiamo (o meglio battevamo) il record asintotico sulla complessitá computazionale per produrre una soluzione ottima al problema di colorare gli archi di un grafo bipartito col minor numero possibile di colori. Inoltre davamo un algoritmo di complessitá lineare (e meglio di cosí non é ovviamente possibile per una macchina sequenziale) per produrre una soluzione che impieghi solamente un colore in piú che non la soluzione ottima.
Finding 1-factors in bipartite regular graphs, and edge-coloring bipartite graphs,
submitted
descrizione: Questo lavoro migliora ulteriormente lo stato del problema di colorare gli archi in un grafo bipartito con al piú
colori.
Il collo di bottiglia per la complessitá
computazionele dell'algoritmo proposto
da Kapoor
e Rizzi in ``Edge-coloring bipartite graphs''
era la procedura presa in prestito da Hopcroft e Cole
per il reperimento di un accoppiamento perfetto
in un grafo bipartito e regolare.
Qui si migliora su questa procedura
grazie a degli argomenti algebrici.
In lavoro mette in luce il legame tra
la fattorizzazione di grafi e la fattorizzazione
di numeri interi.
Improving a Family of Approximation Algorithms to Edge Color Multigraphs,
Inf. Proc. Lett. 68 (1998) 11-15.
descrizione: Coloriamo gli archi di un grafo in modo che archi incidenti ad uno stesso nodo abbiano colori diversi. Evidentemente non possiamo sperare di impiegare meno di
colori,
ove
é il massimo grado di un nodo.
Il teorema di Vizing dice che
possiamo sempre farcela
con 
colori.
Tuttavia ció non é piú vero
ove si consideri la possibilitá di avere archi paralleli
tra una stessa copia di nodi.
É stato tuttavia definito
un parametro 
,
di facile computazione,
che costituisce una miglior stima inferiore
che non
sul numero di colori necessari.
Delle famigerate congetture
degli anni 80
affermano poi che ce la si puó sempre
fare con al piú 
colori.
In ogni caso,
il problema di colorare
gli archi con pochi colori ha importanti applicazioni.
Questo spiega la serie di algoritmi che sono stati
via via presentati per impiegare al piú
colori.
Purtroppo, ogni nuovo algoritmo se ne esce
con un valore di 
piú vicino ad 1,
ma anche con una complessitá computazionale
e di implementazione sempre maggiore.
Noi abbiamo mostrato come con un semplice trucco fosse possibile
migliorare il grado di approssimazione per ciascuno
degli algoritmi sinora proposti senza incrementarne
la complessitá.
Ció consente di dedurre la validitá della congettura
di cui sopra per
.
Konig's Edge Coloring Theorem without augmenting paths,
Journal of Graph Theory 29 (1998) 87.
descrizione: Il teorema dei balli é uno di quei risultati con cui Konig ha posto le basi della teoria dei grafi per come oggi é conosciuta. Il teorema ha applicazioni dirette in problemi di scheduling e timetabling, ma anche in discipline piú lontane come la statistica. Nonostante la sua importanza, il risultato veniva derivato come corollario di un'altro fondamentale teorema di Konig. Noi introduciamo un'operazione elementare che trasforma un grafo bipartito e
-regolare
in un suo fratellino minore.
La dimostrazione é ora per induzione
ed é diretta.
Impaccando T-tagli e T-giunti,
Bollettino Sezione B dell'Unione Matematica Italiana,
Fascicolo speciale dedicato alle tesi di dottorato (8) 1-A Suppl. (1998) 201-204.
descrizione: L'UMI offriva uno spazio di 4 pagine per presentare la tesi di dottorato nel suo prestigioso bollettino. In italiano, e con delle figure, ho cercato di attirare l'attenzione del lettore introducendo solo un paio dei problemi affrontati nella mia tesi. Risultato? Un successo: qualcuno ha risposto chiedendomi copia della tesi.
