Teoria e problemi di matching

ROMEO RIZZI,
A short proof of Konig's matching theorem,
accepted by Journal of Graph Theory
descrizione: ``In ogni grafo bipartito la massima cardinalitá di un matching é pari alla minima cardinalitá di un node cover.'' - qui lo si dimostra succintamente senza ricorrere ai cammini aumentanti. La stessa dimostrazione consente inoltre di ottenere in tutta semplicitá la ben piú impegnativa generalizzazione di Egerváry al caso pesato.

ROMEO RIZZI,
Indecomposable r-graphs and some other counterexamples,
Journal of Graph Theory 32 (1) (1999) 1-15.
descrizione: Un r-grafo é un punto intero nel cono generato proiettando il politopo dei matching perfetti in un grafo completo. Noi diamo dei controesempi a delle congetture di Seymour e di altri ricercatori e mostriamo come le altezze per le basi di Hilbert di questi coni non siano limitate da costante alcuna. Paul Seymour in persona mi ha chiesto di sottomettere questo lavoro al suo giornale spendendo significativi apprezzamenti.

RICHARD C. BREWSTER, PAVOL HELL, SARAH H. PANTEL, ROMEO RIZZI, ANDERS YEO,
Packing paths in digraphs,
accepted by Journal of Graph Theory
descrizione: Un matching puó essere considerato come una collezione di copie di K₂disgiunte sui nodi. Una generalizzazione del probema di trovare un matching di massima cardinalitá é pertanto quella di, fissata una famiglia di grafi ${\cal G}$, e dato un certo grafo in input G, trovare una collezione di sottografi di G disgiunti sui nodi, tutti isomorfi a qualche membro di ${\cal G}$. Questo problema, noto come il ${\cal G}$-packing problem, ha ricevuto molta attenzione nella letteratura. Tuttavia poco era noto nel caso ${\cal G}$sia una famiglia di grafi diretti, se non che questa cornice fosse piú generale. In questo lavoro si é dato inizio all'esplorazione del caso in cui ${\cal G}$é una famiglia di grafi diretti. In particolare, si é affrontato e completamente caratterizzato il caso in cui ${\cal G}$ é una famiglia di cammini diretti. Il problema di coprire il maggior numero di nodi di G é risolvibile in tempo polinomiale se ${\cal G}$ é riducibile o alla famiglia ${\cal G}=\{\vec{P}_1\}$o alla famiglia ${\cal G}=\{\vec{P}_1,\vec{P}_2\}$. In tutti gli altri casi il problema risulta essere $N\!P$-completo.

ROMEO RIZZI,
The T-join cone,
in preparation
descrizione: Forniamo la descrizione del cono dei T-joins tramite un sistema di diseguaglianze lineari. Ció generalizza la ben nota descrizione di Seymour per il cono dei cicli.

ROMEO RIZZI,
Efficiently solvable extensions of the MS-matching problem,
in preparation
descrizione: Vogliamo accoppiare macchine e lavori con il vicolo che se un certo lavoro (slave) viene eseguito allora anche un altro lavoro (il suo master) viene eseguito. Obbiettivo: trovare un accoppiamento che massimizzi il numero di lavori assegnati a macchine. Questo é un problema squisitamente di Ricerca Operativa. Purtroppo il problema é NP-hard in generale e tuttavia é di interesse risolverlo anche in casi particolari. Una formula min-max era nota per un caso particolare. Noi estendiamo l'ambito di validitá di tale formula e consideriamo generalizzazioni di casi risolvibili mostrando come esse stesse siano risolvibili.

ROMEO RIZZI,
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 $\Delta$-regolare in un suo fratellino minore. La dimostrazione é ora per induzione ed é diretta.

ROMEO RIZZI,
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ú $\Delta$ 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.

ROMEO RIZZI,
Simple proofs for the bipartite matching politope,
Rapporto Interno n.5,
Dipartimento di Matematica Pura ed Applicata,
Università di Padova, Italia.
descrizione: Questo rapporto interno vuole offrire una trattazione semplice ed elegante per il problema del matching su grafi bipartiti. Abbiamo raccolto qui alcune nostre dimostrazioni originali ed altre prese in prestito. Il lavoro va inteso come sussidio alla didattica. I principali risultati del settore vengono ottenuti senza sforzo.

ROMEO RIZZI,
Minimum T-cuts and optimal T-pairings,
submitted
descrizione: Diamo una formula di min-max per la minima cardinalitá di un T-taglio. Mostriamo inoltre come nel minimal TDI system per il poliedro dei T-tagli siano presenti disuguaglianze a coefficienti comunque grandi.

ROMEO RIZZI,
A Simple Minimum T-Cut Algorithm,
in preparation
descrizione: Diamo un' algoritmo diretto per il computo di un minimo T-taglio. L'algoritmo, pur basandosi sulle stesse proprietá di submodulariaá ed uncrossing al pari delle soluzioni precedenti, purtuttavia presenta dei vantaggi di semplicitá e praticitá. L'algoritmo reperisce inoltre un T-accoppiamento ottimo, fornendo quindi dimostrazione algoritmica della ``buona caratterizzazione'' da noi fornita nel lavoro ``Minimum T-cuts and optimal T-pairings''.