Onkraj redkosti: razredi grafov in širinski parametri
|
Naziv Tittle |
Onkraj redkosti: razredi grafov in širinski parametri |
|
Akronim Acronim |
N1-0370 |
|
Opis Description |
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:
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. |
|
Vrsta projekta Project Type |
Prilagojen raziskovalni projekt |
|
Trajanje Duration |
01/06/2024 - 31/05/2027 |
|
URL URL |
https://cris.cobiss.net/ecris/si/sl/project/21824 |
|
Vodja projekta Project Leader |
Martin Milanič |
|
Sodelujoče organizacije Participating organizations |
UP IAM |
|
Oddelek Department |
Oddelek za matematiko IAM |
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.
[project_type] => Projekt ARRS [project_subtype] => Programska skupina [arrs_klasifikacija] => [from] => 2024-06-01 [to] => 2027-05-31 [url] => https://cris.cobiss.net/ecris/si/sl/project/21824 [results] => Redkost grafov, hereditaren razred grafov, širinski parametri, drevesna dekompozicija [project_status] => V izvajanju [nosilna_clanica] => UP FAMNIT [project_role] => Vodilni partner [project_program] => [naziv_razpisa] => Javni razpis za (so)financiranje prilagojenih raziskovalnih projektov v okviru komplementarne sheme za prijave na razpise Evropskega raziskovalnega sveta (ERC), z dne 23.12.2022 [project_category] => ARRS [project_classification] => [project_arrs_classification] => Prilagojen raziskovalni projekt [project_research_area1] => [project_research_area2] => [project_research_area3] => [project_arrs_research_area] => 1 NARAVOSLOVJE [project_arrs_research_subarea] => 1.01 Matematika [drzava] => [clanica] => UP IAM ) 1 -->