Research output per year
Research output per year
Project Details
Description
In this project, we explore the boundaries between tractability and intractability for graph modification problems. The study of such problems has developed fast in the past years with a wealth of new results being published. One common aspect of most such results is that they are tailored for very specific types of graph modification problems or specific types of inputs. The field lacks tools for unifying theories, such as algorithmic meta theorems, that can provide efficient algorithms for multiple types of modifications, or a wide range of inputs, at once. The goal of this project is to develop this missing theory.
| Status | Active |
|---|---|
| Effective start/end date | 01/07/2023 → 30/06/2027 |
Collaborative partners
- IT University of Copenhagen (lead)
- University of Montpellier
Funding
- Independent Research Fund Denmark: DKK2,836,501.00
Keywords
- Graph Modification
- Algorithms
- Complexity Theory
- Graph Theory
Fingerprint
Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.
-
Equitable coloring of large bipartite graphs
Nikabadi, A., 2026, 7 p. arXiv.Research output: Other contribution › Research
Open Access -
Longest Path Transversals in Claw-Free and $$P_5$$-Free Graphs
Lima, P. T. & Nikabadi, A., 18 May 2025, Algorithms and Complexity. CICA 2025 ed. Springer, Vol. 15679. p. 310-325 15 p. (Lecture Notes in Computer Science, Vol. 15679).Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review
-
Maximum list $r$-colorable induced subgraphs in $kP_3$-free graphs
Galby, E., Lima, P. T., Munaro, A. & Nikabadi, A., 1 May 2025, p. 1-20, 20 p.Research output: Working paper › Preprint
File