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.
