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
Principal investigator (from the host institution)
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)
-
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
-
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
-
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