Témakiírások
Vegyes hipergráfok: struktúrák és algoritmusok
témakiírás címe
Vegyes hipergráfok: struktúrák és algoritmusok
intézmény
doktori iskola
témakiíró
tudományág
témakiírás leírása
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 megengedett 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 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:
V. Voloshin: Coloring Mixed Hypergraphs – Theory, Algorithms and Applications. Fields Institute Monographs Vol. 17, Amer. Math. Soc., 2002.
Cs. Bujtás, Zs. Tuza: Maximum number of colors: C-coloring and related problems. Journal of Geometry 101, 2011, 83–97 Uncolorable mixed hypergraphs.
Cs. Bujtás, Zs. Tuza, V. Voloshin: Hypergraph coloring. In: Topics in Chromatic Graph Theory (L. W. Beineke and R. J. Wilson, eds.), Encyclopedia of Mathematics and Its Applications Vol. 156, 2010, 230–254.
A kutatási téma előzményei:
V. Voloshin: Coloring Mixed Hypergraphs – Theory, Algorithms and Applications. Fields Institute Monographs Vol. 17, Amer. Math. Soc., 2002.
Cs. Bujtás, Zs. Tuza: Maximum number of colors: C-coloring and related problems. Journal of Geometry 101, 2011, 83–97 Uncolorable mixed hypergraphs.
Cs. Bujtás, Zs. Tuza, V. Voloshin: Hypergraph coloring. In: Topics in Chromatic Graph Theory (L. W. Beineke and R. J. Wilson, eds.), Encyclopedia of Mathematics and Its Applications Vol. 156, 2010, 230–254.
felvehető hallgatók száma
1 fő
helyszín
Pannon Egyetem, Műszaki Informatikai Kar, Rendszer- és Számítástudományi Tanszék
jelentkezési határidő
2016-09-22