General Information
The GRAPA project is a bilateral French-Japanese research project financed
under the PHC Sakura
program of JSPS and the French ministry of Foreign Affairs. The research
topic of the project is the design of algorithms for NP-hard problems on
graphs, using the tools of parameterized complexity and approximation.
General Information about the project:
- PIs: Michael Lampis (France) and Yota Otachi (Japan).
- Duration: Jan 2017-Apr 2019.
- Total Budget: 13k€ (France) + 2,000,000 ¥ (Japan).
Project Members
The project is carried out by a French and a Japanese team of researchers. Both teams include several young researchers (doctoral students/post-docs).
French Team
Japanese Team
Publications
The project has resulted in the publication of the following research articles.
-
| Title: |
Token Sliding on Split Graphs
|
| Author(s): |
Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, and Florian Sikora
|
| Conference: |
STACS 2019
|
| Links: |
draft
|
-
| Title: |
Parameterized Complexity of Safe Set
|
| Author(s): |
Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Hirotaka Ono, and Yota Otachi
|
| Conference: |
CIAC 2019
|
| Links: |
draft
|
-
| Title: |
New Results on Directed Edge Dominating Set
|
| Author(s): |
Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Eun Jung Kim, and Michael Lampis
|
| Conference: |
MFCS 2018
|
| Links: |
draft
|
-
| Title: |
Parameterized Orientable Deletion
|
| Author(s): |
Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, and Florian Sikora
|
| Conference: |
SWAT 2018
|
| Links: |
draft
|
-
| Title: |
How Bad is the Freedom to Flood-It?
|
| Author(s): |
Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi, Michael Lampis, and Yota Otachi
|
| Conference: |
FUN 2018
|
| Journal: | JGAA (2019) |
| Links: |
online
|
-
| Title: |
Parameterized (Approximate) Defective Coloring
|
| Author(s): |
Rémy Belmonte, Michael Lampis, and Valia Mitsou
|
| Conference: |
STACS 2018
|
| Links: |
draft
|
-
| Title: |
Defective Coloring on Classes of Perfect Graphs
|
| Author(s): |
Rémy Belmonte, Michael Lampis, Valia Mitsou
|
| Conference: |
WG 2017
|
| Links: |
draft |
Workshops
The project's funding has allowed the two teams to organize several research workshops, giving them the opportunity to collaborate. In particular, the following research workshops have been organized as part of the GRAPA project.
- Kick-off Meeting. Place: LAMSADE, Universite Paris-Dauphine, Paris, FRANCE. Period: 12-16 Jun 2017. Participant members: ML, VM, EK, FS, IK; YO, RB, TH.
- Japan Meeting 1. Place: Kumamoto University, Kumamoto, JAPAN. Period: 20-24 Nov 2017. Participant members: ML, IK, MG; YO, HO, RB, TH.
- Japan Meeting 2. Place: Nagoya University, Nagoya, JAPAN. Period: 25-29 Jun 2018. Participant members: ML, EK, FS, VM; YO, HO, RB, TH.
- Japan mini-Meeting. Place: University of Electro-Communications, Chofu, JAPAN. Period: 17-21 Dec 2018. Participant members: ML, VM; YO, HO, RB, TH.
- Final Meeting. Place: LAMSADE, Universite Paris-Dauphine, Paris, FRANCE. Period: 25-29 Mar 2019. Participant members: ML, VM, EK, FS, IK, MG; YO, HO, RB, TH.
