[Dottorcomp] Seminario 19 maggio 2026 - 16:00, Aula C29 e Zoom su Basi di cicli minime nei grafi orientati: teoria, complessità e odio per le ciambelle tenuto

[GABOR RICCARDI]

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>