Prilagojeni projekt N1-0370
Onkraj redkosti: razredi grafov and širinski parametri

 

Naslov projekta: Onkraj redkosti: razredi grafov and širinski parametri

Vodja projekta: Martin Milanič

Šifra projekta: N1-0370.

Tip projekta: prilagojeni projekt.

Financer: Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost RS (ARIS).

Raziskovalno področje (ARRS): 1.01.00 - Naravoslovno-matematične vede / Matematika.

Trajanje projekta: 1. 6. 2024 - 31. 5. 2027.

Cenovna kategorija projekta: C.

Letni obseg projekta: 0,59 FTE (1.008 raziskovalnih ur letno).

Sicris profil projekta je dostopen tukaj.

Raziskovalne organizacije v okviru katere se izvaja projekt:

Univerza na Primorskem, UP FAMNIT

Univerza na Primorskem, UP IAM

Člani raziskovalnega projekta:

Martin Milanič (ARIS koda: 30211) Matjaž Krnc (ARIS koda: 34562) Nina Chiarelli (ARIS koda: 35452) Peter Muršič (ARIS koda: 53028) Claire Hilaire (ARIS koda: 58123) Kenny Štorgel (ARIS koda: 53598)

Povzetek projekta:

Teorija redkih grafov Nešetřila in Ossone de Mendeza je zelo aktivna in hitro razvijajoča se tema v kombinatoriki in teoriji grafov z aplikacijami na številnih področjih, vključno z algoritmično teorijo grafov, teorijo kompleksnosti in testiranjem lastnosti. Nedavno se je strukturna in algoritmična teorija grafov osredotočila na razširitev teorije redkih grafov na goste razrede grafov. Cilj predlaganega projekta je uvesti nove načine in metode za dosego tega cilja. To bo potekalo v okviru naslednjih dveh med seboj povezanih raziskovalnih smeri:
– prvič, z napredovanjem nedavno nastajajoče in hitro razvijajoče se teorije širinskih in globinskih parametrov grafov prek splošnega okvira, ki temelji na merah grafov in poglobljeni analizi znanih in novih parametrov grafov;
– drugič, z razvojem biparametrične teorije hereditarnih razredov grafov, v katerih je nek parameter omejen s funkcijo drugega, s ciljem identificirati netrivialne strukturne in algoritmične posledice.

Predlagan pristop dopolnjuje teorijo razredov grafov z omejeno širino obračanja, ki jo je pred kratkim razvil Toruńczyk, in bo vodil do boljšega razumevanja meja učinkovite rešljivosti problema največje neodvisne množice in več drugih praktično pomembnih optimizacijskih problemov na grafih.