Projekty finansowane przez NCN


Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Program optymalności w problemach homomorfizmu grafów

2018/31/D/ST6/00062

Słowa kluczowe:

homomorfizm grafów złożoność obliczeniowa algorytmy

Deskryptory:

  • ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier
  • ST6_4: Metody formalne, teoretyczne podstawy informatyki w tym informatyka teoretyczna
  • ST1_14: Kombinatoryka

Panel:

ST6 - Informatyka i technologie informacyjne: technologie i systemy informacyjne, informatyka, obliczenia naukowe, systemy inteligentne

Jednostka realizująca:

Politechnika Warszawska, Wydział Matematyki i Nauk Informacyjnych

woj. mazowieckie

Inne projekty tej jednostki 

Kierownik projektu (z jednostki realizującej):

dr Paweł Rzążewski 

Liczba wykonawców projektu: 4

Konkurs: SONATA 14 - ogłoszony 2018-09-14

Przyznana kwota: 306 680 PLN

Rozpoczęcie projektu: 2019-06-13

Zakończenie projektu: 2023-06-12

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

  • Publikacje w czasopismach (5)
  • Teksty w publikacjach pokonferencyjnych (14)
  1. Subexponential algorithms for variants of homomorphism problem in string graphs IF: 1,494
    Autorzy:
    Karolina Okrasa, Paweł Rzążewski
    Czasopismo:
    Journal of Computer and System Sciences (rok: 2020, tom: 109, strony: 126-144), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.jcss.2019.12.004 - link do publikacji
  2. Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs IF: 0,65
    Autorzy:
    Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, Bartosz Walczak
    Czasopismo:
    Algorithmica (rok: 2020, tom: n/a, strony: n/a), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00453-020-00745-z - link do publikacji
  3. Finding Large H-Colorable Subgraphs in Hereditary Graph Classes IF: 0,755
    Autorzy:
    Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rzaͅżewski, Sophie Spirkl
    Czasopismo:
    SIAM Journal on Discrete Mathematics (rok: 2021, tom: 35, strony: 2357-2386), Wydawca: SIAM
    Status:
    Opublikowana
    Doi:
    10.1137/20M1367660 - link do publikacji
  4. Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs IF: 1,414
    Autorzy:
    Karolina Okrasa, Paweł Rzaͅżewski
    Czasopismo:
    SIAM Journal on Computing (rok: 2021, tom: 50, strony: 487-508), Wydawca: SIAM
    Status:
    Opublikowana
    Doi:
    10.1137/20M1320146 - link do publikacji
  5. On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest IF: 0,65
    Autorzy:
    Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Paweł Rzążewski
    Czasopismo:
    Algorithmica (rok: 2020, tom: 82, strony: 2841–2866), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00453-020-00706-6 - link do publikacji
  1. Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
    Autorzy:
    Karolina Okrasa, Paweł Rzążewski
    Konferencja:
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2020) (rok: 2020, ), Wydawca: SIAM
    Data:
    konferencja 5-8.01.2020
    Status:
    Opublikowana
  2. Sparsification Lower Bounds for List H-Coloring
    Autorzy:
    Hubie chen, Bart M.P. Jansen, Karolina Okrasa, Astrid Pieterse, Paweł Rzążewski
    Konferencja:
    31st International Symposium on Algorithms and Computation (ISAAC 2020) (rok: 2020, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 14-18.12.2020
    Status:
    Opublikowana
  3. Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs
    Autorzy:
    Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, Bartosz Walczak
    Konferencja:
    14th International Symposium on Parameterized and Exact Computation (IPEC 2019) (rok: 2019, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 9-13.09.2019
    Status:
    Opublikowana
  4. Clique-Width: Harnessing the Power of Atoms
    Autorzy:
    Konrad K. Dabrowski, Tomáš Masařík, Jana Novotná, Daniël Paulusma, Paweł Rzążewski
    Konferencja:
    WG 2020: Graph-Theoretic Concepts in Computer Science (rok: 2020, ), Wydawca: Springer
    Data:
    konferencja 24-26.06.2020
    Status:
    Opublikowana
  5. Finding large induced sparse subgraphs in C_{>t} -free graphs in quasipolynomial time
    Autorzy:
    Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski
    Konferencja:
    Symposium on Theory of Computing (STOC 2021) (rok: 2021, ), Wydawca: ACM
    Data:
    konferencja 2021.06.21-25
    Status:
    Opublikowana
  6. Full Complexity Classification of the List Homomorphism Problem for Bounded-Treewidth Graphs
    Autorzy:
    Karolina Okrasa, Marta Piecyk, Paweł Rzążewski
    Konferencja:
    28th Annual European Symposium on Algorithms (ESA 2020) (rok: 2020, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 7-9.09.2020
    Status:
    Opublikowana
  7. Parameterized Inapproximability of Independent Set in H-Free Graphs
    Autorzy:
    Pavel Dvořák, Andreas Emil Feldmann, Ashutosh Rai, Paweł Rzążewski
    Konferencja:
    WG 2020: Graph-Theoretic Concepts in Computer Science (rok: 2020, ), Wydawca: Springer
    Data:
    konferencja 24-26.06.2020
    Status:
    Opublikowana
  8. Complexity of the List Homomorphism Problem in Hereditary Graph Classes
    Autorzy:
    Karolina Okrasa, Paweł Rzążewski
    Konferencja:
    International Symposium on Theoretical Aspects of Computer Science (STACS 2021) (rok: 2021, ), Wydawca: LIPIcs
    Data:
    konferencja 2021.03.16-19
    Status:
    Opublikowana
  9. Fine-Grained Complexity of the List Homomorphism Problem: Feedback Vertex Set and Cutwidth
    Autorzy:
    Maria Piecyk, Paweł Rzążewski
    Konferencja:
    International Symposium on Theoretical Aspects of Computer Science (STACS 2021) (rok: 2021, ), Wydawca: LIPIcs
    Data:
    konferencja 2021.03.16-19
    Status:
    Opublikowana
  10. Quasi-polynomial-time algorithm for Independent Set in Pt-free graphs via shrinking the space of induced paths
    Autorzy:
    Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski
    Konferencja:
    Symposium on Simplicity in Algorithms (SOSA 2021) (rok: 2021, ), Wydawca: SIAM
    Data:
    konferencja 2021.01.11-12
    Status:
    Opublikowana
  11. Induced subgraphs of bounded treewidth and the container method
    Autorzy:
    Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Paweł Rzążewski, Paul Seymour
    Konferencja:
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2021) (rok: 2021, ), Wydawca: SIAM
    Data:
    konferencja 2021.01.10-13
    Status:
    Opublikowana
  12. Faster 3-Coloring of Small-Diameter Graphs
    Autorzy:
    Michał Dębski, Marta Piecyk, Paweł Rzążewski
    Konferencja:
    European Symposium on Algorithms (ESA 2021) (rok: 2021, ), Wydawca: LIPIcs
    Data:
    konferencja 2021.09.6-8
    Status:
    Opublikowana
  13. Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs
    Autorzy:
    Giacomo Paesani, Daniel Paulusma, Paweł Rzążewski
    Konferencja:
    International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) (rok: 2021, ), Wydawca: LIPIcs
    Data:
    konferencja 2021.08.23-27
    Status:
    Opublikowana
  14. Finding Large H-Colorable Subgraphs in Hereditary Graph Classes
    Autorzy:
    Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rzążewski, Sophie Spirkl
    Konferencja:
    28th Annual European Symposium on Algorithms (ESA 2020) (rok: 2020, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 7-9.09.2020
    Status:
    Opublikowana