Leírás
Bonylultságelmélet szeminárium
Absztrakt: Az előadásomat Alexandros Hollender és Paul W. Goldberg,
"The Complexity of Multi-source Variants of the End-of-Line Problem,
and the Concise Mutilated Chessboard" című cikkéből tartom. Az előadás
fő témája a PPAD-teljes End-of-Line probléma különböző
általánosításainak és ezek bonyolultságának vizsgálata lesz. Az
End-of-Line probléma a következő: Adott egy G irányított gráf, ahol
minden csúcs befoka és kifoka is legfeljebb 1, továbbá adott egy
forrás. A feladatunk egy másik forrás/nyelő keresése. Az előadás során
ennek több verziójával is fogunk foglalkozni, például amikor több
forrás és több nyelő is adott, vagy amikor több forrást/nyelőt kell
keresnünk, illetve belátjuk ezekről is, hogy PPAD-teljesek.
For Teams access please contact Zoltán Király (kiraly[at]cs.elte.hu).