Projekty finansowane przez NCN
Strukturalne i algorytmiczne własności dziedzicznych klas grafów
2022/46/E/ST6/00143
Słowa kluczowe:
problem maksymalnego zbioru niezależnego dziedziczne klasy grafów hipoteza Erdosa-Hajnala chi-ograniczoność
Deskryptory:
- 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
Jednostka realizująca:
Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
woj. mazowieckie
Kierownik projektu (z jednostki realizującej):
dr hab. Marcin Łukasz Pilipczuk
Liczba wykonawców projektu: 4
Konkurs: SONATA BIS 12 - ogłoszony 2022-05-15
Przyznana kwota: 1 845 300 PLN
Rozpoczęcie projektu: 2023-07-03
Zakończenie projektu: 2028-07-02
Planowany czas trwania projektu: 60 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)
- Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial TimeAutorzy:Peter Gartland, Daniel Lokshtanov, Tomas Masarik, Marcin Pilipczuk, Michal Pilipczuk, Pawel RzazewskiKonferencja:Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024 (rok: 2024, tom: 56th Annual ACM Symposium on Theory of Computing, STOC 2024, strony: 683-691), Wydawca: ACMData:konferencja 2024-06-24 do 2024-06-28Status:OpublikowanaDoi:10.1145/3618260.3649791 - link do publikacji
- Sparse induced subgraphs in P6-free graphsAutorzy:Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk, Michał Pilipczuk, Paweł RzążewskiKonferencja:Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 (rok: 2024, tom: 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, strony: 5291-5299), Wydawca: SIAMData:konferencja 2024-01-07 do 2024-01-10Status:OpublikowanaDoi:10.1137/1.9781611977912.190 - link do publikacji
- Max Weight Independent Set in Sparse Graphs with No Long ClawsAutorzy:Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Paweł RzążewskiKonferencja:41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024 (rok: 2024, tom: 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, strony: 4:1-4:15), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer InformatikData:konferencja 2024-03-12 do 2024-03-14Status:OpublikowanaDoi:10.4230/LIPIcs.STACS.2024.4 - link do publikacji