Onkraj redkosti: razredi grafov in širinski parametri
natisniPredstavitev projekta
Naslov: Onkraj redkosti: razredi grafov in širinski parametri
Šifra projekta: N1-0370
Vodilna institucija: UP FAMNIT
Partnerska institucija: UP IAM
Vodja projekta: dr. Martin Milanič
Financer projekta: Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije (ARIS)
Raziskovalno področje (ARIS): 1.01 - Matematika
Vrsta projekta: Prilagojeni raziskovalni projekt
Trajanje projekta: 1. 6. 2024–31. 5. 2027
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čnateorija grafov osredotočila na razširitev teorije redkih grafov na goste razrede grafov. Cilj predlaganega projekta je uvesti nove načine in metode zadosego 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 temeljina 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 identificiratinetrivialne 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šegarazumevanja meja učinkovite rešljivosti problema največje neodvisne množice in več drugih praktično pomembnih optimizacijskih problemov nagrafih.
Oddelek UP FAMNIT, v okviru katerega se izvaja projekt:
Oddelek za aplikativno naravoslovje
Project presentationna vrh
Title: Beyond Sparsity: Graph Classes and Width Parameters
Project acronym: N1-0370
Leading institution: UP FAMNIT
Partner institutions: UP IAM
Principal investigator: dr. Martin Milanič
Funding organization: Slovenian Research and Innovation Agency (ARIS)
Research field (ARIS): 1.01 - Mathematics
Duration: 1. 6. 2024–31. 5. 2027
The Graph Sparsity Theory of Nešetřil and Ossona de Mendez is a highly active and rapidly developing topic in combinatorics and graph theory, withapplications in many areas including algorithmic graph theory, complexity theory, and property testing. A recent focus of structural and algorithmicgraph theory has been to extend the graph sparsity theory to dense graph classes. The proposed project aims at introducing novel ways andmethods of addressing this goal. This will be done along the following two interconnected research lines:
– first, by advancing the recently emerging and fast developing theory of graph width and depth parameters through a general framework based ongraph measures and an in-depth analysis of known and novel graph parameters;
– second, by developing a biparametric theory of hereditary graph classes in which some parameter is bounded by a function of another one, withthe goal of identifying nontrivial structural and algorithmic implications.
Our approach is complementary to the theory of graph classes with bounded flip-width developed recently by Toruńczyk and will lead to an improvedunderstanding of the boundaries of tractability for maximum independent set and several other practically relevant graph optimization problems.
Department of Applied Natural Sciences
