From dense graphs to sparse ones and back again

2024/54/E/ST6/00094

Keywords

Descriptors

  • ST6_06: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier
  • ST1_14: Matematyka dyskretna i kombinatoryka

Panel

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

Host institution

Politechnika Warszawska

Voivodeship: 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
2025-04-07
Project end date
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. Polynomial-Time Recognition and Maximum Independent Set in Burling Graphs

    Authors:
    Paweł Rzążewski, Bartosz Walczak
    Conference:
    WG 2025 Proceedings, LNCS16124 (year: 2026, volume: International Workshop on Graph-Theoretic Concepts in Computer Science 2025, pages: 445-460), Publisher: Springer
    Date:
    conference 11-13.06.2025
    Status:
    Published
    DOI:
    10.1007/978-3-032-11835-6_32 – link to the publication
  2. 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 (year: 2025, volume: International Colloquium on Theoretical Aspects of Computing 2025, pages: 459–467), Publisher: Springer
    Date:
    conference 24-28.11.2025
    Status:
    Published
    DOI:
    10.1007/978-3-032-11176-0_27 – link to the publication
  3. An 11/6-Approximation Algorithm for Vertex Cover on String Graphs

    Authors:
    Édouard Bonnet, Paweł Rzążewski
    Conference:
    SoCG 2025 Proc., LIPIcs 332 (year: 2025, volume: 41st International Symposium on Computational Geometry (SoCG 2025), pages: 24:1-24:15), Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
    Date:
    conference 23-27.06.2025
    Status:
    Published
    DOI:
    10.4230/LIPIcs.SoCG.2025.24 – link to the publication

« New search

Graphic design and implementation: Jakub Piotrowski