Mader proved that every loopless undirected graph contains a pair (u,v) of nodes such that the star of v is a minimum cut separating u and v. Nagamochi and Ibaraki showed that the last two nodes of a max-back order" form such a pair and used this fact to develop an elegant min-cut algorithm. M. Queyranne extended this approach to minimize symmetric submodular functions. With the help of a short and simple proof
On minimizing symmetric set functions / Rizzi, Romeo. - ELETTRONICO. - (1999), pp. 1-5.
On minimizing symmetric set functions
Rizzi, Romeo
1999-01-01
Abstract
Mader proved that every loopless undirected graph contains a pair (u,v) of nodes such that the star of v is a minimum cut separating u and v. Nagamochi and Ibaraki showed that the last two nodes of a max-back order" form such a pair and used this fact to develop an elegant min-cut algorithm. M. Queyranne extended this approach to minimize symmetric submodular functions. With the help of a short and simple proofFile in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
tec55.pdf
accesso aperto
Tipologia:
Versione editoriale (Publisher’s layout)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
225.85 kB
Formato
Adobe PDF
|
225.85 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione
