Logo

Algorithms, Combinatorics, and Operations Research

Powered by Jekyll—theme by BDHU. Something wrong? Please contact Oscar Defrain.

Publications

Here is the publication list of ACRO members; see also the HAL repository.
Journal Conference Preprint Thesis

2024

  1. Oscar Defrain and Jean-Florent Raymond. Sparse graphs without long induced paths. Journal of Combinatorial Theory, Series B 166: 30–49 (2024) DOI
  2. Laurent Beaudou, Caroline Brosse, Oscar Defrain, Florent Foucaud, Aurélie Lagoutte, Vincent Limouzy, and Lucas Pastor. Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly. To appear in Discret. Math. Theor. Comput. Sci. (2024)
  3. Caroline Brosse, Oscar Defrain, Kazuhiro Kurita, Vincent Limouzy, Takeaki Uno, and Kunihiro Wasa. On the hardness of inclusion-wise minimal separators enumeration. Inf. Process. Lett. 185: 106469 (2024) DOI
  4. Nadia Creignou, Oscar Defrain, Frédéric Olive, and Simon Vilmin. On the enumeration of signatures of XOR-CNF’s. CoRR abs/2402.18537 (2024) arXiv
  5. Guilherme D. da Fonseca, Yan Gerard, and Bastien Rivier. Short Flip Sequences to Untangle Segments in the Plane. International Conference and Workshops on Algorithms and Computation (WALCOM 2024), 163–178 (2024) DOI arXiv

2023

  1. Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, and Jean-Florent Raymond. Local certification of geometric graph classes. CoRR abs/2311.16953 (2023) arXiv
  2. Benjamin Bergougnoux, Oscar Defrain, and Fionn Mc Inerney. Enumerating minimal solution sets for metric graph problems. CoRR abs/2309.17419 (2023) arXiv
  3. Caroline Brosse, Oscar Defrain, Kazuhiro Kurita, Vincent Limouzy, Takeaki Uno, and Kunihiro Wasa. On the hardness of inclusion-wise minimal separators enumeration. CoRR abs/2308.15444 (2023) arXiv
  4. Marthe Bonamy, Oscar Defrain, Tereza Klimošová, Aurélie Lagoutte, and Jonathan Narboni. On Vizing’s edge colouring question. Journal of Combinatorial Theory, Series B 159: 126–139 (2023) DOI
  5. Valentin Bartier, Oscar Defrain, and Fionn Mc Inerney. Minimal dominating sets enumeration with FPT-delay parameterized by the degeneracy and maximum degree. CoRR abs/2305.06974 (2023) arXiv
  6. Oscar Defrain and Jean-Florent Raymond. Sparse graphs without long induced paths. CoRR abs/2304.09679 (2023) arXiv
  7. Arun Kumar Das, Sandip Das, Guilherme D. da Fonseca, Yan Gerard, and Bastien Rivier. Complexity Results on Untangling Red-Blue Matchings. Computational Geometry 111: 101974 (2023) DOI arXiv
  8. Loïc Crombez, Guilherme D. da Fonseca, Florian Fontan, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, Luc Libralesso, Benjamin Momege, Jack Spalding-Jamieson, Brandon Zhang, et al. Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring. ACM Journal of Experimental Algorithmics 28: 1–13 (2023) DOI arXiv
  9. Guilherme D. da Fonseca, Yan Gerard, and Bastien Rivier. On the Longest Flip Sequence to Untangle Segments in the Plane. International Conference and Workshops on Algorithms and Computation (WALCOM 2023), 102–112 (2023) DOI arXiv
  10. Sunil Arya, Guilherme D. da Fonseca, and David M. Mount. Economical Convex Coverings and Applications. ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), 1834–1861 (2023) DOI arXiv
  11. Guilherme D. da Fonseca. Shadoks Approach to Convex Covering. 39th International Symposium on Computational Geometry (SoCG 2023), 67:1–67:9 (2023) DOI arXiv
  12. François Hamonic, Cécile Albert, Basile Couëtoux, and Yann Vaxès. Optimizing the ecological connectivity of landscapes. Networks 81, 2: 278–293 (2023) DOI
  13. Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel, and Yann Vaxès. Sample Compression Schemes for Balls in Graphs. SIAM J. Discret. Math. 37, 4: 2585–2616 (2023) DOI
  14. Dibyayan Chakraborty, Jérémie Chalopin, Florent Foucaud, and Yann Vaxès. Isometric Path Complexity of Graphs. 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 32:1–32:14 (2023) DOI

2022

  1. Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. Distance labeling schemes for $K_4$-free bridged graphs. Inf. Comput. 289, Part: 104959 (2022) DOI
  2. Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi, and Yann Vaxès. Medians in median graphs and their cube complexes in linear time. J. Comput. Syst. Sci. 126: 80–105 (2022) DOI
  3. Jérémie Chalopin, Victor Chepoi, Shay Moran, and Manfred K. Warmuth. Unlabeled sample compression schemes and corner peelings for ample and maximum classes. J. Comput. Syst. Sci. 127: 1–28 (2022) DOI
  4. Victor Chepoi, Kolja Knauer, and Manon Philibert. Ample Completions of Oriented Matroids and Complexes of Uniform Oriented Matroids. SIAM J. Discret. Math. 36, 1: 509–535 (2022) DOI
  5. Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel, and Yann Vaxès. Sample Compression Schemes for Balls in Graphs. 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, August 22-26, 2022, Vienna, Austria, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 31:1–31:14 (2022) DOI
  6. Jérémie Chalopin, Victor Chepoi, and Ugo Giocanti. Graphs with convex balls. CoRR abs/2201.01599 (2022) arXiv
  7. Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi, and Yann Vaxès. Graphs with $G^p$-connected medians. CoRR abs/2201.12248 (2022) arXiv
  8. Jérémie Chalopin, Manoj Changat, Victor Chepoi, and Jeny Jacob. First-order logic axiomatization of metric graph theory. CoRR abs/2203.01070 (2022) arXiv
  9. Mikhael Carmona, Victor Chepoi, Guyslain Naves, and Pascal Préa. Modules in Robinson Spaces. CoRR abs/2203.12386 (2022) arXiv
  10. Mikhael Carmona, Victor Chepoi, Guyslain Naves, and Pascal Préa. A simple and optimal algorithm for strict circular seriation. CoRR abs/2205.04694 (2022) arXiv
  11. Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi, and Yann Vaxès. ABC(T)-graphs: an axiomatic characterization of the median procedure in graphs with connected and $G^2$-connected medians. CoRR abs/2206.03587 (2022) arXiv
  12. Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel, and Yann Vaxès. Sample compression schemes for balls in graphs. CoRR abs/2206.13254 (2022) arXiv
  13. Raphael Sturgis, Valentin Emiya, Basile Couëtoux, and Pierre Garreau. Vessel Behaviour Classification from AIS Without Geographical Biases. 25th IEEE International Conference on Intelligent Transportation Systems, ITSC 2022, Macau, China, October 8-12, 2022, IEEE, 2465–2470 (2022) DOI
  14. Łukasz Bożyk, Oscar Defrain, Karolina Okrasa, and Michał Pilipczuk. On objects dual to tree-cut decompositions. J. Comb. Theory, Ser. B 157: 401–428 (2022) DOI
  15. Łukasz Bożyk, Oscar Defrain, Karolina Okrasa, and Michał Pilipczuk. On digraphs without onion star immersions. CoRR abs/2211.15477 (2022) arXiv
  16. Loïc Crombez, Guilherme D. da Fonseca, and Yan Gerard. Greedy and Local Search Heuristics to Build Area-Optimal Polygons. ACM Journal of Experimental Algorithms 27: 1–11 (2022) DOI
  17. Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, and Luc Libralesso. Shadoks Approach to Low-Makespan Coordinated Motion Planning. ACM Journal of Experimental Algorithms 27: 1–17 (2022) DOI arXiv
  18. Rahul Arya, Sunil Arya, Guilherme D. da Fonseca, and David M. Mount. Optimal Bound on the Combinatorial Complexity of Approximating Polytopes. ACM Transactions on Algorithms 18, 4: 1–29 (2022) DOI arXiv
  19. Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, and Aldo Gonzalez-Lorenzo. Shadoks Approach to Minimum Partition into Plane Subgraphs. 38th International Symposium on Computational Geometry (SoCG 2022), 71:1–71:8 (2022) DOI
  20. Arun Kumar Das, Sandip Das, Guilherme D. da Fonseca, Yan Gerard, and Bastien Rivier. Complexity Results on Untangling Red-Blue Matchings. 15th Latin American Theoretical Informatics Symposium (LATIN 2022), 730–745 (2022) DOI arXiv
  21. François Hamonic, Cécile Albert, Basile Couëtoux, and Yann Vaxès. Optimizing the ecological connectivity of landscapes. Networks: 1–16 (2022) DOI
  22. Pierre Aboulker, Frédéric Havet, Kolja Knauer, and Clément Rambaud. On the Dichromatic Number of Surfaces. Electron. J. Comb. 29, 1 (2022) DOI
  23. Kolja Knauer, Hoang La, and Petru Valicov. Feedback Vertex Sets in (Directed) Graphs of Bounded Degeneracy or Treewidth. Electron. J. Comb. 29, 4 (2022) DOI
  24. Garcı́a-Marco Ignacio and Kolja Knauer. On sensitivity in bipartite Cayley graphs. J. Comb. Theory, Ser. B 154: 211–238 (2022) DOI
  25. Garcı́a-Marco Ignacio and Kolja Knauer. Beyond symmetry in generalized Petersen graphs. CoRR abs/2202.06785 (2022) arXiv
  26. Carolina Benedetti and Kolja Knauer. Lattice path matroids and quotients. CoRR abs/2202.11634 (2022) arXiv
  27. Guyslain Naves and F. Bruce Shepherd. When Do Gomory-Hu Subtrees Exist? SIAM J. Discret. Math. 36, 3: 1567–1585 (2022) DOI
  28. Edouard Thiel. On the Validity of the Two Raster Sequences Distance Transform Algorithm. Discrete Geometry and Mathematical Morphology - Second International Joint Conference, DGMM 2022, Strasbourg, France, October 24-27, 2022, Proceedings, Springer, 436–446 (2022) DOI

2021

  1. Valentin Bartier, Laurine Bénéteau, Marthe Bonamy, Hoang La, and Jonathan Narboni. A note on deterministic zombies. Discret. Appl. Math. 301: 65–68 (2021) DOI
  2. Célia Châtel, François Brucker, and Pascal Préa. Binary set systems and totally balanced hypergraphs. Discret. Appl. Math. 295: 120–133 (2021) DOI
  3. Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. Distance and Routing Labeling Schemes for Cube-Free Median Graphs. Algorithmica 83, 1: 252–296 (2021) DOI
  4. Jérémie Chalopin, Victor Chepoi, Feodor F. Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, and Yann Vaxès. Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs. Discret. Comput. Geom. 65, 3: 856–892 (2021) DOI
  5. Victor Chepoi, Kolja Knauer, and Manon Philibert. Labeled sample compression schemes for complexes of oriented matroids. CoRR abs/2110.15168 (2021) arXiv
  6. François Hamonic, Cécile Albert, Basile Couëtoux, and Yann Vaxès. Optimizing the ecological connectivity of landscapes with generalized flow models and preprocessing. CoRR abs/2109.06622 (2021) arXiv
  7. Marthe Bonamy, Oscar Defrain, Tereza Klimosová, Aurélie Lagoutte, and Jonathan Narboni. On Vizing’s edge colouring question. CoRR abs/2107.07900 (2021) arXiv
  8. Laurent Beaudou, Caroline Brosse, Oscar Defrain, Florent Foucaud, Aurélie Lagoutte, Vincent Limouzy, and Lucas Pastor. Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly. CoRR abs/2110.14003 (2021) arXiv
  9. Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, and Luc Libralesso. Shadoks Approach to Low-Makespan Coordinated Motion Planning. 37th International Symposium on Computational Geometry (SoCG 2021), 63:1–63:9 (2021) DOI arXiv
  10. Oswin Aichholzer, Jean Cardinal, Tony Huynh, Kolja Knauer, Torsten Mütze, Raphael Steiner, and Birgit Vogtenhuber. Flip Distances Between Graph Orientations. Algorithmica 83, 1: 116–143 (2021) DOI
  11. Garcı́a-Marco Ignacio, Kolja Knauer, and Luis Pedro Montejano. Chomp on generalized Kneser graphs and others. Int. J. Game Theory 50, 3: 603–621 (2021) DOI
  12. Guillaume Guégan, Kolja Knauer, Jonathan Rollin, and Torsten Ueckerdt. The interval number of a planar graph is at most three. J. Comb. Theory, Ser. B 146: 61–67 (2021) DOI
  13. Pierre Aboulker, Frédéric Havet, Kolja Knauer, and Clément Rambaud. On the dichromatic number of surfaces. CoRR abs/2102.01034 (2021) arXiv
  14. Kolja Knauer and Gil Puig i Surroca. On monoid graphs. CoRR abs/2110.00993 (2021) arXiv
  15. Kolja Knauer, Hoang La, and Petru Valicov. Feedback vertex sets in (directed) graphs of bounded degeneracy or treewidth. CoRR abs/2111.14986 (2021) arXiv
  16. Guyslain Naves, F. Bruce Shepherd, and Henry Xia. Maximum Weight Disjoint Paths in Outerplanar Graphs via Single-Tree Cut Approximators. Integer Programming and Combinatorial Optimization - 22nd International Conference, IPCO 2021, Atlanta, GA, USA, May 19-21, 2021, Proceedings, Springer, 326–339 (2021) DOI
  17. Manon Philibert. Cubes partiels: complétion, compression, plongement. (Partial cubes: completion, compression, embedding). Retrieved from https://tel.archives-ouvertes.fr/tel-03581541 (2021)
  18. Matthieu Rosenfeld. Lower-Bounds on the Growth of Power-Free Languages Over Large Alphabets. Theory Comput. Syst. 65, 7: 1110–1116 (2021) DOI
  19. Matthieu Rosenfeld. The Growth Rate Over Trees Of Any Family Of Sets Defined By A Monadic Second Order Formula Is Semi-computable. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, SIAM, 776–795 (2021) DOI

2020

  1. Valentin Bartier, Laurine Bénéteau, Marthe Bonamy, Hoang La, and Jonathan Narboni. A note on deterministic zombies. CoRR abs/2008.03587 (2020) arXiv
  2. François Brucker, Pascal Préa, and Célia Châtel. Totally Balanced Dissimilarities. J. Classif. 37, 1: 203–222 (2020) DOI
  3. Victor Chepoi, Kolja Knauer, and Manon Philibert. Two-Dimensional Partial Cubes. Electron. J. Comb. 27, 3: 3 (2020) DOI
  4. Victor Chepoi, Kolja Knauer, and Tilen Marc. Hypercellular graphs: Partial cubes without Q3- as partial cube minor. Discret. Math. 343, 4: 111678 (2020) DOI
  5. Jérémie Chalopin and Victor Chepoi. A counterexample to Thiagarajan’s conjecture on regular event structures. J. Comput. Syst. Sci. 113: 76–100 (2020) DOI
  6. Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. On density of subgraphs of Cartesian products. J. Graph Theory 93, 1: 64–87 (2020) DOI
  7. Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi, and Yann Vaxès. Medians in Median Graphs and Their Cube Complexes in Linear Time. 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 10:1–10:17 (2020) DOI
  8. Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. Distance Labeling Schemes for $K_4$-Free Bridged Graphs. Structural Information and Communication Complexity - 27th International Colloquium, SIROCCO 2020, Paderborn, Germany, June 29 - July 1, 2020, Proceedings, Springer, 310–327 (2020) DOI
  9. Victor Chepoi, Kolja Knauer, and Manon Philibert. Ample completions of OMs and CUOMs. CoRR abs/2007.12527 (2020) arXiv
  10. Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. Distance labeling schemes for $K_4$-free bridged graphs. CoRR abs/2007.14192 (2020) arXiv
  11. Gautam K. Das, Guilherme D. da Fonseca, and Ramesh K. Jallu. Efficient Independent Set Approximation in Unit Disk Graphs. Discrete Applied Mathematics 280: 63–70 (2020) DOI
  12. Loïc Crombez, Guilherme D. da Fonseca, and Yan Gerard. Efficient Algorithms to Test Digital Convexity. Journal of Mathematical Imaging and Vision 62: 693–703 (2020) DOI
  13. Rahul Arya, Sunil Arya, Guilherme D. da Fonseca, and David M. Mount. Optimal Bound on the Combinatorial Complexity of Approximating Polytopes. ACM-SIAM Symposium on Discrete Algorithms (SODA), 786–805 (2020) DOI arXiv
  14. Loïc Crombez, Guilherme D. da Fonseca, and Yan Gerard. Efficient Algorithms for Battleship. International Conference on Fun with Algorithms (FUN 2020), 11:1–15 (2020) DOI arXiv
  15. Sarah Blind, Kolja Knauer, and Petru Valicov. Enumerating k-Arc-Connected Orientations. Algorithmica 82, 12: 3588–3603 (2020) DOI
  16. Stefan Felsner, Winfried Hochstättler, Kolja Knauer, and Raphael Steiner. Complete Acyclic Colorings. Electron. J. Comb. 27, 2: 2 (2020) DOI
  17. Kolja Knauer and Tilen Marc. On Tope Graphs of Complexes of Oriented Matroids. Discret. Comput. Geom. 63, 2: 377–417 (2020) DOI
  18. Stefan Felsner, Kolja Knauer, and Torsten Ueckerdt. Plattenbauten: Touching Rectangles in Space. Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Leeds, UK, June 24-26, 2020, Revised Selected Papers, Springer, 161–173 (2020) DOI
  19. Stefan Felsner, Kolja Knauer, and Torsten Ueckerdt. Plattenbauten: Touching Rectangles in Space. CoRR abs/2007.07806 (2020) arXiv
  20. Garcı́a-Marco Ignacio and Kolja Knauer. On sensitivity in bipartite Cayley graphs. CoRR abs/2009.00554 (2020) arXiv
  21. Guyslain Naves, F. Bruce Shepherd, and Henry Xia. Maximum Weight Disjoint Paths in Outerplanar Graphs via Single-Tree Cut Approximators. CoRR abs/2007.10537 (2020) arXiv
  22. Marie Lejeune, Michel Rigo, and Matthieu Rosenfeld. On the binomial equivalence classes of finite words. CoRR abs/2001.11732 (2020) arXiv
  23. Marie Lejeune, Michel Rigo, and Matthieu Rosenfeld. The binomial equivalence classes of finite words. Int. J. Algebra Comput. 30, 07: 1375–1397 (2020) DOI
  24. Matthieu Rosenfeld. Another approach to non-repetitive colorings of graphs of bounded degree. CoRR abs/2006.09094 (2020) arXiv
  25. Matthieu Rosenfeld. Lower-bounds on the growth of power-free languages over large alphabets. CoRR abs/2008.05192 (2020) arXiv

2019

  1. Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. On density of subgraphs of halved cubes. Eur. J. Comb. 80: 57–70 (2019) DOI
  2. Victor Chepoi, Feodor F. Dragan, Michel Habib, Yann Vaxès, and Hend Alrasheed. Fast approximation of eccentricities and distances in hyperbolic graphs. J. Graph Algorithms Appl. 23, 2: 393–433 (2019) DOI
  3. Jérémie Chalopin and Victor Chepoi. 1-Safe Petri Nets and Special Cube Complexes: Equivalence and Applications. ACM Trans. Comput. Log. 20, 3: 17:1–17:49 (2019) DOI
  4. Jérémie Chalopin, Victor Chepoi, Shay Moran, and Manfred K. Warmuth. Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes. 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 34:1–34:15 (2019) DOI
  5. Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. Distance Labeling Schemes for Cube-Free Median Graphs. 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 15:1–15:14 (2019) DOI
  6. Victor Chepoi, Kolja Knauer, and Manon Philibert. Two-dimensional partial cubes. CoRR abs/1906.04492 (2019) arXiv
  7. Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi, and Yann Vaxès. Medians in median graphs in linear time. CoRR abs/1907.10398 (2019) arXiv
  8. Ahmed Abdelkader, Sunil Arya, Guilherme D. da Fonseca, and David M. Mount. Approximate Nearest Neighbor Searching with Non-Euclidean and Weighted Distances. ACM-SIAM Symposium on Discrete Algorithms (SODA), 355–372 (2019) DOI
  9. Loïc Crombez, Guilherme D. da Fonseca, and Yan Gérard. Efficient Algorithms to Test Digital Convexity. International Conference on Discrete Geometry for Computer Imagery (DGCI), 409–419 (2019) DOI arXiv
  10. Loïc Crombez, Guilherme D. da Fonseca, and Yan Gérard. Peeling Digital Potatoes. Canadian Conference in Computational Geometry (CCCG), 124–132 (2019) arXiv
  11. Kolja Knauer and Nicolas Nisse. Computing metric hulls in graphs. Discret. Math. Theor. Comput. Sci. 21, 1 (2019)
  12. Kolja Knauer and Petru Valicov. Cuts in matchings of 3-connected cubic graphs. Eur. J. Comb. 76: 27–36 (2019) DOI
  13. Kolja Knauer and Torsten Ueckerdt. Decomposing 4-connected planar triangulations into two trees and one path. J. Comb. Theory, Ser. B 134: 88–109 (2019) DOI
  14. Kolja Knauer, Daniel Gonçalves, and Benjamin Lévêque. On the structure of Schnyder woods on orientable surfaces. J. Comput. Geom. 10, 1: 127–163 (2019) DOI
  15. Oswin Aichholzer, Jean Cardinal, Tony Huynh, Kolja Knauer, Torsten Mütze, Raphael Steiner, and Birgit Vogtenhuber. Flip Distances Between Graph Orientations. Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19-21, 2019, Revised Papers, Springer, 120–134 (2019) DOI
  16. Oswin Aichholzer, Jean Cardinal, Tony Huynh, Kolja Knauer, Torsten Mütze, Raphael Steiner, and Birgit Vogtenhuber. Flip distances between graph orientations. CoRR abs/1902.06103 (2019) arXiv
  17. Sandi Klavzar, Kolja Knauer, and Tilen Marc. On the Djoković-Winkler relation and its closure in subdivisions of fullerenes, triangulations, and chordal graphs. CoRR abs/1906.06111 (2019) arXiv
  18. Sarah Blind, Kolja Knauer, and Petru Valicov. Enumerating k-arc-connected orientations. CoRR abs/1908.02050 (2019) arXiv
  19. Émilie Charlier, Manon Philibert, and Manon Stipulanti. Nyldon words. J. Comb. Theory, Ser. A 167: 60–90 (2019) DOI

2018

  1. Célia Châtel, François Brucker, and Pascal Préa. Binary Lattices. Proceedings of the 6th International Workshop "What can FCA do for Artificial Intelligence"? co-located with International Joint Conference on Artificial Intelligence and European Conference on Artificial Intelligence (IJCAI/ECAI 2018), Stockholm, Sweden, July 13, 2018, CEUR-WS.org, 93–104 (2018)
  2. Hans-Jürgen Bandelt, Victor Chepoi, and Kolja Knauer. COMs: Complexes of oriented matroids. J. Comb. Theory, Ser. A 156: 195–237 (2018) DOI
  3. Victor Chepoi, Feodor F. Dragan, Michel Habib, Yann Vaxès, and Hend Alrasheed. Fast Approximation of Centrality and Distances in Hyperbolic Graphs. Combinatorial Optimization and Applications - 12th International Conference, COCOA 2018, Atlanta, GA, USA, December 15-17, 2018, Proceedings, Springer, 3–18 (2018) DOI
  4. Jérémie Chalopin, Victor Chepoi, Feodor F. Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, and Yann Vaxès. Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs. 34th International Symposium on Computational Geometry, SoCG 2018, June 11-14, 2018, Budapest, Hungary, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 22:1–22:15 (2018) DOI
  5. Jérémie Chalopin, Victor Chepoi, Feodor F. Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, and Yann Vaxès. Fast approximation and exact computation of negative curvature parameters of graphs. CoRR abs/1803.06324 (2018) arXiv
  6. Victor Chepoi, Feodor F. Dragan, Michel Habib, Yann Vaxès, and Hend Al-Rasheed. Fast approximation of centrality and distances in hyperbolic graphs. CoRR abs/1805.07232 (2018) arXiv
  7. Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. Distance and routing labeling schemes for cube-free median graphs. CoRR abs/1809.10508 (2018) arXiv
  8. Jérémie Chalopin and Victor Chepoi. 1-Safe Petri nets and special cube complexes: equivalence and applications. CoRR abs/1810.03395 (2018) arXiv
  9. Jérémie Chalopin, Victor Chepoi, Shay Moran, and Manfred K. Warmuth. Unlabeled sample compression schemes and corner peelings for ample and maximum classes. CoRR abs/1812.02099 (2018) arXiv
  10. Kolja Knauer, Martı́nez-Sandoval Leonardo, and Alfonsı́n Jorge Luis Ramı́rez. A Tutte polynomial inequality for lattice path matroids. Adv. Appl. Math. 94: 23–38 (2018) DOI
  11. Kolja Knauer, Luis Pedro Montejano, and Alfonsı́n Jorge Luis Ramı́rez. How Many Circuits Determine an Oriented Matroid? Comb. 38, 4: 861–885 (2018) DOI
  12. Kolja Knauer, Martı́nez-Sandoval Leonardo, and Alfonsı́n Jorge Luis Ramı́rez. On Lattice Path Matroid Polytopes: Integer Points and Ehrhart Polynomial. Discret. Comput. Geom. 60, 3: 698–719 (2018) DOI
  13. Kolja Knauer, Piotr Micek, and Torsten Ueckerdt. The Queue-Number of Posets of Bounded Width or Height. Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Barcelona, Spain, September 26-28, 2018, Proceedings, Springer, 200–212 (2018) DOI
  14. Guillaume Guégan, Kolja Knauer, Jonathan Rollin, and Torsten Ueckerdt. The interval number of a planar graph is at most three. CoRR abs/1805.02947 (2018) arXiv
  15. Kolja Knauer, Piotr Micek, and Torsten Ueckerdt. The queue-number of planar posets. CoRR abs/1806.04489 (2018) arXiv
  16. Guyslain Naves and F. Bruce Shepherd. When Do Gomory-Hu Subtrees Exist? CoRR abs/1807.07331 (2018) arXiv
  17. Émilie Charlier, Manon Philibert, and Manon Stipulanti. Nyldon words. CoRR abs/1804.09735 (2018) arXiv

2017

  1. Pascal Préa, Mathieu Rouault, and François Brucker. An optimal algorithm to generate extendable self-avoiding walks in arbitrary dimension. Electron. Notes Discret. Math. 59: 37–50 (2017) DOI
  2. Victor Chepoi. Distance-Preserving Subgraphs of Johnson Graphs. Comb. 37, 6: 1039–1055 (2017) DOI
  3. Victor Chepoi, Bertrand Estellon, and Guyslain Naves. Packing and Covering with Balls on Busemann Surfaces. Discret. Comput. Geom. 57, 4: 985–1011 (2017) DOI
  4. Nicolas Catusse, Victor Chepoi, Karim Nouioua, and Yann Vaxès. Bidirected minimum Manhattan network problem. Networks 69, 2: 167–178 (2017) DOI
  5. Jérémie Chalopin and Victor Chepoi. A Counterexample to Thiagarajan’s Conjecture on Regular Event Structures. 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 101:1–101:14 (2017) DOI
  6. Victor Chepoi, Feodor F. Dragan, and Yann Vaxès. Core congestion is inherent in hyperbolic networks. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, SIAM, 2264–2279 (2017) DOI
  7. Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. On density of subgraphs of halved cubes. CoRR abs/1711.11414 (2017) arXiv
  8. Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. On density of subgraphs of Cartesian products. CoRR abs/1711.11485 (2017) arXiv
  9. Basile Couëtoux, Elie Nakache, and Yann Vaxès. The Maximum Labeled Path Problem. Algorithmica 78, 1: 298–318 (2017) DOI
  10. Rémi Desgranges and Kolja Knauer. A correction of a characterization of planar partial cubes. Discret. Math. 340, 6: 1151–1153 (2017) DOI
  11. Kolja Knauer, Petru Valicov, and Paul S. Wenger. Planar Digraphs without Large Acyclic Sets. J. Graph Theory 85, 1: 288–291 (2017) DOI
  12. Kolja Knauer and Tilen Marc. On tope graphs of complexes of oriented matroids. CoRR abs/1701.05525 (2017) arXiv
  13. Garcı́a-Marco Ignacio and Kolja Knauer. Chomp on numerical semigroups. CoRR abs/1705.11034 (2017) arXiv
  14. Kolja Knauer and Torsten Ueckerdt. Decomposing 4-connected planar triangulations into two trees and one path. CoRR abs/1710.02411 (2017) arXiv
  15. Kolja Knauer and Nicolas Nisse. Computing metric hulls in graphs. CoRR abs/1710.02958 (2017) arXiv
  16. Kolja Knauer and Petru Valicov. Cuts in matchings of 3-edge-connected cubic graphs. CoRR abs/1712.06143 (2017) arXiv
  17. Pierre Bonami, Dorian Mazauric, and Yann Vaxès. Maximum flow under proportional delay constraint. Theor. Comput. Sci. 689: 58–66 (2017) DOI

2016

  1. François Brucker and Pascal Préa. Approximate Seriation Problem in Formal Context Analysis. Proceedings of the Thirteenth International Conference on Concept Lattices and Their Applications, Moscow, Russia, July 18-22, 2016, CEUR-WS.org, 71–83 (2016)
  2. Victor Chepoi, Feodor F. Dragan, and Yann Vaxès. Core congestion is inherent in hyperbolic networks. CoRR abs/1605.03059 (2016) arXiv
  3. Jérémie Chalopin and Victor Chepoi. A counterexample to Thiagarajan’s conjecture. CoRR abs/1605.08288 (2016) arXiv
  4. Victor Chepoi, Kolja Knauer, and Tilen Marc. Partial cubes without \textdollarQ_3\^-\textdollar minors. CoRR abs/1606.02154 (2016) arXiv
  5. Ian Gambini and Laurent Vuillon. Tiling the Space by Polycube Analogues of Fedorov’s Polyhedra. Fundam. Informaticae 146, 2: 197–209 (2016) DOI
  6. Garcı́a-Marco Ignacio and Kolja Knauer. Drawing graphs with vertices and edges in convex position. Comput. Geom. 58: 25–33 (2016) DOI
  7. Stefan Felsner, Kolja B. Knauer, George B. Mertzios, and Torsten Ueckerdt. Intersection graphs of L-shapes and segments in the plane. Discret. Appl. Math. 206: 48–55 (2016) DOI
  8. Kolja B. Knauer and Torsten Ueckerdt. Three ways to cover a graph. Discret. Math. 339, 2: 745–758 (2016) DOI
  9. Marie Albenque and Kolja Knauer. Convexity in partial cubes: The hull number. Discret. Math. 339, 2: 866–876 (2016) DOI
  10. Boris Albar, Daniel Gonçalves, and Kolja Knauer. Orienting Triangulations. J. Graph Theory 83, 4: 392–405 (2016) DOI
  11. Bartlomiej Bosek, Stefan Felsner, Kolja Knauer, and Grzegorz Matecki. On the Duality of Semiantichains and Unichain Coverings. Order 33, 1: 29–38 (2016) DOI
  12. Kolja Knauer and Bartosz Walczak. Graph Drawings with One Bend and Few Slopes. LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings, Springer, 549–561 (2016) DOI
  13. Rémi Desgranges and Kolja Knauer. A correction of a characterization of planar partial cubes. CoRR abs/1610.05466 (2016) arXiv
  14. Julian Anaya, Jérémie Chalopin, Jurek Czyzowicz, Arnaud Labourel, Andrzej Pelc, and Yann Vaxès. Convergecast and Broadcast by Power-Aware Mobile Agents. Algorithmica 74, 1: 117–155 (2016) DOI

2015

  1. François Brucker and Pascal Préa. Totally Balanced Formal Context Representation. Formal Concept Analysis - 13th International Conference, ICFCA 2015, Nerja, Spain, June 23-26, 2015, Proceedings, Springer, 169–182 (2015) DOI
  2. Jérémie Chalopin, Victor Chepoi, and Guyslain Naves. Isometric Embedding of Busemann Surfaces into $L_1$ Discret. Comput. Geom. 53, 1: 16–37 (2015) DOI
  3. Hans-Jürgen Bandelt, Victor Chepoi, and David Eppstein. Ramified Rectilinear Polygons: Coordinatization by Dendrons. Discret. Comput. Geom. 54, 4: 771–797 (2015) DOI
  4. Jérémie Chalopin, Victor Chepoi, and Damian Osajda. On two conjectures of Maurer concerning basis graphs of matroids. J. Comb. Theory, Ser. B 114: 1–32 (2015) DOI
  5. Hans-Jürgen Bandelt, Victor Chepoi, and Kolja Knauer. COMs: Complexes of Oriented Matroids. CoRR abs/1507.06111 (2015) arXiv
  6. Victor Chepoi, Bertrand Estellon, and Guyslain Naves. Packing and covering with balls on Busemann surfaces. CoRR abs/1508.00778 (2015) arXiv
  7. Basile Couëtoux, James M. Davis, and David P. Williamson. A 3/2-approximation algorithm for some minimum-cost graph problems. Math. Program. 150, 1: 19–34 (2015) DOI
  8. Leonhard Lücken, Jan Philipp Pade, and Kolja Knauer. Classification of Coupled Dynamical Systems with Multiple Delays: Finding the Minimal Number of Delays. SIAM J. Appl. Dyn. Syst. 14, 1: 286–304 (2015) DOI
  9. Garcı́a-Marco Ignacio and Kolja Knauer. Drawing Graphs with Vertices and Edges in Convex Position. Graph Drawing and Network Visualization - 23rd International Symposium, GD 2015, Los Angeles, CA, USA, September 24-26, 2015, Revised Selected Papers, Springer, 348–359 (2015) DOI
  10. Daniel Gonçalves, Kolja B. Knauer, and Benjamin Lévêque. Structure of Schnyder labelings on orientable surfaces. CoRR abs/1501.05475 (2015) arXiv
  11. Kolja Knauer and Petru Valicov. Planar digraphs without large acyclic sets. CoRR abs/1504.06726 (2015) arXiv
  12. Kolja B. Knauer and Bartosz Walczak. Graph drawings with one bend and few slopes. CoRR abs/1506.04423 (2015) arXiv
  13. Garcı́a-Marco Ignacio and Kolja Knauer. Drawing graphs with vertices and edges in convex position. CoRR abs/1509.01981 (2015) arXiv
  14. Kolja Knauer, Martı́nez-Sandoval Leonardo, and Alfonsı́n Jorge Luis Ramı́rez. A Tutte polynomial inequality for lattice path matroids. CoRR abs/1510.00600 (2015) arXiv
  15. Jérémie Chalopin, Victor Chepoi, and Guyslain Naves. Isometric Embedding of Busemann Surfaces into L\(_\mbox1\). Discret. Comput. Geom. 53, 1: 16–37 (2015) DOI

2014

  1. Jérémie Chalopin, Victor Chepoi, Panos Papasoglu, and Timothée Pecatte. Cop and Robber Game and Hyperbolicity. SIAM J. Discret. Math. 28, 4: 1987–2007 (2014) DOI
  2. Basile Couëtoux, Elie Nakache, and Yann Vaxès. The Maximum Labeled Path Problem. Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers, Springer, 152–163 (2014) DOI
  3. Kolja B. Knauer, Piotr Micek, and Bartosz Walczak. Outerplanar graph drawings with few slopes. Comput. Geom. 47, 5: 614–624 (2014) DOI
  4. Daniel Heldt, Kolja B. Knauer, and Torsten Ueckerdt. Edge-intersection graphs of grid paths: The bend-number. Discret. Appl. Math. 167: 144–162 (2014) DOI
  5. Daniel Heldt, Kolja B. Knauer, and Torsten Ueckerdt. On the bend-number of planar and outerplanar graphs. Discret. Appl. Math. 179: 109–119 (2014) DOI
  6. Kolja B. Knauer, Juan José Montellano-Ballesteros, and Ricardo Strausz. A graph-theoretical axiomatization of oriented matroids. Eur. J. Comb. 35: 388–391 (2014) DOI
  7. Jean Cardinal, Kolja B. Knauer, Piotr Micek, and Torsten Ueckerdt. Making Octants Colorful and Related Covering Decomposition Problems. SIAM J. Discret. Math. 28, 4: 1948–1959 (2014) DOI
  8. Marie Albenque and Kolja B. Knauer. Convexity in Partial Cubes: The Hull Number. LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31 - April 4, 2014. Proceedings, Springer, 421–432 (2014) DOI
  9. Stefan Felsner, Kolja B. Knauer, George B. Mertzios, and Torsten Ueckerdt. Intersection Graphs of L-Shapes and Segments in the Plane. Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II, Springer, 299–310 (2014) DOI
  10. Jean Cardinal, Kolja B. Knauer, Piotr Micek, and Torsten Ueckerdt. Making Octants Colorful and Related Covering Decomposition Problems. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, SIAM, 1424–1432 (2014) DOI
  11. Bartlomiej Bosek, Stefan Felsner, Kolja B. Knauer, and Grzegorz Matecki. On the Duality of Semiantichains and Unichain Coverings. CoRR abs/1401.1225 (2014) arXiv
  12. Joseph Cheriyan, Bundit Laekhanukit, Guyslain Naves, and Adrian Vetta. Approximating Rooted Steiner Networks. ACM Trans. Algorithms 11, 2: 8:1–8:22 (2014) DOI
  13. Guyslain Naves and Arnaud Spiwack. Balancing Lists: A Proof Pearl. Interactive Theorem Proving - 5th International Conference, ITP 2014, Held as Part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 14-17, 2014. Proceedings, Springer, 437–449 (2014) DOI
  14. Guyslain Naves and Arnaud Spiwack. Balancing lists: a proof pearl. CoRR abs/1401.7886 (2014) arXiv
  15. Pascal Préa and Monique Rolbert. Distinguishing and Classifying from n-ary Properties. J. Classif. 31, 1: 28–48 (2014) DOI
  16. Pascal Préa and Dominique Fortin. An Optimal Algorithm To Recognize Robinsonian Dissimilarities. J. Classif. 31, 3: 351–385 (2014) DOI

2013

  1. Victor Chepoi and Daniela Maftuleac. Shortest path problem in rectangular complexes of global nonpositive curvature. Comput. Geom. 46, 1: 51–64 (2013) DOI
  2. Victor Chepoi and Stefan Felsner. Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve. Comput. Geom. 46, 9: 1036–1041 (2013) DOI
  3. Victor Chepoi and Mark F. Hagen. On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes. J. Comb. Theory, Ser. B 103, 4: 428–467 (2013) DOI
  4. Bostjan Bresar, Jérémie Chalopin, Victor Chepoi, Matjaz Kovse, Arnaud Labourel, and Yann Vaxès. Retracts of Products of Chordal Graphs. J. Graph Theory 73, 2: 161–180 (2013) DOI
  5. Jérémie Chalopin, Victor Chepoi, and Guyslain Naves. Isometric embedding of Busemann surfaces into $L_1$ CoRR abs/1308.3181 (2013) arXiv
  6. Jérémie Chalopin, Victor Chepoi, Panos Papasoglu, and Timothée Pecatte. Cop and robber game and hyperbolicity. CoRR abs/1308.3987 (2013) arXiv
  7. Bertrand Estellon and Frédéric Gardi. Car sequencing is NP-hard: a short proof. J. Oper. Res. Soc. 64, 10: 1503–1504 (2013) DOI
  8. Chandra Chekuri, Guyslain Naves, and F. Bruce Shepherd. Maximum Edge-Disjoint Paths in k-Sums of Graphs. Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, Springer, 328–339 (2013) DOI
  9. Chandra Chekuri, Guyslain Naves, and F. Bruce Shepherd. Maximum Edge-Disjoint Paths in \textdollark\textdollar-sums of Graphs. CoRR abs/1303.4897 (2013) arXiv
  10. Jérémie Chalopin, Victor Chepoi, and Guyslain Naves. Isometric embedding of Busemann surfaces into L\(_\mbox1\). CoRR abs/1308.3181 (2013) arXiv
  11. Fabien Rebatel and Edouard Thiel. On Dimension Partitions in Discrete Metric Spaces. Discrete Geometry for Computer Imagery - 17th IAPR International Conference, DGCI 2013, Seville, Spain, March 20-22, 2013. Proceedings, Springer, 11–22 (2013) DOI

2012

  1. Victor Chepoi, Tristan Fevat, Emmanuel Godard, and Yann Vaxès. A Self-stabilizing Algorithm for the Median Problem in Partial Rectangular Grids and Their Relatives. Algorithmica 62, 1-2: 146–168 (2012) DOI
  2. Victor Chepoi, Feodor F. Dragan, Bertrand Estellon, Michel Habib, Yann Vaxès, and Yang Xiang. Additive Spanners and Distance and Routing Labeling Schemes for Hyperbolic Graphs. Algorithmica 62, 3-4: 713–732 (2012) DOI
  3. Nicolas Catusse, Victor Chepoi, Karim Nouioua, and Yann Vaxès. Minimum Manhattan Network Problem in Normed Planes with Polygonal Balls: A Factor 2.5 Approximation Algorithm. Algorithmica 63, 1-2: 551–567 (2012) DOI
  4. Victor Chepoi, Feodor F. Dragan, Ilan Newman, Yuri Rabinovich, and Yann Vaxès. Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs. Discret. Comput. Geom. 47, 1: 187–214 (2012) DOI
  5. Victor Chepoi. Nice Labeling Problem for Event Structures: A Counterexample. SIAM J. Comput. 41, 4: 715–727 (2012) DOI
  6. Jérémie Chalopin, Victor Chepoi, and Damian Osajda. Proof of two Maurer’s conjectures on basis graphs of matroids. CoRR abs/1212.6879 (2012) arXiv
  7. Basile Couëtoux, Jérôme Monnot, and Sonia Toubaline. Complexity Results for the Empire Problem in Collection of Stars. Combinatorial Optimization and Applications - 6th International Conference, COCOA 2012, Banff, AB, Canada, August 5-9, 2012. Proceedings, Springer, 73–82 (2012) DOI
  8. Ian Gambini and Laurent Vuillon. Non-lattice-periodic tilings of R\(^\mbox3\)by single polycubes. Theor. Comput. Sci. 432: 52–57 (2012) DOI
  9. Guyslain Naves. The hardness of routing two pairs on one face. Math. Program. 131, 1-2: 49–69 (2012) DOI
  10. Joseph Cheriyan, Bundit Laekhanukit, Guyslain Naves, and Adrian Vetta. Approximating rooted Steiner networks. Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, SIAM, 1499–1511 (2012) DOI
  11. Bundit Laekhanukit, Guyslain Naves, and Adrian Vetta. Non-redistributive Second Welfare Theorems. Internet and Network Economics - 8th International Workshop, WINE 2012, Liverpool, UK, December 10-12, 2012. Proceedings, Springer, 227–243 (2012) DOI
  12. Julian Anaya, Jérémie Chalopin, Jurek Czyzowicz, Arnaud Labourel, Andrzej Pelc, and Yann Vaxès. Collecting Information by Power-Aware Mobile Agents. Distributed Computing - 26th International Symposium, DISC 2012, Salvador, Brazil, October 16-18, 2012. Proceedings, Springer, 46–60 (2012) DOI

2011

  1. François Brucker and Alain Gély. Crown-free Lattices and Their Related Graphs. Order 28, 3: 443–454 (2011) DOI
  2. Victor Chepoi and Morgan Seston. Seriation in the Presence of Errors: A Factor 16 Approximation Algorithm for $\ell_∞$-Fitting Robinson Structures to Distances. Algorithmica 59, 4: 521–568 (2011) DOI
  3. Jérémie Chalopin, Victor Chepoi, Nicolas Nisse, and Yann Vaxès. Cop and Robber Games When the Robber Can Hide and Ride. SIAM J. Discret. Math. 25, 1: 333–359 (2011) DOI
  4. Nicolas Catusse, Victor Chepoi, and Yann Vaxès. Embedding into the rectilinear plane in optimal O(n^2) time. Theor. Comput. Sci. 412, 22: 2425–2433 (2011) DOI
  5. Nicolas Catusse, Victor Chepoi, Karim Nouioua, and Yann Vaxès. Bidirected minimum Manhattan network problem. CoRR abs/1107.1359 (2011) arXiv
  6. Cristina Bazgan, Basile Couëtoux, and Zsolt Tuza. Complexity and approximation of the Constrained Forest problem. Theor. Comput. Sci. 412, 32: 4081–4091 (2011) DOI
  7. Basile Couëtoux. A \textdollar}frac{3}{2}\textdollar Approximation for a Constrained Forest Problem. Algorithms - ESA 2011 - 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings, Springer, 652–663 (2011) DOI
  8. Thierry Benoist, Bertrand Estellon, Frédéric Gardi, Romain Megel, and Karim Nouioua. LocalSolver 1.x: a black-box local-search solver for 0-1 programming. 4OR 9, 3: 299–316 (2011) DOI
  9. Thierry Benoist, Frédéric Gardi, Antoine Jeanjean, and Bertrand Estellon. Randomized Local Search for Real-Life Inventory Routing. Transp. Sci. 45, 3: 381–398 (2011) DOI
  10. Ian Gambini and Laurent Vuillon. How many Faces can the Polycubes of Lattice Tilings by Translation of R\(^\mbox3\) have? Electron. J. Comb. 18, 1 (2011) DOI
  11. Guyslain Naves and Vincent Jost. The graphs with the max-Mader-flow-min-multiway-cut property. CoRR abs/1101.2061 (2011) arXiv
  12. Frédéric Gardi and Karim Nouioua. Local Search for Mixed-Integer Nonlinear Optimization: A Methodology and an Application. Evolutionary Computation in Combinatorial Optimization - 11th European Conference, EvoCOP 2011, Torino, Italy, April 27-29, 2011. Proceedings, Springer, 167–178 (2011) DOI
  13. Fabien Rebatel and Edouard Thiel. Metric Bases for Polyhedral Gauges. Discrete Geometry for Computer Imagery - 16th IAPR International Conference, DGCI 2011, Nancy, France, April 6-8, 2011. Proceedings, Springer, 116–128 (2011) DOI

2010

  1. Victor Chepoi, Nadia Creignou, Miki Hermann, and Gernot Salzer. The Helly property and satisfiability of Boolean formulas defined on set families. Eur. J. Comb. 31, 2: 502–516 (2010) DOI
  2. Victor Chepoi, Karim Nouioua, Edouard Thiel, and Yann Vaxès. Pareto Envelopes in Simple Polygons. Int. J. Comput. Geom. Appl. 20, 6: 707–721 (2010) DOI
  3. Hans-Jürgen Bandelt, Victor Chepoi, and David Eppstein. Combinatorics and Geometry of Finite and Infinite Squaregraphs. SIAM J. Discret. Math. 24, 4: 1399–1440 (2010) DOI
  4. Nicolas Catusse, Victor Chepoi, and Yann Vaxès. Planar Hop Spanners for Unit Disk Graphs. Algorithms for Sensor Systems - 6th International Workshop on Algorithms for Sensor Systems, Wireless Ad Hoc Networks, and Autonomous Mobile Entities, ALGOSENSORS 2010, Bordeaux, France, July 5, 2010, Revised Selected Papers, Springer, 16–30 (2010) DOI
  5. Victor Chepoi, Feodor F. Dragan, Ilan Newman, Yuri Rabinovich, and Yann Vaxès. Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, Springer, 95–109 (2010) DOI
  6. Jérémie Chalopin, Victor Chepoi, Nicolas Nisse, and Yann Vaxès. Cop and robber games when the robber can hide and ride. CoRR abs/1001.4457 (2010) arXiv
  7. Nicolas Catusse, Victor Chepoi, Karim Nouioua, and Yann Vaxès. Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm. CoRR abs/1004.5517 (2010) arXiv
  8. Victor Chepoi, Feodor F. Dragan, Ilan Newman, Yuri Rabinovich, and Yann Vaxès. Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs. CoRR abs/1007.0489 (2010) arXiv
  9. Victor Chepoi and Daniela Maftuleac. Shortest path problem in rectangular complexes of global nonpositive curvature. CoRR abs/1010.0852 (2010) arXiv
  10. Basile Couëtoux, Laurent Gourvès, Jérôme Monnot, and Orestis Telelis. Labeled Traveling Salesman Problems: Complexity and approximation. Discret. Optim. 7, 1-2: 74–85 (2010) DOI
  11. Guyslain Naves. Routages optimaux : tours, flots et chemins. (Optimal Routings: Tours, Flows and Paths). Retrieved from https://tel.archives-ouvertes.fr/tel-00465585 (2010)
  12. Guyslain Naves, Nicolas Sonnerat, and Adrian Vetta. Maximum Flows on Disjoint Paths. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, Springer, 326–337 (2010) DOI
  13. Guyslain Naves. On disjoint paths in acyclic planar graphs. CoRR abs/1008.3652 (2010) arXiv
  14. Guyslain Naves and Christophe Weibel. Congestion in planar graphs with demands on faces. CoRR abs/1008.3653 (2010) arXiv

2009

  1. François Brucker and Alain Gély. Parsimonious cluster systems. Adv. Data Anal. Classif. 3, 3: 189–204 (2009) DOI
  2. Victor Chepoi, Bernard Fichet, and Morgan Seston. Seriation in the Presence of Errors: NP-Hardness of $\ell_∞$-Fitting Robinson Structures to Dissimilarity Matrices. J. Classif. 26, 3: 279–296 (2009) DOI
  3. Victor Chepoi and Morgan Seston. An Approximation Algorithm for $\ell_∞$ Fitting Robinson Structures to Distances. 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26-28, 2009, Freiburg, Germany, Proceedings, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany, 265–276 (2009) DOI
  4. Victor Chepoi and Morgan Seston. An Approximation Algorithm for l}infty-Fitting Robinson Structures to Distances. CoRR abs/0902.1261 (2009) arXiv
  5. Nicolas Catusse, Victor Chepoi, and Yann Vaxès. Embedding into the rectilinear plane in optimal O*(n\^2). CoRR abs/0910.1059 (2009) arXiv
  6. Cristina Bazgan, Basile Couëtoux, and Zsolt Tuza. Covering a Graph with a Constrained Forest (Extended Abstract). Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings, Springer, 892–901 (2009) DOI
  7. Bertrand Estellon, Frédéric Gardi, and Karim Nouioua. High-Performance Local Search for Task Scheduling with Human Resource Allocation. Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics, Second International Workshop, SLS 2009, Brussels, Belgium, September 3-4, 2009. Proceedings, Springer, 1–15 (2009) DOI
  8. Thierry Benoist, Bertrand Estellon, Frédéric Gardi, and Antoine Jeanjean. High-Performance Local Search for Solving Real-Life Inventory Routing Problems. Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics, Second International Workshop, SLS 2009, Brussels, Belgium, September 3-4, 2009. Proceedings, Springer, 105–109 (2009) DOI
  9. Guyslain Naves. The hardness of routing two pairs on one face. CoRR abs/0911.3024 (2009) arXiv
  10. Monique Rolbert and Pascal Préa. Distinguishable Entities: Definitions and Properties. ENLG 2009 - Proceedings of the 12th European Workshop on Natural Language Generation, March 30-31, 2009, Athens, Greece, The Association for Computer Linguistics, 34–41 (2009)
  11. Jérôme Hulin and Edouard Thiel. Visible Vectors and Discrete Euclidean Medial Axis. Discret. Comput. Geom. 42, 4: 759–773 (2009) DOI
  12. Jérôme Hulin and Edouard Thiel. Appearance Radii in Medial Axis Test Mask for Small Planar Chamfer Norms. Discrete Geometry for Computer Imagery, 15th IAPR International Conference, DGCI 2009, Montréal, Canada, September 30 - October 2, 2009. Proceedings, Springer, 434–445 (2009) DOI
  13. Jérôme Hulin and Edouard Thiel. Farey Sequences and the Planar Euclidean Medial Axis Test Mask. Combinatorial Image Analysis, 13th International Workshop, IWCIA 2009, Playa del Carmen, Mexico, November 24-27, 2009. Proceedings, Springer, 82–95 (2009) DOI

2008

  1. Jean-Pierre Barthélemy and François Brucker. Binary clustering. Discret. Appl. Math. 156, 8: 1237–1250 (2008) DOI
  2. Hans-Jürgen Bandelt and Victor Chepoi. The algebra of metric betweenness II: Geometry and equational characterization of weakly median graphs. Eur. J. Comb. 29, 3: 676–700 (2008) DOI
  3. Victor Chepoi, Feodor F. Dragan, Bertrand Estellon, Michel Habib, and Yann Vaxès. Notes on diameters, centers, and approximating trees of delta-hyperbolic geodesic spaces and graphs. Electron. Notes Discret. Math. 31: 231–234 (2008) DOI
  4. Victor Chepoi, Karim Nouioua, and Yann Vaxès. A rounding algorithm for approximating minimum Manhattan networks. Theor. Comput. Sci. 390, 1: 56–69 (2008) DOI
  5. Victor Chepoi, Bertrand Estellon, and Yann Vaxès. Approximation algorithms for forests augmentation ensuring two disjoint paths of bounded length. Theor. Comput. Sci. 401, 1-3: 131–143 (2008) DOI
  6. Victor Chepoi, Feodor F. Dragan, Bertrand Estellon, Michel Habib, and Yann Vaxès. Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs. Proceedings of the 24th ACM Symposium on Computational Geometry, College Park, MD, USA, June 9-11, 2008, ACM, 59–68 (2008) DOI
  7. Victor Chepoi, Nadia Creignou, Miki Hermann, and Gernot Salzer. Deciding the Satisfiability of Propositional Formulas in Finitely-Valued Signed Logics. 38th IEEE International Symposium on Multiple-Valued Logic (ISMVL 2008), 22-23 May 2008, Dallas, Texas, USA, IEEE Computer Society, 100–105 (2008) DOI
  8. Basile Couëtoux, Laurent Gourvès, Jérôme Monnot, and Orestis Telelis. On Labeled Traveling Salesman Problems. Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008. Proceedings, Springer, 776–787 (2008) DOI
  9. Bertrand Estellon, Frédéric Gardi, and Karim Nouioua. Two local search approaches for solving real-life car sequencing problems. Eur. J. Oper. Res. 191, 3: 928–944 (2008) DOI
  10. Guyslain Naves and András Sebö. Multiflow Feasibility: An Annotated Tableau. Research Trends in Combinatorial Optimization, Bonn Workshop on Combinatorial Optimization, November 3-7, 2008, Bonn, Germany, Springer, 261–283 (2008) DOI

2007

  1. Jean-Pierre Barthélemy, François Brucker, and Christophe Osswald. Combinatorial optimisation and hierarchical classifications. Ann. Oper. Res. 153, 1: 179–214 (2007) DOI
  2. Victor Chepoi, Bertrand Estellon, and Yann Vaxès. Covering Planar Graphs with a Fixed Number of Balls. Discret. Comput. Geom. 37, 2: 237–244 (2007) DOI
  3. Hans-Jürgen Bandelt and Victor Chepoi. The algebra of metric betweenness I: Subdirect representation and retraction. Eur. J. Comb. 28, 6: 1640–1661 (2007) DOI
  4. Victor Chepoi. Basis graphs of even Delta-matroids. J. Comb. Theory, Ser. B 97, 2: 175–192 (2007) DOI
  5. Victor Chepoi and Bertrand Estellon. Packing and Covering delta -Hyperbolic Spaces by Balls. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, USA, August 20-22, 2007, Proceedings, Springer, 59–73 (2007) DOI
  6. Victor Chepoi and Karim Nouioua. Pareto envelopes in $ℝ^3$ under $\ell_1$ and $\ell_∞$ distance functions. Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, South Korea, June 6-8, 2007, ACM, 284–293 (2007) DOI
  7. Victor Chepoi, Tristan Fevat, Emmanuel Godard, and Yann Vaxès. A Self-stabilizing Algorithm for the Median Problem in Partial Rectangular Grids and Their Relatives. Structural Information and Communication Complexity, 14th International Colloquium, SIROCCO 2007, Castiglioncello, Italy, June 5-8, 2007, Proceedings, Springer, 81–95 (2007) DOI
  8. Ian Gambini and Laurent Vuillon. An algorithm for deciding if a polyomino tiles the plane. RAIRO Theor. Informatics Appl. 41, 2: 147–155 (2007) DOI

2006

  1. François Brucker. Sub-dominant theory in numerical taxonomy. Discret. Appl. Math. 154, 7: 1085–1099 (2006) DOI
  2. Victor Chepoi, Bertrand Estellon, Karim Nouioua, and Yann Vaxès. Mixed Covering of Trees and the Augmentation Problem with Odd Diameter Constraints. Algorithmica 45, 2: 209–226 (2006) DOI
  3. Hans-Jürgen Bandelt, Victor Chepoi, Andreas W. M. Dress, and Jack H. Koolen. Combinatorics of lopsided sets. Eur. J. Comb. 27, 5: 669–689 (2006) DOI
  4. Victor Chepoi, Feodor F. Dragan, and Yann Vaxès. Distance and routing labeling schemes for non-positively curved plane graphs. J. Algorithms 61, 2: 60–88 (2006) DOI
  5. Victor Chepoi, Feodor F. Dragan, and Yann Vaxès. Addressing, distances and routing in triangular systems with applications in cellular networks. Wirel. Networks 12, 6: 671–679 (2006) DOI
  6. Bertrand Estellon, Frédéric Gardi, and Karim Nouioua. Large neighborhood improvements for solving car sequencing problems. RAIRO Oper. Res. 40, 4: 355–379 (2006) DOI
  7. Jérôme Hulin and Edouard Thiel. Chordal Axis on Weighted Distance Transforms. Discrete Geometry for Computer Imagery, 13th International Conference, DGCI 2006, Szeged, Hungary, October 25-27, 2006, Proceedings, Springer, 271–282 (2006) DOI

2005

  1. François Brucker. From hypertrees to arboreal quasi-ultrametrics. Discret. Appl. Math. 147, 1: 3–26 (2005) DOI
  2. Victor Chepoi, Bertrand Estellon, Karim Nouioua, and Yann Vaxès. Mixed covering of trees and the augmentation problem with odd diameter constraints. Electron. Notes Discret. Math. 22: 405–408 (2005) DOI
  3. Victor Chepoi, Feodor F. Dragan, and Chenyu Yan. Additive sparse spanners for graphs with bounded length of largest induced cycle. Theor. Comput. Sci. 347, 1-2: 54–75 (2005) DOI
  4. Victor Chepoi, Karim Nouioua, and Yann Vaxès. A Rounding Algorithm for Approximating Minimum Manhattan Networks. Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th InternationalWorkshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings, Springer, 40–51 (2005) DOI
  5. Victor Chepoi, Feodor F. Dragan, and Yann Vaxès. Distance-Based Location Update and Routing in Irregular Cellular Networks. Proceedings of the 6th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD 2005), May 23-25, 2005, Towson, Maryland, USA, IEEE Computer Society, 380–387 (2005) DOI
  6. Victor Chepoi, Bertrand Estellon, and Yann Vaxès. Approximation Algorithms for Forests Augmentation Ensuring Two Disjoint Paths of Bounded Length. Algorithms and Data Structures, 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005, Proceedings, Springer, 282–293 (2005) DOI
  7. Eric Remy and Edouard Thiel. Exact medial axis with euclidean distance. Image Vis. Comput. 23, 2: 167–175 (2005) DOI
  8. Toshihide Ibaraki, Yann Vaxès, and Xiao Guang Yang. Lowering eccentricity of a tree by node upgrading. Networks 45, 4: 232–239 (2005) DOI

2004

  1. Régis Barbanchon. On unique graph 3-colorability and parsimonious reductions in the plane. Theor. Comput. Sci. 319, 1-3: 455–482 (2004) DOI
  2. Régis Barbanchon and Etienne Grandjean. The Minimal Logically-Defined NP-Complete Problem. STACS 2004, 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004, Proceedings, Springer, 338–349 (2004) DOI
  3. Jean-Pierre Barthélemy, François Brucker, and Christophe Osswald. Combinatorial optimization and hierarchical classifications. 4OR 2, 3: 179–219 (2004) DOI
  4. Victor Chepoi, Clémentine Fanciullini, and Yann Vaxès. Median problem in some plane triangulations and quadrangulations. Comput. Geom. 27, 3: 193–210 (2004) DOI
  5. Victor Chepoi, Feodor F. Dragan, and Yann Vaxès. Addressing, Distances and Routing in Triangular Systems with Applications in Cellular and Sensor Networks. 18th International Parallel and Distributed Processing Symposium (IPDPS 2004), CD-ROM / Abstracts Proceedings, 26-30 April 2004, Santa Fe, New Mexico, USA, IEEE Computer Society (2004) DOI

2003

  1. Victor Chepoi and Feodor F. Dragan. Finding a central vertex in an HHD-free graph. Discret. Appl. Math. 131, 1: 93–11 (2003) DOI
  2. Victor Chepoi and Yann Vaxès. On covering bridged plane triangulations with balls. J. Graph Theory 44, 1: 65–80 (2003) DOI
  3. Victor Chepoi, Hartmut Noltemeier, and Yann Vaxès. Upgrading trees under diameter and budget constraints. Networks 41, 1: 24–35 (2003) DOI
  4. Hans-Jürgen Bandelt and Victor Chepoi. 1-Hyperbolic Graphs. SIAM J. Discret. Math. 16, 2: 323–334 (2003) DOI
  5. Victor Chepoi and Alexis Rollin. Interval routing in some planar networks. Theor. Comput. Sci. 290, 3: 1503–1540 (2003) DOI
  6. Victor Chepoi, Feodor F. Dragan, and Chenyu Yan. Additive Spanners for k-Chordal Graphs. Algorithms and Complexity, 5th Italian Conference, CIAC 2003, Rome, Italy, May 28-30, 2003, Proceedings, Springer, 96–107 (2003) DOI
  7. Eric Remy and Edouard Thiel. Look-Up Tables for Medial Axis on Squared Euclidean Distance Transform. Discrete Geometry for Computer Imagery, 11th International Conference, DGCI 2003, Naples, Italy, November 19-21, 2003, Proceedings, Springer, 224–235 (2003) DOI

2002

  1. Régis Barbanchon and Etienne Grandjean. Local Problems, Planar Local Problems and Linear Time. Computer Science Logic, 16th International Workshop, CSL 2002, 11th Annual Conference of the EACSL, Edinburgh, Scotland, UK, September 22-25, 2002, Proceedings, Springer, 397–411 (2002) DOI
  2. Victor Chepoi and Yann Vaxès. Augmenting Trees to Meet Biconnectivity and Diameter Constraints. Algorithmica 33, 2: 243–262 (2002) DOI
  3. Hans-Jürgen Bandelt and Victor Chepoi. Graphs with Connected Medians. SIAM J. Discret. Math. 15, 2: 268–282 (2002) DOI
  4. Victor Chepoi, Feodor F. Dragan, and Yann Vaxès. Center and diameter problems in plane triangulations and quadrangulations. Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA, ACM/SIAM, 346–355 (2002)
  5. Eric Remy and Edouard Thiel. Medial axis for chamfer distances: computing look-up tables and neighbourhoods in 2D or 3D. Pattern Recognit. Lett. 23, 6: 649–661 (2002) DOI