Nalaganje ...
Projekti / Programi vir: ARIS

Strukturni, optimizacijski in algoritmični problemi v geometrijskih in topoloških predstavitvah grafov

Raziskovalna dejavnost

Koda Veda Področje Podpodročje
1.01.05  Naravoslovje  Matematika  Teorija grafov 

Koda Veda Področje
1.01  Naravoslovne vede  Matematika 
Ključne besede
topološka teorija grafov, algoritmi, optimizacija na grafih, prekrižna števila, ravninski grafi, presečni grafi, limite grafov
Vrednotenje (pravilnik)
vir: COBISS
Raziskovalci (23)
št. Evidenčna št. Ime in priimek Razisk. področje Vloga Obdobje Štev. publikacijŠtev. publikacij
1.  22402  dr. Drago Bokal  Matematika  Raziskovalec  2020 - 2023  240 
2.  39519  Dragana Božović  Matematika  Raziskovalec  2022 - 2023  30 
3.  17005  dr. Boštjan Brešar  Matematika  Raziskovalec  2020 - 2023  403 
4.  52103  dr. Simon Brezovnik  Matematika  Raziskovalec  2020 - 2022  50 
5.  25993  dr. Sergio Cabello Justo  Matematika  Raziskovalec  2020 - 2023  218 
6.  32028  dr. Tanja Dravec  Matematika  Raziskovalec  2022 - 2023  145 
7.  16332  dr. Gašper Fijavž  Matematika  Raziskovalec  2020 - 2023  121 
8.  34564  dr. David Gajser  Matematika  Raziskovalec  2020 - 2023  33 
9.  50518  dr. Vesna Iršič  Matematika  Raziskovalec  2021 - 2023  54 
10.  24751  dr. Janja Jerebic  Upravne in organizacijske vede  Raziskovalec  2020 - 2023  121 
11.  37839  dr. Aleksander Kelenc  Matematika  Raziskovalec  2022 - 2023  27 
12.  05949  dr. Sandi Klavžar  Matematika  Raziskovalec  2020 - 2023  1.177 
13.  22401  dr. Matjaž Konvalinka  Matematika  Raziskovalec  2020 - 2023  115 
14.  34750  dr. Gašper Košmrlj  Matematika  Raziskovalec  2022 - 2023  19 
15.  05952  mag. Matija Lokar  Matematika  Raziskovalec  2022 - 2023  416 
16.  51477  dr. Daša Mesarič Štesl  Matematika  Raziskovalec  2022 - 2023  20 
17.  01931  dr. Bojan Mohar  Matematika  Vodja  2020 - 2023  1.002 
18.  32250  dr. Polona Repolusk  Interdisciplinarne raziskave  Raziskovalec  2022 - 2023  45 
19.  52490  dr. Gregor Rus  Matematika  Raziskovalec  2022 - 2023  22 
20.  52334  Alen Vegi Kalamar  Matematika  Raziskovalec  2020 - 2023 
21.  11666  dr. Aleksander Vesel  Računalniško intenzivne metode in aplikacije  Raziskovalec  2020 - 2023  339 
22.  30920  dr. Janoš Vidali  Matematika  Raziskovalec  2020 - 2023  26 
23.  24049  dr. Andrej Vodopivec  Matematika  Raziskovalec  2022 - 2023  14 
Organizacije (3)
št. Evidenčna št. Razisk. organizacija Kraj Matična številka Štev. publikacijŠtev. publikacij
1.  0101  Inštitut za matematiko, fiziko in mehaniko  Ljubljana  5055598000  20.216 
2.  1554  Univerza v Ljubljani, Fakulteta za matematiko in fiziko  Ljubljana  1627007  34.059 
3.  2547  Univerza v Mariboru, Fakulteta za naravoslovje in matematiko  Maribor  5089638051  18.010 
Povzetek
Grafovske modele je moč najti vsepovsod in naraščajoča popularnost raziskav v teoriji grafov je presegla staro prepričanje, da so grafi zgolj matematične diskretne strukture. Gradnja modelov z uporabo zelo velikih grafov se uporablja v najrazličnejših področjih znanosti in tehnike. Klasična teorija grafov obdeluje majhne grafe in njihove lastnosti, a druga področja znanosti dandanes potrebujejo razvoj orodij za delo z zelo velikimi grafi, neskončnimi grafi, slučajnimi grafi in še bolj kompleksnimi objekti, kot so neskončne družine grafov ali grafovske limite. Tako topološka kot geometrijska teorija grafov se ukvarjata s problemi v takšnih družinah objektov, raziskujeta njihovo strukturo in uporabo v teoretičnih in praktičnih problemih optimizacije, algoritmov in podatkovnih struktur. V sklopu projekta se bomo ukvarjali s strukturnimi, optimizacijskimi in algoritmičnimi problemi v geometrijskih in topoloških predstavitvah grafov. V prvem delovnem paketu bomo raziskovali strukturo predstavitev končnih grafov, ki jih lahko razumemo bodisi kot topološke bodisi kot geometrijske strukture. Nadaljevali bomo naše raziskave o strukturi prekrižno kritičnih grafov, širini vložitev grafov in triangulacij v ploskvah. V drugem delovnem paketu bomo obravnavali teorijo limit optimalnih (oz. lokalno optimalnih) grafovskih risb v zvezi z različnimi modeli slučajnih risb grafov. Z razvito strukturno teorijo limit grafovskih risb si obetamo alternativen pogled na asimptotično (morda celo eksaktno) verzijo domneve Harary-Hill-Guy iz leta 1963 in/ali domneve Turan-Zarankiewicz iz leta 1954. S povezavo z geometrijskimi risbami grafov si obetamo napredek v razumevanju Sylvestrovega problema o štirih točkah iz leta 1865. Tretji delovni paket se bo ukvarjal z uporabo strukturnih rezultatov prvih dveh delovnih paketov pri modeliranju in razvoju algoritmov. Kot primer konkretnih povezav navedemo uporabo grafovskih razdalj v problemih usmerjanja tokov, uporabo geometrijskih presečnih grafov pri problemih premikanja agentov in analize slik, limitni grafovski objekti pa se povezujejo s Hebbovim učenjem, psihološkimi modeli optimalne izkušnje in učenjem nevronskih mrež. Med orodji, ki jih bomo uporabljali pri delu na projektu, naj naštejemo Erdősevo verjetnostno metodo, Robertsonovo in Seymourjevo teorijo strukture grafov s prepovedanim minorjem, Szemerédijevo lemo o regularnosti in novejšo teorijo grafovskih limit, ki jo je prvenstveno razvil L. Lovász. Omenjene rezultate bomo prepletli s strukturnimi rezultati grafovskih vložitev in grafovskih risb, ki smo jih razvili sodelavci projekta in njihovi soavtorji (mostovi v grafih, teorija tlakovcev, šiv grafov, specialne podatkovne strukture za predstavitve geometrijskih grafov). V okviru projekta bomo združili znanja projektne skupine in širili meje znanja na teh grafovskih raziskovalnih problemih.
Zgodovina ogledov
Priljubljeno