Megszorított Feedback arc set és sorbarendezési feladatok

Témavezető: Madarasi Péter
ELTE TTK, Operációkutatási Tsz.
email: madarasip@staff.elte.hu

Projekt leírás

Egy élsúlyozott irányított gráf minden v csúcsára adott egy f(v) alsó és egy g(v) felső korlát. Szeretnénk eldönteni, hogy létezik-e olyan csúcssorrend, amely szerint minden v csúcs bal súlyozott kifoka f(v) és g(v) között van. A fenti kérdés NP-teljes, viszont polinom időben megoldható, amikor vagy csak alsó, vagy csak felső korlát adott. Speciális esetként az is eldönthető, hogy egy irányított gráf felbomlik-e egy befenyves és egy aciklikus gráf uniójára.

A projekt célja ezen kérdéskör és néhány kapcsolódó megszorított Feedback Arc Set feladat vizsgálata. Ilyen feladat például, hogy mikor bontható fel egy irányított gráf egy aciklikus és egy befenyő uniójára?

Előfeltételek

Elvárás a gráfelméleti alapok és az angol szakmai nyelv ismerete.

Korábbi hallgatók