Uporaba pristopov kombinatorične optimizacije pri prekrižnem številu grafov - delavnica Prekrižna števila 2014

Organizator delavnice: FNM


Koordinator delavnice: Drago Bokal


Datum in kraj izvedbe: junij 2014


Št. ur delavnice: 18 ur


Št. tujih predavateljev: 8


Vsebina delavnice: Namen delavnice je bil zbrati raziskovalce, ki jih zanimajo algoritmični in teoretični vidiki prekrižnega števila grafov. Tekom zadnjih 10 let je na tem področju prišlo do naraščajočega zanimanja za vprašanja algoritmične kompleksnosti ter aproksimacijskih pristopov k problemu prekrižnega števila. Na temo kompleksnosti je zanimiv Grohe-jev rezultat, da je prekrižno število v razredu FPT problemov, ki sta ga nadgradila Kawarabayashi in Reed z linearnim algoritmom za preverjanje izbranega prekrižnega števila. Na bolj uporabni strani pa so algoritmi, implementirani v ekipi Petre Mutzel, ki s pristopi celoštevilskega programiranja izračunajo natančno prekrižno število relativno velikih grafov. Podobno imamo vrsto nedavnih aproksimacijskih algoritmov za specifične probleme, ki so jih odkrili Hlineny, Salazar, in Chimani. Cabello in Mohar sta pokazala, da je Prekrižno Število NP-polno tudi za skoraj-planarne grafe. Na delavnici smo predstavili nove rezultate v navedenih smereh ter reflektirali ta odkritja, s poudarkom na prepletu med teoretičnimi in algoritmičnimi vidiki problema prekrižnega števila. V okviru delavnice se je porodilo ogromno novih idej na tem področju, ki bodo zapisane tudi v več člankih.




_____________________________________________________________________


»Operacijo delno financira Evropska unija iz Evropskega socialnega sklada ter Ministrstvo za izobraževanje, znanost in šport. Operacija se izvaja v okviru Operativnega programa razvoja človeških virov za obdobje 2007-2013, 3. razvojne prioritete: Razvoj človeških virov in vseživljenjskega učenja; prednostne usmeritve 3.3.: Kakovost, konkurenčnost in odzivnost visokega šolstva.«
Urednik strani: Oddelek za raziskovalno in umetniško dejavnost
Dokumenti
 Univerza v Mariboru, Slomškov trg 15, 2000 Maribor | +386 2 23 55 280 | rektorat@um.si | Davčna številka: SI 71674705 | Prijava