Problemi di taglio minimo


ROMEO RIZZI,
On minimizing symmetric set functions,
accepted by Combinatorica
descrizione: Talvota una dimostrazione semplice é la base di una nuova generalizzazione. É il caso di questo lavoro dove si é data una dimostrazione del tutto elementare di un lemma un po' magico che legava certi ordinamenti dei nodi di un grafo con delle coppie di nodi che erano buone, nel senso che consentivano di ridurre il problema del taglio minimo. Il metodo era stato generalizzato precedentemente da Queyranne per la minimizzazione di funzioni simmetriche e submodulari, ma i suoi argomenti erano complessi e poco trasparenti. Noi si é data una dimostrazione induttiva talmente elementare da non richiedere quasi alcuna ipotesi. Ció ha portato a definire una classe di funzioni sulla base delle sole proprietá utilizzate ed a derivare poi le varie generalizzazioni precedentemente conosciute come casi particolari della nostra analisi. Il tutto in grande semplicitá. Questo lavoro mi ha meritato l'apprezzamento da parte dei piú insigni studiosi nel settore.


ROMEO RIZZI,
Excluding a simple good pair approach to directed cuts,
accepted by Graphs and Combinatorics
descrizione: Un controesempio non particolarmente difficile ma tecnicamente necessario. Recentemente, un nuovo ed efficace approccio era stato proposto per il problema del taglio minimo su grafi non-diretti. Volevamo assicurarci che lo stesso approccio non poteva essere esteso in quanto tale al caso di grafi diretti.


ROMEO RIZZI,
Efficient implementations of greedy order algorithms,
submitted
descrizione: Nel caso del problema del taglio minimo, Nagamochi ed Ibaraki avevano mostrato come alcuni accorgimenti fossero effettivi nel migliorare le performances dell'algoritmo da loro stessi proposto per il problema. Questa analisi non era stata possibile per le successive generalizzazioni del loro approccio causa l'eccessiva complessitá delle stesse. A seguito del nostro successo in ``On minimizing symmetric set functions'', tale strada diviene peró percorribile. Qui noi mostriamo come gli accorgimenti di Nagamochi ed Ibaraki possano essere di fatto inclusi nell'impostazione assiomatica da noi proposta nel lavoro di cui sopra. Di fatto il nostro approccio consente persino di perfezionare da un lato, e di semplificare dall'altro, gli accorgimenti in questione, Tali perfezionamenti si applicano anche nel caso particolare ed originale del problema del taglio minimo.


ROMEO RIZZI,
A new method for finding cuts of minimum weight,
in preparation
descrizione: Forniamo un metodo nuovo ed invero semplice per il problema del taglio minimo in grafi. Il metodo generalizza al problema del taglio minimo in ipergrafi. Inoltre l'idea base promette bene in quanto ad applicabilitá ad altri problemi di edge-connectivity.



2000-02-14 © Dipartimento di Matematica - Università di Trento