Projekty finansowane przez NCN
Problem homomorfizmu grafów w strukturalnie ograniczonych klasach
2022/45/N/ST6/00237
Słowa kluczowe:
homomorfizm grafów kolorowanie grafów złożoność obliczeniowa parametryzowana złożoność średnica
Deskryptory:
- ST6_004: Metody formalne, teoretyczne podstawy informatyki w tym informatyka teoretyczna, algorytmy kwantowe
- ST6_006: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier
- ST1_014: Matematyka dyskretna i kombinatoryka
Panel:
ST6 - Informatyka i technologie informacyjne: technologie i systemy informacyjne, informatyka, obliczenia naukowe, systemy inteligentne
Konkurs: PRELUDIUM 21 - ogłoszony 2022-03-28
Przyznana kwota: 111 020 PLN
Rozpoczęcie projektu: 2023-01-25
Zakończenie projektu: 2026-01-24
Planowany czas trwania projektu: 36 miesięcy (z wniosku)
Status projektu: Projekt w realizacji
Opis Projektu
Pobierz opis projektu w formacie .pdf
Uwaga - opisy projektów zostały sporządzone przez samych autorów wniosków i w niezmienionej formie umieszczone w systemie.
Dane z raportu końcowego/rocznego
- Teksty w publikacjach pokonferencyjnych (3)
- Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix ParametersAutorzy:Carla Groenland, Isja Mannens, Jesper Nederlof, Marta Piecyk, Paweł RzążewskiKonferencja:51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia (rok: 2024, tom: 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), strony: 77:1-77:21), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum für InformatikData:konferencja 8.07.2024-12.07.2024Status:OpublikowanaDoi:10.4230/LIPIcs.ICALP.2024.77 - link do publikacji
- C_{2k+1}-Coloring of Bounded-Diameter GraphsAutorzy:Marta PiecykKonferencja:49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, August 26-30, 2024, Bratislava, Slovakia (rok: 2024, tom: 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), strony: 78:1-78:15), Wydawca: Schloss Dagstuhl – Leibniz-Zentrum für InformatikData:konferencja 26.08.2024-30.08.2024Status:OpublikowanaDoi:10.4230/LIPIcs.MFCS.2024.78 - link do publikacji
- Graph Reconstruction with Connectivity QueriesAutorzy:Kacper Kluk, Hoang La, Marta PiecykKonferencja:Graph-Theoretic Concepts in Computer Science. 50th International Workshop, WG 2024, Gozd Martuljek, Slovenia, June 19–21, 2024, Revised Selected Papers (rok: 2024, tom: 50th International Workshop on Graph-Theoretic Concepts in Computer Science, strony: 343-357), Wydawca: SpringerData:konferencja 19.06.2024-21.06.2024Status:OpublikowanaDoi:10.1007/978-3-031-75409-8\_24 - link do publikacji