ACRO : Algorithmique, Combinatoire et Recherche Opérationnelle

Keys Words

Graph Theory, Combinatorics of Structured Set Families, Metric Graph Theory, Graph Algorithms, Approximation Algorithms, Computational Geometry,
Combinatorial Optimization, Multiflows, Covering and Packing Problems, Classification and Data Analysis





Permanent Members

BARBANCHON RégisMaitre de Conférences
Courriel :
Telephone : 0486090453
BERNARD FichetMaitre de Conférences
Courriel :
BRUCKER FrancoisProfesseur des Universités
Courriel :
Telephone : 0486090486
CHEPOI VictorProfesseur des Universités
Courriel :
Telephone : 0486090459
Page personnelle :
COUETOUX BasileMaitre de Conférences
Courriel :
Telephone : 0486090461
Page personnelle :
ESTELLON BertrandMaitre de Conférences
Courriel :
Telephone : 0486090465
Page personnelle :
DIAS DA FONSECA GuilhermeProfesseur des Universités
Courriel :
GAMBINI IanMaitre de Conférences
Courriel :
Telephone : 0442913422
KNAUER KoljaMaitre de Conférences
Courriel :
Telephone : 0486090476
Page personnelle :
MASSAT Jean-LucMaitre de Conférences
Courriel :
Telephone : 0486090488
Page personnelle :
NAVES GuyslainMaitre de Conférences
Courriel :
Telephone : 0486090492
Page personnelle :
NOUIOUA KarimMaitre de Conférences
Courriel :
Telephone : 0486090494
Page personnelle :
PRÉA PascalMaitre de Conférences
Courriel :
Telephone : 0486090486
THIEL ÉdouardProfesseur des Universités
Courriel :
Telephone : 0486090682
Page personnelle :
VALICOV PetruMaitre de Conférences
Courriel :
Telephone : 0486090683
Page personnelle :
VAXES YannProfesseur des Universités
Courriel :
Telephone : 0486090684
Page personnelle :


Phd Studients

Courriel :
Telephone : 0486090483
CHATEL CéliaDoctorant
Courriel :
Telephone : 0491829070
Page personnelle :
PHILIBERT ManonDoctorant
Courriel :
RATEL SébastienDoctorant
Courriel :
Telephone : 0486090481
Page personnelle :


Other staff members

Research interests

The main activities of the research team ACRO ”Algorithmique, Combinatoire et Recherche Opérationnelle” concern the structural, combinatorial, geometric, and
algorithmic study of various discrete structures (graphs and networks, distances, cubical and simplicial complexes, set families, event structures) and the study of
combinatorial optimization problems.

The research work is performed on the following five themes:

  • Combinatorics, graphs, and distances
  • Graph and network algorithms, approximation algorithms
  • Computational and discrete geometry
  • Operations Research
  • Seriation and classification

The research team ACRO is a part of the “Theory of Computation” department (pôle Calcul) of LIS. Its five research themes contribute to the axis “Algorithms and Discrete Structures” (Algorithmique et Structures Discrètes) of this department.

A part of the theme “Combinatorics, graphs, and distances” and most research of the theme “Computational and discrete geometry” also contribute to the axis “Geometry and Topology of Computation” of this department. We also try to contribute to subjects issued from other axes of “Theory of Computation” and also from other departments of LIS. This allows us to enrich our research themes and to find new applications of our expertise in combinatorics, graph theory, algorithmics, combinatorial optimization, and classification.

This also allows to have an active collaboration with teams DALGO and MOVE and to start new collaborations with other teams.

The members of our team ACRO participate or have participated in the following ANR projects:

  • DISTANCIA « Metric Graph Theory » (2018-2021)
  • CAPPS « Combinatorial Analysis of Polytopes and Polyhedral Subdivisions » (2018-2021)
  • GATO « Graphes Algorithmes et TOpologie » (2016-2020)
  • GGAA « Aspects Géométriques, Analytiques et Algorithmiques des Groupes » (2010-2014)
  • TEOMATRO « Nouvelles Tendances dans les Matroides : Polytopes des bases, Structures, Algorithmes et Interactions » (2010-2013)
  • BOOLE « Quantifying Boolean Frameworks » (2009-2013)
  • ENUM « Algorithmes et complexité pour l’énumération » (2007-2011)
  • OPTICOMB « Optimisation Combinatoire » (2006-2010)


Scientific publications

10 documents

Article dans une revue

  • Jérémie Chalopin, Victor Chepoi, Feodor Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, et al.. Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs. Discrete and Computational Geometry, Springer Verlag, In press, ⟨10.1007/s00454-019-00107-9⟩. ⟨hal-02149991⟩
  • Victor Chepoi, Arnaud Labourel, Sébastien Ratel. On density of subgraphs of halved cubes. European Journal of Combinatorics, Elsevier, 2018. ⟨hal-01959093⟩
  • Jérémie Chalopin, Victor Chepoi, Hirai Hiroshi, Damian Osajda. Weakly modular graphs and nonpositive curvature. Memoirs of the American Mathematical Society, American Mathematical Society, In press. ⟨hal-01787197⟩
  • Jérémie Chalopin, Victor Chepoi, Damian Osajda. On two conjectures of Maurer concerning basis graphs of matroids. Journal of Combinatorial Theory, Series B, Elsevier, 2015, 114, pp.1-32. ⟨10.1016/j.jctb.2015.03.004⟩. ⟨hal-02065778⟩

Communication dans un congrès

  • Victor Chepoi, Feodor Dragan, Michel Habib, Yann Vaxès, Hend Alrasheed. Fast Approximation of Centrality and Distances in Hyperbolic Graphs. COCOA 2018 - 12th Annual International Conference on Combinatorial Optimization and Applications, Dec 2018, Atlanta, United States. pp.1-23. ⟨hal-01955263⟩
  • Jérémie Chalopin, Victor Chepoi, Feodor Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, et al.. Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs. 34th International Symposium on Computational Geometry (SoCG 2018), Jun 2018, Budapest, Hungary. pp.22, ⟨10.4230/LIPIcs.SoCG.2018.22⟩. ⟨hal-01836063⟩
  • Jérémie Chalopin, Victor Chepoi. A Counterexample to Thiagarajan's Conjecture on Regular Event Structures. ICALP 2017, 2017, Warsaw, Poland. ⟨10.4230/LIPIcs.ICALP.2017.101⟩. ⟨hal-01787205⟩

Pré-publication, Document de travail

  • Jérémie Chalopin, Victor Chepoi. 1-Safe Petri nets and special cube complexes: equivalence and applications. 2019. ⟨hal-01863455v2⟩
  • Jérémie Chalopin, Victor Chepoi, Shay Moran, Manfred K. Warmuth. Unlabeled sample compression schemes and corner peelings for ample and maximum classes. 2019. ⟨hal-02065772⟩
  • Jérémie Chalopin, Victor Chepoi, Feodor F. Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, et al.. Fast approximation and exact computation of negative curvature parameters of graphs. 2018. ⟨hal-01737445⟩