Vegyes hipergráfok: struktúrák és algoritmusok

Pannon Egyetem

Informatikai Tudományok Doktori Iskola

Tuza Zsolt

informatikai tudományok

A hipergráfoknak (halmazrendszereknek) lehetőleg sok színnel történő csúcsszínezéseit Ahlswede vizsgálta elsőként, információs csatornák adatátvitelével kapcsolatban. Később Voloshin bevezette a „vegyes hipergráf” struktúrát, és annak számos alkalmazását is leírta. A modell alapgondolata a megenge¬dett csúcspartícióknak két, ellentétes szerepű halmazrendszerrel történő korlátozása, amelyek külön-külön a minél több ill. minél kevesebb szín használatát kényszerítik, de tényleges hatásuk rendszerint csak együttesen mutatkozik meg. A szakterület ismert eredményeit és módszereit rész¬letesen tárgyalja az [1] monográfia, az azóta megjelent eredményeket és aktuális problémákat a [2] áttekintő cikk. A struktúrára és algoritmikus bonyolultságra egyaránt számos fontos és érdekes nyitott kérdés vonatkozik.

A kutatási téma előzményei:
[1] V. Voloshin: Coloring Mixed Hypergraphs – Theory, Algorithms and Applications. Fields Institute Monographs Vol. 17, Amer. Math. Soc., 2002.
[2] Zs. Tuza, V. Voloshin: Uncolorable mixed hypergraphs. Discrete Applied Mathematics 99, 2000, 209–227.

1 fő

Pannon Egyetem, MIK, Rendszer- és Számítástudományi Tanszék

2012-08-31

angol