Prilagojeni projekt N1-0102
Teme v strukturni teoriji grafov: invariante, separatorji in presečne predstavitve
Naslov projekta: Teme v strukturni teoriji grafov: invariante, separatorji in presečne predstavitve
Vodja projekta: Martin Milanič
Šifra projekta: N1-0102.
Tip projekta: prilagojeni projekt.
Financer: Javna agencija RS za raziskovalno dejavnost (ARRS).
Raziskovalno področje (ARRS): 1.01.00 - Naravoslovno-matematične vede / Matematika.
Trajanje projekta: 1. 5. 2019 - 30. 4. 2022.
Cenovna kategorija projekta: B.
Letni obseg projekta: 1.30 FTE (2.202 raziskovalnih ur).
Sicris profil projekta je dostopen tukaj.
Raziskovalne organizacije v okviru katere se izvaja projekt:
Univerza na Primorskem, Inštitut Andrej Marušič
Člani raziskovalnega projekta:
|
Povzetek projekta:
Praktična in teoretična vprašanja, ki izhajajo iz številnih področij uporabe teorije grafov, spodbujajo razvoj hitrih algoritmov za točno ali približno računanje različnih grafovskih invariant, kot so kromatično število, klično število in neodvisnostno število. Ker so ustrezni optimizacijski problemi običajno računsko zahtevni, je razumevanje odnosov med invariantami ključnega pomena za identifikacijo enostavnih primerov; ti so opisani s pojmom razredov grafov. Kljub številnim nedavnim napredkom na tem področju veliko globokih vprašanj ostaja odprtih.
Ta projekt bo preučil več ključnih problemov znotraj čiste in algoritmične teorije grafov, s poudarkom na grafovskih invariantih in razredih grafov. Projekt se bo razvijal vzdolž treh medsebojno povezanih raziskovalnih tem: pogoji za obstoj funkcije, ki omejujejo eno invarianto v odvisnosti od druge, algoritmični vidiki izbranih grafovskih optimizacijskih problemov na ustreznih razredih grafov in sistematičen študij posplošitev tetivnosti. Napredek na teh problemih bo izhajal iz učinkovite kombinacije komplementarnih tehnik, ki se trenutno uporabljajo pri preučevanju razredov grafov, kot so: razcepi grafov, širinski parametri grafov, minimalni separatorji, grafovski minorji, ekstremalna teorija grafov.
Posebno pozornost bomo posvetili proučevanju nekaterih slabo razumljenih vidikov teorije, kot so odnosi med Hadwigerjevim številom in drugimi invariantami, predstavljivost grafov kot presečni grafi grafov majhne drevesne širine in zadostni pogoji za učinkovito rešljivost problema največje neodvisne množice in sorodnih problemov. Končni cilj tega projekta je razvoj novih orodij za globoko in algoritmično uporabno matematično analizo strukture grafov v hereditarnih razredih. Učinek projekta bo izboljšano temeljno razumevanje meja učinkovite rešljivosti za več praktično relevantnih problemov diskretne optimizacije na grafih.