(+36) 88 424 483

   8200 Veszprém, Egyetem utca 10. I. épület 9. emelet

   info@dcs.uni-pannon.hu

Kutatócsoportok

A kutatólaboratórium számos irányban folytat elméleti kutatásokat. A diszkrét matematikai modellek – elsősorban gráfok (hálózatok) és hipergráfok – strukturális és extremális vizsgálata mellett a kombinatorikus problémák algoritmikus (idő-) komplexitását, diszkrét optimalizálási feladatok approximálhatóságát, valamint on-line ütemezések versenyképességi arányát tanulmányozzák.

Kutatási eredmények

A gráfszínezés klasszikus és listás változataira vonatkozó kutatások mellett olyan színezéseket is tanulmányoznak, ahol a színek száma valamilyen lokális feltétellel felülről korlátozott. Strukturális, komplexitási és a felhasználható színek számára vonatkozó eredmények mellett a gráfok elvágó csúcs- és élhalmazaival való szoros kapcsolat került kimutatásra (társzerzők: E. Sampathkumar és kutatócsoportja).

Bevezették a hipergráfok színezéseinek, halmazrendszerek partícióinak általános modelljét, és egy cikksorozatban folyamatosan publikálják a rájuk vonatkozó elmélet részleteit. Eközben egy speciális részosztályra (C-színezés) vonatkozóan több, hosszú ideje nyitott problémát oldottak meg. Ezek közül a legrégebbi kérdés az n-elemű halmaz minden k-osztályú partícióját lefogó k-elemű transzverzális-rendszer minimális mérete, amelyre aszimptotikusan pontos megoldást találtak és egy korábbi ezzel kapcsolatos sejtést cáfoltak.

Több megközelítésben tanulmányozták a gráfok felbonthatóságát. Élösszefüggőségi feltételt vizsgáltak K_{1,3} részekre bontásra, és feltárták ennek szoros kapcsolatát irányítási kérdésekkel és folyamokkal (társszerző: C. Thomassen). Továbbá komplexitási eredményeket értek el csúcspartíciók létezésére vonatkozóan, fokszámfeltételek mellett (társszerzők: C. Bazgan és D. Vanderpooten).

Thue nevezetes nem-ismétlő sorozatának általánosításaként kezdték el vizsgálni a gráfok nem-ismétlő színezését. Megmutatták, hogy a korlátos favastagságú gráfok véges sok színnel színezhetők ilyen értelemben (társszerző: Varjú Péter).

Két évtizede nyitott probléma megoldásaként karakterizálták az olyan hálózatok szerkezetét, amelyeknek minden összefüggő részében létezik egy előírt tulajdonságú domináló részhálózat (vagyis amelyből a részhálózat összes többi eleme is közvetlenül elérhető).

A korábban ismerteknél jobb versenyképességi arányt biztosító on-line ütemezési algoritmusokat konstruáltak, továbbá bebizonyították, hogy több feladatra is az alkalmasan szervezett félig on-line (részleges információt felhasználó) algoritmusok garantáltan hatékonyabbak, mint ami a teljesen on-line esetben bármilyen módszerrel elérhető. Négy évtizede nyitott probléma lezárásaként meghatározták a „First Fit Decreasing” és a „First Fit” algoritmusok pontos abszolút approximációs arányát. Új ütemezési és ládapakolási modelleket vezettek be és bizonyították azok approximációs tulajdonságait (társszerzők: L. Epstein, X. Han, H. Kellerer, J. Sgall és M. G. Speranza).

A „kombinatorikus batch kód” olyan halmazrendszer, amellyel  adott mennyiségű információ adott számú szerveren történő tárolása és kiolvasása modellezhető. A kikötések az egyszerre dekódolandó adatok  maximális számára és az adatvédelemmel kapcsolatos titkosításra vonatkoznak. A feltételeknek eleget tevő  halmazrendszer  minimális összméretét határozták meg a  paraméterek különböző tartományain, továbbá a kombinatorika ehhez kapcsolódó klasszikus problémaköreire (Hall feltétel, Turán-probléma) vonatkozóan is új eredményekre jutottak.

A kutatólaboratórium vezetőjének bemutatása

thumb tuzaTuza Zsolt matematikus (ELTE, 1978), a matematikai tudomány doktora (MTA, 1992), habilitált doktor (alkalmazott matematika, BME, 1995), tudományos tanácsadó (MTA SZTAKI, 1993-tól), egyetemi tanár (Veszprémi Egyetem ill. Pannon Egyetem, 2001-től). 1972-ben a Nemzetközi Matematikai Diákolimpia I. díjasa. 300-nál több angol nyelvű tudományos közlemény szerzője, munkáira évente 100-nál több hivatkozás jelenik meg. Számos eredményt ért el többek között az extremális hipergráf-elmélet, gráfok listaszínezései, domináló részgráfok szerkezete, színkorlátos hipergráfok, valamint félig on-line ütemezés terén. Hat nemzetközi szakfolyóirat szerkesztőbizottsági tagja, rendszeresen meghívott előadó nemzetközi gráfelméleti konferenciákon. A „Center of Excellence in Interdisciplinary Mathematics” Tanácsadó Testületének tagja (2008-tól), a Hereditarnia Club elnöke (2007-2008), az Erdős Pál Matematikai Tehetséggondozó Iskola tudományos vezetője.