Fiodor Fomine

Données clés
Naissance	16 mars 1968 (56 ans)
Domaines	Algorithmique et théorie des graphes
Institutions	Université de Bergen
Formation	Université d'État de Saint-Pétersbourg
Directeur de thèse	Nikolaï Nikolaïevitch Petrov
Distinctions	prix IPEC Nerode 2015 et 2017
Site	www.ii.uib.no/~fomin/

Fiodor Vladimirovitch Fomine (en russe : Фёдор Владимирович Фомин, orthographe anglaise : Fedor Fomin) est un professeur d'informatique à l'université de Bergen. Il est connu pour ses contributions à l'algorithmique et à la théorie des graphes.

Carrière

Fiodor Fomine obtient sa maîtrise (1992) et son doctorat (1997) à l'université d'État de Saint-Pétersbourg sous la supervision de Nikolaï Nikolaïevitch Petrov^[1]. Il est professeur assistant à l'université d'État de Saint-Pétersbourg (chaire de recherche opérationnelle) jusqu'en 1999. Il est chercheur postdoctoral au Chili (Centro de Modelamiento Matemático de l'Universidad de Chile), en République tchèque (Institute for Theoretical Computer Science de l'université Charles de Prague, en Allemagne (université de Paderborn). Depuis 2002, Fomine est professeur d'algorithmique au département d'informatique de l'université de Bergen.

En 2011-2016, il dirige un projet ERC (Advanced Investigator Grant) intitulé Rigorous Theory of Preprocessing. Il dirige également un projet financé par la Russie sur les Algorithms and complexity beyond polynomial time, qui a pour objectif de créer l'infrastructure de recherche en informatique théorique au département de l'Institut Steklov.

Travaux

Fomine travaille principalement dans les domaines de l'algorithmique et de la combinatoire. Il contribue principalement en complexité paramétrée^[2] , kernelisation, algorithmes exacts en temps exponentiel, algorithmes de théorie des graphes, et notamment mineurs de graphes , coloration de graphes et ses variantes, graphes avec paramètres de largeur (largeur arborescente, largeur de branchement, largeur de clique), et des problèmes de poursuite-évasion et de recherche dans un graphe.

Fomine est connu par ses publications sur la bidimensionnalité, sur laquelle il travaille depuis 2004, et qu'il présente notamment dans l'article de synthèse

Fedor V. Fomin, Erik D. Demaine, Mohammad Taghi Hajiaghayi et Dimitrios M. Thilikos, « Bidimensionality », dans Ming-Yang Kao (éditeur), Encyclopedia of Algorithms, 2016 (ISBN 978-1-4939-2863-7), p. 203-207.

Fomine est coauteur de deux livres :

Fedor V. Fomin et Dieter Kratsch, Exact Exponential Algorithms, Springer, 2010, 203 p. (ISBN 978-3-642-16532-0, lire en ligne)
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk et Saket Saurabh, Parameterized Algorithms, Springer, 2015, 555 p. (ISBN 978-3-319-21274-6, lire en ligne)

Honneurs et récompenses

Fiodor Fomine a reçu en 2004 le Young Investigator Award du Conseil norvégien de la recherche. Il a reçu deux fois le prix IPEC Nerode attribué par l'European Association for Theoretical Computer Science^[3] :

une première fois en 2015, avec ses coauteurs Erik D. Demaine, Mohammad Hajiaghayi et Dimitrios M. Thilikos, pour leur article :

Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi et Dimitrios M. Thilikos, « Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs », Journal of the ACM, vol. 52, n^o 6,‎ 2005, p. 866–893 (ISSN 0004-5411, DOI 10.1145/1101821.1101823).

une deuxième fois en 2017, avec ses coauteurs Fabrizio Grandoni et Dieter Kratsch :

Fedor V. Fomin, Fabrizio Grandoni et Dieter Kratsch, « A measure & conquer approach for the analysis of exact algorithms », Journal of the ACM, vol. 56, n^o 5,‎ 2009, p. 1–32 (ISSN 0004-5411, DOI 10.1145/1552285.1552286)

Notes et références

↑ (en) « Fedor Vladimirovich Fomin », sur le site du Mathematics Genealogy Project.
↑ Par exemple : Pradeesha Ashok, Fedor V. Fomin, Sudeshna Kolay, Saket Saurabh et Meirav Zehavi, « Exact Algorithms for Terrain Guarding », ACM Transactions on Algorithms, vol. 14, n^o 2,‎ 2018, p. 1–20 (DOI 10.1145/3186897).
↑ « Nerode Prize » (consulté le 25 juin 2018)

Liens externes

Page personnelle de Fomine à l'université de Bergen
Publications de Fomine sur DBLP
Google Scholar
Notices d'autorité :
- VIAF
- ISNI
- IdRef
- LCCN
- GND
- Pologne
- Israël
- NUKAT
- WorldCat
Ressources relatives à la recherche :

Portail de l'informatique théorique

[1] (en) « Fedor Vladimirovich Fomin », sur le site du Mathematics Genealogy Project.

[AshokFomin2018-2] Par exemple : Pradeesha Ashok, Fedor V. Fomin, Sudeshna Kolay, Saket Saurabh et Meirav Zehavi, « Exact Algorithms for Terrain Guarding », ACM Transactions on Algorithms, vol. 14, n^o 2,‎ 2018, p. 1–20 (DOI 10.1145/3186897).

[3] « Nerode Prize » (consulté le 25 juin 2018)

[1]

[2]

[3]