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

 

Head

Victor CHEPOI

 

Membres

BARBANCHON Regis  Enseignant-Chercheur / Chercheur
BENETEAU Laurine  Doctorant
BRUCKER Francois  Enseignant-Chercheur / Chercheur
CHEPOI Victor  Enseignant-Chercheur / Chercheur
COUETOUX Basile  Enseignant-Chercheur / Chercheur
DIAS DA FONSECA Guilherme  Enseignant-Chercheur / Chercheur
ESTELLON Bertrand  Enseignant-Chercheur / Chercheur
GAMBINI Ian  Enseignant-Chercheur / Chercheur
KNAUER Kolja  Enseignant-Chercheur / Chercheur
MASSAT Jean-Luc  Enseignant-Chercheur / Chercheur
MC INERNEY Fionn  Post-Docs / ATER / Ingenieurs
NAVES Guyslain  Enseignant-Chercheur / Chercheur
NOUIOUA Karim  Enseignant-Chercheur / Chercheur
PHILIBERT Manon  Doctorant
PREA Pascal  Enseignant-Chercheur / Chercheur
ROSENFELD Matthieu  Post-Docs / ATER / Ingenieurs
THIEL Edouard  Enseignant-Chercheur / Chercheur
VALICOV Petru  Enseignant-Chercheur / Chercheur
VAXES Yann  Enseignant-Chercheur / Chercheur


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



71 documents

Article dans une revue

  • Ignacio García-Marco, Kolja Knauer, Luis Pedro Montejano. Chomp on generalized Kneser graphs and others. International Journal of Game Theory, Springer Verlag, 2019, ⟨10.1007/s00182-019-00697-x⟩. ⟨hal-02068632⟩
  • Victor Chepoi, Arnaud Labourel, Sébastien Ratel. On density of subgraphs of halved cubes. European Journal of Combinatorics, Elsevier, 2019, 80, pp.57-70. ⟨10.1016/j.ejc.2018.02.039⟩. ⟨hal-02268756⟩
  • Victor Chepoi, Arnaud Labourel, Sébastien Ratel. On density of subgraphs of Cartesian products. Journal of Graph Theory, Wiley, 2019, 93 (1), pp.64-87. ⟨10.1002/jgt.22469⟩. ⟨hal-02443844⟩
  • Kolja Knauer, Petru Valicov. Cuts in matchings of 3-connected cubic graphs. European Journal of Combinatorics, Elsevier, 2019, 76, pp.27-36. ⟨10.1016/j.ejc.2018.09.004⟩. ⟨hal-02068863⟩
  • François Brucker, Pascal Prea, Célia Châtel. Totally Balanced Dissimilarities. Journal of Classification, Springer Verlag, 2019, ⟨10.1007/s00357-019-09320-w⟩. ⟨hal-02269391⟩
  • Victor Chepoi, Feodor Dragan, Michel Habib, Yann Vaxès, Hend Alrasheed. Fast approximation of eccentricities and distances in hyperbolic graphs. Journal of Graph Algorithms and Applications, Brown University, 2019, 23 (2), pp.393-433. ⟨10.7155/jgaa.00496⟩. ⟨hal-02268468⟩
  • Jérémie Chalopin, Victor Chepoi. 1-Safe Petri nets and special cube complexes: equivalence and applications. ACM Transactions on Computational Logic, Association for Computing Machinery, 2019, 20 (3), pp.17:1-17:49. ⟨10.1145/3322095⟩. ⟨hal-01863455v2⟩
  • Kolja Knauer, Torsten Ueckerdt. Decomposing 4-connected planar triangulations into two trees and one path. Journal of Combinatorial Theory, Series B, Elsevier, 2019, 134, pp.88-109. ⟨10.1016/j.jctb.2018.05.006⟩. ⟨hal-02068864⟩
  • 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, Kolja Knauer, Tilen Marc. Hypercellular graphs: Partial cubes without Q_3^- as partial cube minor. Discrete Mathematics, Elsevier, 2019. ⟨hal-02065775⟩
  • Kolja Knauer, Petru Valicov. Cuts in matchings of 3-connected cubic graphs. European Journal of Combinatorics, Elsevier, 2018, 76, ⟨10.1016/j.ejc.2018.09.004⟩. ⟨hal-01672548v2⟩
  • Kolja Knauer, Leonardo Martínez-Sandoval, Jorge Luis Ramírez Alfonsín. On Lattice Path Matroid Polytopes: Integer Points and Ehrhart Polynomial. Discrete and Computational Geometry, Springer Verlag, 2018, 60 (3), pp.698-719. ⟨10.1007/s00454-018-9965-4⟩. ⟨hal-02068868⟩
  • 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⟩
  • Hans-Jürgen Bandelt, Victor Chepoi, Kolja Knauer. COMs: Complexes of Oriented Matroids. Journal of Combinatorial Theory, Series A, Elsevier, 2018, 156, pp.195--237. ⟨hal-01457780⟩
  • Laurent Oxusoff, Pascal Prea, Yvan Perez. A complete logical approach to resolve the evolution and dynamics of mitochondrial genome in bilaterians. PLoS ONE, Public Library of Science, 2018, 13 (3), pp.e0194334. ⟨10.1371/journal.pone.0194334⟩. ⟨hal-01765687⟩
  • Victor Chepoi. Distance-Preserving Subgraphs of Johnson Graphs. Combinatorica, Springer Verlag, 2017, 37 (6), pp.1039-1055. ⟨10.1007/s00493-016-3421-y⟩. ⟨hal-02268710⟩
  • Rémi Desgranges, Kolja Knauer. A correction of a characterization of planar partial cubes. Discrete Mathematics, Elsevier, 2017. ⟨hal-01457179⟩
  • Victor Chepoi, Bertrand Estellon, Guyslain Naves. Packing and Covering with Balls on Busemann Surfaces. Discrete and Computational Geometry, Springer Verlag, 2017, 57 (4), pp.985-1011. ⟨10.1007/s00454-017-9872-0⟩. ⟨hal-02268712⟩
  • Basile Couëtoux, Elie Nakache, Yann Vaxès. The Maximum Labeled Path Problem. Algorithmica, Springer Verlag, 2017, 78 (1), pp.298 - 318. ⟨10.1007/s00453-016-0155-6⟩. ⟨hal-01769613⟩
  • Nicolas Catusse, Victor Chepoi, Karim Nouioua, Yann Vaxès. Bidirected minimum Manhattan network problem. Networks, Wiley, 2017, 69 (2), pp.167-178. ⟨10.1002/net.21719⟩. ⟨hal-02268714⟩
  • Pierre Bonami, Dorian Mazauric, Yann Vaxès. Maximum flow under proportional delay constraint. Theoretical Computer Science, Elsevier, 2017, 689, pp.58-66. ⟨10.1016/j.tcs.2017.05.034⟩. ⟨hal-01571232⟩
  • Pascal Préa, Mathieu Rouault, François Brucker. An Optimal Algorithm to Generate Extendable Self-Avoiding Walks in Arbitrary Dimension. Electronic Notes in Discrete Mathematics, Elsevier, 2017. ⟨hal-01790908⟩
  • Boris Albar, Daniel Gonçalves, Kolja Knauer. Orienting Triangulations. Journal of Graph Theory, Wiley, 2016, 83 (4), pp.392-405. ⟨10.1002/jgt.22005⟩. ⟨hal-01457782⟩
  • Ignacio García-Marco, Kolja Knauer. Drawing graphs with vertices and edges in convex position. Computational Geometry, Elsevier, 2016, 58, pp.25-33. ⟨10.1016/j.comgeo.2016.06.002⟩. ⟨hal-01457727⟩
  • Ian Gambini, Laurent Vuillon. Tiling the Space by Polycube Analogues of Fedorov’s Polyhedra. Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2016, 146 (2), pp.197-209. ⟨10.3233/FI-2016-1381⟩. ⟨hal-02269399⟩
  • Stefan Felsner, Kolja Knauer, George Mertzios, Torsten Ueckerdt. Intersection Graphs of L-Shapes and Segments in the Plane. Discrete Applied Mathematics, Elsevier, 2016, 206, pp.48-55. ⟨10.1016/j.dam.2016.01.028⟩. ⟨hal-01457800⟩
  • Marie Albenque, Kolja Knauer. Convexity in partial cubes: the hull number. Discrete Mathematics, Elsevier, 2016, 339 (2), pp.866-876. ⟨10.1016/j.disc.2015.10.032⟩. ⟨hal-01457877⟩
  • Kolja Knauer, Leonardo Martínez-Sandoval, Jorge Luis Ramírez Alfonsín. A Tutte polynomial inequality for lattice path matroids. Advances in Applied Mathematics, Elsevier, 2016, 94, pp.23-38. ⟨10.1016/j.aam.2016.11.008⟩. ⟨hal-01457675⟩
  • Kolja Knauer, Ulrich Knauer. On planar right groups. Semigroup Forum, Springer Verlag, 2016, 92, pp.142 - 157. ⟨10.1007/s00233-015-9688-2⟩. ⟨hal-01457892⟩
  • Bartłomiej Bosek, Stefan Felsner, Kolja Knauer, Grzegorz Matecki. On the Duality of Semiantichains and Unichain Coverings. Order, Springer Verlag, 2016. ⟨hal-01457982⟩
  • Kolja Knauer, Torsten Ueckerdt. Three ways to cover a graph. Discrete Mathematics, Elsevier, 2016, 339, pp.745 - 758. ⟨10.1016/j.disc.2015.10.023⟩. ⟨hal-01457977⟩
  • Hans-Jürgen Bandelt, Victor Chepoi, David Eppstein. Ramified Rectilinear Polygons: Coordinatization by Dendrons. Discrete and Computational Geometry, Springer Verlag, 2015, 54 (4), pp.771-797. ⟨10.1007/s00454-015-9743-5⟩. ⟨hal-02268742⟩
  • 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⟩
  • Victor Chepoi, Damian Osajda. Dismantlability of weakly systolic complexes and applications. Transactions of the American Mathematical Society, American Mathematical Society, 2015, 367, pp.1247-1272. ⟨hal-01199906⟩
  • Jérémie Chalopin, Victor Chepoi, Guyslain Naves. Isometric Embedding of Busemann Surfaces into $L_1$. Discrete and Computational Geometry, Springer Verlag, 2015, 53 (1), pp.16-37. ⟨10.1007/s00454-014-9643-0⟩. ⟨hal-02268738⟩
  • Pascal Préa, Monique Rolbert. Distinguishing and Classifying from n-ary Properties. Journal of Classification, Springer Verlag, 2014, 31 (1), pp.28-48. ⟨10.1007/s00357-014-9151-1⟩. ⟨hal-02435796⟩
  • Kolja Knauer, Piotr Micek, Bartosz Walczak. Outerplanar graph drawings with few slopes ✩. Computational Geometry: Theory and Applications Computational Geometry @ ScienceDirect, 2014. ⟨hal-01457974⟩
  • Kolja Knauer, Juan Montellano-Ballesteros, Ricardo Strausz. A graph-theoretical axiomatization of oriented matroids. European Journal of Combinatorics, Elsevier, 2014. ⟨hal-01457945⟩
  • Jean Cardinal, Kolja Knauer, Piotr Micek, Torsten Ueckerdt. Making Octants Colorful and Related Covering Decomposition Problems. SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2014. ⟨hal-01457899⟩
  • Pascal Préa, Dominique Fortin. An Optimal Algorithm To Recognize Robinsonian Dissimilarities. Journal of Classification, Springer Verlag, 2014. ⟨hal-02435793⟩
  • Maria Axenovich, Kolja Knauer, Judith Stumpp, Torsten Ueckerdt. Online and size anti-Ramsey numbers. Journal of Combinatorics, International Press, 2014, 5, pp.87 - 114. ⟨10.4310/JOC.2014.v5.n1.a4⟩. ⟨hal-01457849⟩
  • Daniel Heldt, Kolja Knauer, Torsten Ueckerdt. On the bend-number of planar and outerplanar graphs. Discrete Applied Mathematics, Elsevier, 2014. ⟨hal-01457986⟩
  • Daniel Heldt, Kolja Knauer, Torsten Ueckerdt. Edge-intersection graphs of grid paths: The bend-number. Discrete Applied Mathematics, Elsevier, 2014, 167, pp.144 - 162. ⟨10.1016/j.dam.2013.10.035⟩. ⟨hal-01457989⟩

Communication dans un congrès

  • Rahul Arya, Sunil Arya, Guilherme da Fonseca, David Mount. Optimal Bound on the Combinatorial Complexity of Approximating Polytopes. SODA 2020, Jan 2020, Salt Lake City, United States. pp.786-805, ⟨10.1137/1.9781611975994.48⟩. ⟨hal-02440482⟩
  • Victor Chepoi, Arnaud Labourel, Sébastien Ratel. Distance and routing labeling schemes for cube-free median graphs. 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), 2019, Aachen, Germany. pp.15:1--15:14, ⟨10.4230/LIPIcs.MFCS.2019.15⟩. ⟨hal-02268771⟩
  • Jérémie Chalopin, Victor Chepoi, Shay Moran, Manfred Warmuth. Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes. 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), 2019, Patras, Greece. pp.34:1--34:15, ⟨10.4230/LIPIcs.ICALP.2019.34⟩. ⟨hal-02269141⟩
  • 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⟩
  • Victor Chepoi, Feodor Dragan, Yann Vaxès. Core congestion is inherent in hyperbolic networks. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, Barcelona, Spain. pp.2264-2279. ⟨hal-02268729⟩
  • 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⟩
  • Kolja Knauer, Bartosz Walczak. Graph Drawings with One Bend and Few Slopes. LATIN 2016, Apr 2016, Ensenada, Mexico. pp.549 - 561, ⟨10.1007/978-3-662-49529-2_41⟩. ⟨hal-01457778⟩
  • François Brucker, Pascal Préa. Approximate Seriation in Formal Concept Analysis. CLA, 2016, Moscou, Russia. ⟨hal-02435801⟩
  • Ignacio García-Marco, Kolja Knauer. Drawing graphs with vertices and edges in convex position. Graph Drawing 2015, Sep 2015, Los Angeles, United States. ⟨hal-01457773⟩
  • François Brucker, Pascal Préa. Totally Balanced Formal Context Representation. ICFCA, 2015, Malaga, Spain. ⟨hal-02435802⟩
  • Stefan Felsner, Kolja Knauer, George Mertzios, Torsten Ueckerdt. Intersection Graphs of L-Shapes and Segments in the Plane. MFCS 2014, Aug 2014, Budapest, Hungary. ⟨hal-01457818⟩
  • Basile Couëtoux, Elie Nakache, Yann Vaxès. The Maximum Labeled Path Problem. 40th International Workshop, WG 2014, Jun 2014, Nouan-le-Fuzelier, France. pp.152-163, ⟨10.1007/978-3-319-12340-0_13⟩. ⟨hal-01195672⟩
  • Marie Albenque, Kolja Knauer. Convexity in partial cubes: the hull number. LATIN 2014, Mar 2014, Montevideo, Uruguay. ⟨hal-01457880⟩
  • Jean Cardinal, Kolja Knauer, Piotr Micek, Torsten Ueckerdt. Making Octants Colorful and Related Covering Decomposition Problems. SODA 2014, Jan 2014, Portland, United States. ⟨hal-01457914⟩
  • Pascal Préa. Fractal Self-Avoiding Walks. GASCom, 2012, Bordeaux, France. ⟨hal-02435803⟩

Chapitre d'ouvrage

  • Kolja Knauer, Piotr Micek, Torsten Ueckerdt. The Queue-Number of Posets of Bounded Width or Height. International Symposium on Graph Drawing and Network Visualization GD 2018: Graph Drawing and Network Visualization, 2018, ⟨10.1007/978-3-030-04414-5_14⟩. ⟨hal-02068620⟩

Pré-publication, Document de travail

  • Victor Chepoi, Kolja Knauer, Manon Philibert. Two-dimensional partial cubes. 2020. ⟨hal-02268768⟩
  • Guyslain Naves, Bruce Shepherd. When Do Gomory-Hu Subtrees Exist?. 2020. ⟨hal-02436804⟩
  • François Brucker, Pascal Préa, Célia Châtel. Binary set systems and totally balanced hypergraphs. 2020. ⟨hal-02436247⟩
  • Petru Valicov. (2, 3)-bipartite graphs are strongly 6-edge-choosable. 2020. ⟨hal-02436240⟩
  • Guillaume Guegan, Kolja Knauer, Jonathan Rollin, Torsten Ueckerdt. The interval number of a planar graph is at most three. 2019. ⟨hal-02068628⟩
  • 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⟩
  • Kolja Knauer, Leonardo Martínez-Sandoval, Jorge Luis Ramírez Alfonsín. On lattice path matroid polytopes: integer points and Ehrhart polynomial. 2017. ⟨hal-01457185⟩
  • Victor Chepoi, Kolja Knauer, Marc Tilen. Partial cubes without Q − 3 minors. 2017. ⟨hal-01457191⟩

Thèse

  • Sébastien Ratel. Densité, VC-dimension et étiquetages de graphes. Mathématique discrète [cs.DM]. Aix-Marseile Université, 2019. Français. ⟨tel-02436255⟩
  • Célia Châtel. Modèles de classification en classes empiétantes, cas des modèles arborés. Informatique [cs]. Aix Marseille Université, 2018. Français. ⟨tel-02436273⟩