Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

From dense graphs to sparse ones and back again

2024/54/E/ST6/00094

Keywords:

induced minor induced subgraph graph width parameters graph algorithms ordered graphs homomorphism

Descriptors:

  • ST6_06:
  • ST1_14:

Panel:

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

Host institution :

Politechnika Warszawska

woj. mazowieckie

Other projects carried out by the institution 

Principal investigator (from the host institution):

dr Paweł Rzążewski 

Number of co-investigators in the project: 4

Call: SONATA BIS 14 - announced on 2024-06-18

Amount awarded: 1 847 080 PLN

Project start date (Y-m-d): 2025-04-07

Project end date (Y-m-d): 2030-04-06

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

Project status: Pending project

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.

Information in the final report

  • Articles in post-conference publications (3)
  1. On Computational Aspects of Ordered Matching Problems
    Authors:
    Michal Čertík, Andreas Emil Feldmann, Jaroslav Nešetřil, Paweł Rzążewski
    Conference:
    ICTAC 2025 Proc. LNCS 16237 (rok: 2025, tom: International Colloquium on Theoretical Aspects of Computing 2025, strony: 459–467), Wydawca: Springer
    Data:
    konferencja 24-28.11.2025
    Status:
    Published
    DOI:
    10.1007/978-3-032-11176-0_27 - link to the publication
  2. An 11/6-Approximation Algorithm for Vertex Cover on String Graphs
    Authors:
    Édouard Bonnet, Paweł Rzążewski
    Conference:
    SoCG 2025 Proc., LIPIcs 332 (rok: 2025, tom: 41st International Symposium on Computational Geometry (SoCG 2025), strony: 24:1-24:15), Wydawca: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
    Data:
    konferencja 23-27.06.2025
    Status:
    Published
    DOI:
    10.4230/LIPIcs.SoCG.2025.24 - link to the publication
  3. Polynomial-Time Recognition and Maximum Independent Set in Burling Graphs
    Authors:
    Paweł Rzążewski, Bartosz Walczak
    Conference:
    WG 2025 Proceedings, LNCS16124 (rok: 2026, tom: International Workshop on Graph-Theoretic Concepts in Computer Science 2025, strony: 445-460), Wydawca: Springer
    Data:
    konferencja 11-13.06.2025
    Status:
    Published
    DOI:
    10.1007/978-3-032-11835-6_32 - link to the publication

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy