The graph homomorphism problem in structurally restricted classes

2022/45/N/ST6/00237

Keywords

Descriptors

  • ST6_004: Metody formalne, teoretyczne podstawy informatyki w tym informatyka teoretyczna, algorytmy kwantowe
  • ST6_006: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier
  • ST1_014: 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)

Marta Piecyk

Number of co-investigators in the project: 2

Call

PRELUDIUM 21 – announced on 2022-03-28

Amount awarded
111 020 PLN
Project start date
2023-01-25
Project end date
2026-01-24
Project duration
36 months (the same as in the proposal)
Project status
Project completed

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. Graph Reconstruction with Connectivity Queries

    Authors:
    Kacper Kluk, Hoang La, Marta Piecyk
    Conference:
    Graph-Theoretic Concepts in Computer Science. 50th International Workshop, WG 2024, Gozd Martuljek, Slovenia, June 19–21, 2024, Revised Selected Papers (year: 2024, volume: 50th International Workshop on Graph-Theoretic Concepts in Computer Science, pages: 343-357), Publisher: Springer
    Date:
    conference 19.06.2024-21.06.2024
    Status:
    Published
    DOI:
    10.1007/978-3-031-75409-8\_24 – link to the publication
  2. C_{2k+1}-Coloring of Bounded-Diameter Graphs

    Authors:
    Marta Piecyk
    Conference:
    49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, August 26-30, 2024, Bratislava, Slovakia (year: 2024, volume: 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), pages: 78:1-78:15), Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
    Date:
    conference 26.08.2024-30.08.2024
    Status:
    Published
    DOI:
    10.4230/LIPIcs.MFCS.2024.78 – link to the publication
  3. Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix Parameters

    Authors:
    Carla Groenland, Isja Mannens, Jesper Nederlof, Marta Piecyk, Paweł Rzążewski
    Conference:
    51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia (year: 2024, volume: 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), pages: 77:1-77:21), Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
    Date:
    conference 8.07.2024-12.07.2024
    Status:
    Published
    DOI:
    10.4230/LIPIcs.ICALP.2024.77 – link to the publication

« New search

Graphic design and implementation: Jakub Piotrowski