[Dottorcomp] Correzione orario seminario del 19 maggio 2026 “Basi di cicli minime nei grafi orientati: teoria, complessità e odio per le ciambelle”

[GABOR RICCARDI]

Gentili tutti,

correzione alla precedente comunicazione: nella scorsa mail erano indicati
due orari distinti.
L’orario corretto del seminario è il seguente:

Seminario – 19 maggio 2026, ore 16:00
Aula C29 e su Zoom
“Basi di cicli minime nei grafi orientati: teoria, complessità e odio per
le ciambelle”

Scusate la doppia mail e cordiali saluti,
Gabor Riccardi

Il mar 12 mag 2026, 11:02 GABOR RICCARDI <
gabor.riccardi01 a universitadipavia.it> ha scritto:

> data e luogo:  19 maggio dalle 11:00 alle 12:00 in Beltrami o Zoom
> <https://unipv-it.zoom.us/j/92601608696?pwd=Rz6WMyz004kCO2Wr3bw27FMAZwYfjm.1>
>
> titolo seminario: Basi di cicli minime nei grafi orientati: teoria,
> complessità e odio per le ciambelle tenuto
>
> speaker: Gabor Riccardi
>
> abstract: Le basi di cicli forniscono rappresentazioni compatte dello
> spazio dei cicli di un grafo e hanno varie applicazioni nell’ottimizzazione
> combinatoria: nell'ottimizzazione delle reti elettriche e nelle
> formulazioni di programmazione intera, come il Periodic Event Scheduling
> Problem (PESP). In questo seminario facciamo una introduzione alla teoria
> delle basi di cicli, rivedendo le definizioni fondamentali e le proprietà
> strutturali dello spazio dei cicli.
>
> Presentiamo inoltre nuovi risultati di esistenza e di complessità per le
> basi di cicli debolmente e strettamente fondamentali nel caso in cui
> l’orientamento degli archi nei cicli debba coincidere con quello del grafo
> orientato (forward cycle bases).
>
> Infine, discutiamo il problema della Base di Cicli Intera, la cui
> complessità di minimizzazione rimane una delle principali questioni aperte
> nell’ambito. Nei grafi planari è noto un fenomeno strutturale sorprendente:
> nonostante il vincolo aggiuntivo di integrità, il problema della base di
> cicli intera minima rimane risolvibile in tempo polinomiale. Generalizzando
> questa osservazione, studiamo la famiglia di grafi per cui gli algoritmi di
> basi minime di cicli restituiscono sempre una base di cicli intera,
> mostrando che essa è caratterizzata da una famiglia finita di forbidden
> minors. L’identificazione esplicita di questa famiglia potrebbe fornire
> importanti esempi da utilizzare in una riduzione per il problema della base
> di cicli intera minima
> link seminario:
>  https://sites.google.com/view/comp-opt/news/seminars#h.ndh2zfcquowv
> <https://sites.google.com/view/comp-opt/news/seminars#h.ndh2zfcquowv>
>
>
>