Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Dynamic graphs; connectivity, flows and coloring.

2017/26/D/ST6/00264

Keywords:

graph dynamic connectivity flow coloring

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory
  • ST6_4: Formal methods, foundations of computer science, including theoretical computer science, quantum algorithms

Panel:

ST6 - Computer science and informatics: informatics and information systems, computer science, scientific computing, intelligent systems

Host institution :

Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki

woj. mazowieckie

Other projects carried out by the institution 

Principal investigator (from the host institution):

dr Anna Zych-Pawlewicz 

Number of co-investigators in the project: 3

Call: SONATA 13 - announced on 2017-06-14

Amount awarded: 338 100 PLN

Project start date (Y-m-d): 2018-04-20

Project end date (Y-m-d): 2023-04-19

Project duration:: 60 months (the same as in the proposal)

Project status: Project settled

Project description

Download the project description in a pdf file

Note - project descriptions were prepared by the authors of the applications themselves and placed in the system in an unchanged form.

Equipment purchased [PL]

  1. tablet graficzny.

Information in the final report

  • Publication in academic press/journals (4)
  • Articles in post-conference publications (5)
  • Book publications / chapters in book publications (1)
  1. Hat chromatic number of graphs
    Authors:
    Bartłomiej Bosek, Andrzej Dudek, Michał Farnik, Jarosław Grytczuk, Przemysław Mazur
    Academic press:
    Discrete Mathematics (rok: 2021, tom: 344, strony: brak), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.disc.2021.112620 - link to the publication
  2. Graph polynomials and paintability of plane graphs
    Authors:
    Jarosław Grytczuk, Stanislav Jendrol, Mariusz Zając
    Academic press:
    Discrete Applied Mathematics (rok: 2022, tom: 313, strony: 71-79), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.dam.2022.02.006 - link to the publication
  3. The Alon-Tarsi number of a planar graph minus a matching
    Authors:
    Jarosław Grytczuk, Xuding Zhu
    Academic press:
    Journal of Combinatorial Theory, Series B (rok: 2020, tom: 145, strony: 511-520), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.jctb.2020.02.005 - link to the publication
  4. Multiple twins in permutations
    Authors:
    Andrzej Dudek, Jarosław Grytczuk, Andrzej Ruciński
    Academic press:
    Advances in Applied Mathematics , Wydawca: Elsevier
    Status:
    Submitted
    DOI:
    brak - link to the publication
  1. Dynamic Coloring of Unit Interval Graphs with Limited Recourse Budget
    Authors:
    Bartłomiej Bosek, Anna Zych-Pawlewicz
    Conference:
    European Symposium on Algorithms (ESA) (rok: 2022, ), Wydawca: Schloss Dagstuhl -- Leibniz-Zentrum fur Informatik
    Data:
    konferencja 5-7.09.2022
    Status:
    Published
  2. Dynamic Data Structures for Parametrized String Problems
    Authors:
    Jędrzej Olkowski, Michał Pilipczuk, Mateusz Rychlicki, Karol Węgrzycki, Anna Zych-Pawlewicz
    Conference:
    International Symposium on Theoretical Aspects of Computer Science (STACS) (rok: 2023, ), Wydawca: Schloss Dagstuhl -- Leibniz-Zentrum fur Informatik
    Data:
    konferencja 7-9.03.2023
    Status:
    Published
  3. Recoloring Interval Graphs with Limited Recourse Budget
    Authors:
    Bartłomiej Bosek, Yann Disser, Andreas Emil Feldmann, Jakub Pawlewicz, Anna Zych-Pawlewicz
    Conference:
    SWAT (rok: 2020, ), Wydawca: LIPIcs
    Data:
    konferencja 22-24.06
    Status:
    Published
  4. Efficient fully dynamic elimination forests with applications to detecting long paths and cycles.
    Authors:
    Jiehua Chen, Wojciech Czerwiński, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Marcin Pilipczuk, Michał Pilipczuk, Manuel Sorge, Bartłomiej Wróblewski, Anna Zych-Pawlewicz
    Conference:
    ACM-SIAM Symposium on Discrete Algorithms (SODA21) (rok: 2021, ), Wydawca: SIAM
    Data:
    konferencja January 10 - 13, 2021
    Status:
    Published
  5. Dynamic Parametrized Feedback Problems in Tournaments
    Authors:
    Anna Zych-Pawlewicz, Marek Żochowski
    Conference:
    The International Symposium on Parametrized and Exact Computation (rok: 2023, ), Wydawca: Schloss Dagstuhl -- Leibniz-Zentrum fur Informatik
    Data:
    konferencja 6-8.09.2023
    Status:
    Submitted
  1. Coloring Chain Hypergraphs
    Authors:
    Bartłomiej Bosek, Sebastian Czerwiński, Michał Dębski, Jarosław Grytczuk, Zbigniew Lonc, Paweł Rzążewski
    Book:
    20 years of the Faculty of Mathematics and Information Science (rok: 2020, tom: 1, strony: 41-53), Wydawca: Oficyna Wydawnicza Politechniki Warszawskiej
    Status:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy