A kutatólaboratórium tevékenysége
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 (például különféle ládapakolási feladatok) approximálhatóságát, valamint off-line és 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ő: P. Varjú).
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ő). Adott minimális fokszámot feltételezve a csúcsok számának függvényében felső korlátokat bizonyítottak a gráfok dominálási számára. Ezek a jelenleg ismert legjobb felső becslések az 5 és 50 közötti minimális fokszám esetére, továbbá a bizonyítás algoritmikus eljárást is ad a korlátot meg nem haladó méretű domináló halmazok konstruálására (társszerzők: S. Klavžar, M. Henning). Hasonló eredmények születtek a 2-dominálásra vonatkozóan (társszerző: Sz. Jaskó).
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 jelenlegi legjobb alsó-, illetve a jelenlegi (2020-ban) legjobb felső becsléseket határozták meg az online ládapakolási feladatra (társszerzők: J. Balogh, J. Békési, L. Epstein, A. Levin).
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.
Publikációk
A kutatócsoport tagjainak az elmúlt években (2015 és 2019 között) egyebek mellett közel 100 impakt faktoros publikációja született a DBLP adatbázis adatai szerint.
Projektek
A kutatócsoport tagjai különféle pályázatokat nyertek az elmúlt években (pl. Szlovén-Magyar OTKA), és különféle projektekben vállaltak szerepet (TÁMOP, EFOP, stb. pályázatok), valamint több sikeres konferenciát szerveztek (Veszprém Discrete Mathematics and Applications Conference, 2018, Veszprém Optimization Workshop 2019).
A kutatócsoport két tagja munka közben
