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. Mickael Carmona. Identification passive des milieux de propagation élastiques. Application à la reconstruction géométrique des réseaux de capteurs et au diagnostic des structures. Aix-Marseille University, France (2024)
  2. Mikhael Carmona, Victor Chepoi, Guyslain Naves, and Pascal Préa. Two Simple but Efficient Algorithms to Recognize Robinson Dissimilarities. J. Classif. 41, 3: 455–479 (2024) DOI
  3. Mikhael Carmona, Victor Chepoi, Guyslain Naves, and Pascal Préa. Modules in Robinson Spaces. SIAM J. Discret. Math. 38, 1: 190–224 (2024) DOI
  4. Oscar Defrain, Antonio E. Porreca, and Ekaterina Timofeeva. Polynomial-delay generation of functional digraphs up to isomorphism. Discret. Appl. Math. 357: 24–33 (2024) DOI
  5. 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
  6. Oscar Defrain and Jean-Florent Raymond. Sparse graphs without long induced paths. J. Comb. Theory B 166: 30–49 (2024) DOI
  7. 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 G2-connected medians. Discret. Appl. Math. 359: 55–74 (2024) DOI
  8. Victor Chepoi, Kolja Knauer, and Manon Philibert. Labeled sample compression schemes for complexes of oriented matroids. J. Comput. Syst. Sci. 144: 103543 (2024) DOI
  9. Jérémie Chalopin and Victor Chepoi. Boundary rigidity of CAT(0) cube complexes. J. Comb. Theory B 169: 352–366 (2024) DOI
  10. Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi, and Yann Vaxès. Graphs with G^p-connected medians. Math. Program. 203, 1: 369–420 (2024) DOI
  11. Jérémie Chalopin, Manoj Changat, Victor Chepoi, and Jeny Jacob. First-order logic axiomatization of metric graph theory. Theor. Comput. Sci. 993: 114460 (2024) DOI
  12. Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. Economical Convex Coverings and Applications. SIAM J. Comput. 53, 4: 1002–1038 (2024) DOI
  13. Refka Ben Hamouda, Bertrand Estellon, Khalil Himet, Aimen Cherif, Hugo Marthinet, Jean-Marie Loreau, Gaëtan Texier, Samuel Granjeaud, and Lionel Almeras. MSProfileR: An Open-Source Software for Quality Control of Matrix-Assisted Laser Desorption Ionization-Time of Flight Spectra. Informatics 11, 2: 39 (2024) DOI
  14. Valentin Bartier, Oscar Defrain, and Fionn Mc Inerney. Hypergraph Dualization with FPT-delay Parameterized by the Degeneracy and Dimension. Combinatorial Algorithms - 35th International Workshop, IWOCA 2024, Ischia, Italy, July 1-3, 2024, Proceedings, Springer, 111–125 (2024) DOI
  15. Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, and Jean-Florent Raymond. Local Certification of Geometric Graph Classes. 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, August 26-30, 2024, Bratislava, Slovakia, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 48:1–48:14 (2024) DOI
  16. Benjamin Bergougnoux, Oscar Defrain, and Fionn Mc Inerney. Enumerating Minimal Solution Sets for Metric Graph Problems. Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Gozd Martuljek, Slovenia, June 19-21, 2024, Revised Selected Papers, Springer, 50–64 (2024) DOI
  17. Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, and Sébastien Ratel. Non-Clashing Teaching Maps for Balls in Graphs. The Thirty Seventh Annual Conference on Learning Theory, June 30 - July 3, 2023, Edmonton, Canada, PMLR, 840–875 (2024)
  18. Basile Couëtoux, Bastien Gastaldi, and Guyslain Naves. The Steady-States of Splitter Networks. 12th International Conference on Fun with Algorithms, FUN 2024, June 4-8, 2024, Island of La Maddalena, Sardinia, Italy, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 9:1–9:14 (2024) DOI
  19. Guilherme Dias da Fonseca and Yan Gerard. Shadoks Approach to Knapsack Polygonal Packing (CG Challenge). 40th International Symposium on Computational Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 84:1–84:9 (2024) DOI
  20. Guilherme Dias da Fonseca, Yan Gerard, and Bastien Rivier. Short Flip Sequences to Untangle Segments in the Plane. WALCOM: Algorithms and Computation - 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024, Kanazawa, Japan, March 18-20, 2024, Proceedings, Springer, 163–178 (2024) DOI
  21. François Brucker, Pascal Préa, and Christopher Thraves Caro. Extending Robinson Spaces: Complexity and Algorithmic Solutions for Non-Symmetric Dissimilarity Spaces. CoRR abs/2412.04118 (2024) arXiv
  22. 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
  23. Victor Chepoi. Separation axiom S_3 for geodesic convexity in graphs. CoRR abs/2405.07512 (2024) arXiv
  24. Basile Couëtoux, Bastien Gastaldi, and Guyslain Naves. The steady-states of splitter networks. CoRR abs/2404.05472 (2024) arXiv
  25. Guilherme Dias da Fonseca and Yan Gerard. Shadoks Approach to Knapsack Polygonal Packing. CoRR abs/2403.20123 (2024) arXiv
  26. Dibyayan Chakraborty and Yann Vaxès. Additive approximation algorithm for geodesic centers in \(δ\)-hyperbolic graphs. CoRR abs/2404.03812 (2024) arXiv

2023

  1. François Hamonic. Algorithms for conservation and restauration of landscape connectivty. Aix-Marseille University, France (2023)
  2. Mikhael Carmona, Victor Chepoi, Guyslain Naves, and Pascal Préa. A Simple and Optimal Algorithm for Strict Circular Seriation. SIAM J. Math. Data Sci. 5, 1: 201–221 (2023) DOI
  3. 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. Discret. Math. Theor. Comput. Sci. 25, 2 (2023) DOI
  4. Marthe Bonamy, Oscar Defrain, Tereza Klimosová, Aurélie Lagoutte, and Jonathan Narboni. On Vizing’s edge colouring question. J. Comb. Theory B 159: 126–139 (2023) 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. SIAM J. Discret. Math. 37, 4: 2585–2616 (2023) DOI
  6. 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
  7. Arun Kumar Das, Sandip Das, Guilherme Dias da Fonseca, Yan Gerard, and Bastien Rivier. Complexity results on untangling red-blue matchings. Comput. Geom. 111: 101974 (2023) DOI
  8. Crombez Loı̈c, Guilherme Dias da Fonseca, Florian Fontan, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, Luc Libralesso, Benjamin Momège, Jack Spalding-Jamieson, Brandon Zhang, et al. Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring. ACM J. Exp. Algorithmics 28: 1.2:1–1.2:13 (2023) DOI
  9. Guyslain Naves. Integer Multiflows in Acyclic Planar Digraphs. Comb. 43, 5: 1031–1043 (2023) DOI
  10. Guyslain Naves, F. Bruce Shepherd, and Henry Xia. Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators. Math. Program. 197, 2: 1049–1067 (2023) DOI
  11. Guilherme Dias da Fonseca. Shadoks Approach to Convex Covering (CG Challenge). 39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas, USA, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 67:1–67:9 (2023) DOI
  12. Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. Economical Convex Coverings and Applications. Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, SIAM, 1834–1861 (2023) DOI
  13. Guilherme Dias da Fonseca, Yan Gerard, and Bastien Rivier. On the Longest Flip Sequence to Untangle Segments in the Plane. WALCOM: Algorithms and Computation - 17th International Conference and Workshops, WALCOM 2023, Hsinchu, Taiwan, March 22-24, 2023, Proceedings, Springer, 102–112 (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
  15. Mikhael Carmona, Victor Chepoi, Guyslain Naves, and Pascal Préa. Modules and PQ-trees in Robinson spaces. CoRR abs/2306.08800 (2023) arXiv
  16. Oscar Defrain and Jean-Florent Raymond. Sparse graphs without long induced paths. CoRR abs/2304.09679 (2023) arXiv
  17. 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
  18. 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
  19. Benjamin Bergougnoux, Oscar Defrain, and Fionn Mc Inerney. Enumerating minimal solution sets for metric graph problems. CoRR abs/2309.17419 (2023) arXiv
  20. 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
  21. Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, and Sébastien Ratel. Non-Clashing Teaching Maps for Balls in Graphs. CoRR abs/2309.02876 (2023) arXiv
  22. Jérémie Chalopin and Victor Chepoi. Boundary rigidity of finite CAT(0) cube complexes. CoRR abs/2310.04223 (2023) arXiv
  23. Guilherme Dias da Fonseca. Shadoks Approach to Convex Covering. CoRR abs/2303.07696 (2023) arXiv
  24. Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. Economical Convex Coverings and Applications. CoRR abs/2303.08349 (2023) arXiv
  25. Ahmed Abdelkader, Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. Approximate Nearest Neighbor Searching with Non-Euclidean and Weighted Distances. CoRR abs/2306.15621 (2023) arXiv
  26. Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. Optimal Area-Sensitive Bounds for Polytope Approximation. CoRR abs/2306.15648 (2023) arXiv
  27. Guilherme Dias da Fonseca, Yan Gerard, and Bastien Rivier. Short Flip Sequences to Untangle Segments in the Plane. CoRR abs/2307.00853 (2023) arXiv

2022

  1. Laurine Bénéteau. Medians in graphs : algorithms, connectivity and axiomatic. Aix-Marseille University, France (2022)
  2. Lukasz Bozyk, Oscar Defrain, Karolina Okrasa, and Michal Pilipczuk. On objects dual to tree-cut decompositions. J. Comb. Theory B 157: 401–428 (2022) DOI
  3. Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. Distance labeling schemes for K_4-free bridged graphs. Inf. Comput. 289, Part: 104959 (2022) DOI
  4. 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
  5. 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
  6. 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
  7. Crombez Loı̈c, Guilherme Dias da Fonseca, and Yan Gerard. Greedy and Local Search Heuristics to Build Area-Optimal Polygons. ACM J. Exp. Algorithmics 27: 2.2:1–2.2:11 (2022) DOI
  8. Crombez Loı̈c, Guilherme Dias da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, and Luc Libralesso. Shadoks Approach to Low-Makespan Coordinated Motion Planning. ACM J. Exp. Algorithmics 27: 3.2:1–3.2:17 (2022) DOI
  9. Rahul Arya, Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. Optimal Bound on the Combinatorial Complexity of Approximating Polytopes. ACM Trans. Algorithms 18, 4: 35:1–35:29 (2022) DOI
  10. Guyslain Naves and F. Bruce Shepherd. When Do Gomory-Hu Subtrees Exist? SIAM J. Discret. Math. 36, 3: 1567–1585 (2022) DOI
  11. 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
  12. 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
  13. Crombez Loı̈c, Guilherme Dias da Fonseca, Yan Gerard, and Aldo Gonzalez-Lorenzo. Shadoks Approach to Minimum Partition into Plane Subgraphs (CG Challenge). 38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 71:1–71:8 (2022) DOI
  14. Arun Kumar Das, Sandip Das, Guilherme Dias da Fonseca, Yan Gerard, and Bastien Rivier. Complexity Results on Untangling Red-Blue Matchings. LATIN 2022: Theoretical Informatics - 15th Latin American Symposium, Guanajuato, Mexico, November 7-11, 2022, Proceedings, Springer, 730–745 (2022) DOI
  15. 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
  16. Mikhael Carmona, Victor Chepoi, Guyslain Naves, and Pascal Préa. Modules in Robinson Spaces. CoRR abs/2203.12386 (2022) arXiv
  17. 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
  18. Lukasz Bozyk, Oscar Defrain, Karolina Okrasa, and Michal Pilipczuk. On digraphs without onion star immersions. CoRR abs/2211.15477 (2022) arXiv
  19. Jérémie Chalopin, Victor Chepoi, and Ugo Giocanti. Graphs with convex balls. CoRR abs/2201.01599 (2022) arXiv
  20. 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
  21. 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
  22. 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
  23. 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
  24. Arun Kumar Das, Sandip Das, Guilherme Dias da Fonseca, Yan Gerard, and Bastien Rivier. Complexity Results on Untangling Planar Rectilinear Red-Blue Matchings. CoRR abs/2202.11857 (2022) arXiv
  25. Guilherme Dias da Fonseca, Yan Gerard, and Bastien Rivier. On the Longest Flip Sequence to Untangle Segments in the Plane. CoRR abs/2210.12036 (2022) arXiv

2021

  1. Manon Philibert. Cubes partiels: complétion, compression, plongement. (Partial cubes: completion, compression, embedding). Aix-Marseille University, France (2021)
  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. Oscar Defrain, Lhouari Nourine, and Takeaki Uno. On the dualization in distributive lattices and related problems. Discret. Appl. Math. 300: 85–96 (2021) DOI
  4. Oscar Defrain, Lhouari Nourine, and Simon Vilmin. Translating between the representations of a ranked convex geometry. Discret. Math. 344, 7: 112399 (2021) DOI
  5. 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
  6. 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
  7. Hugo Jacob, Thomas Bellitto, Oscar Defrain, and Marcin Pilipczuk. Close Relatives (Of Feedback Vertex Set), Revisited. 16th International Symposium on Parameterized and Exact Computation, IPEC 2021, September 8-10, 2021, Lisbon, Portugal, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 21:1–21:15 (2021) DOI
  8. Crombez Loı̈c, Guilherme Dias da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, and Luc Libralesso. Shadoks Approach to Low-Makespan Coordinated Motion Planning (CG Challenge). 37th International Symposium on Computational Geometry, SoCG 2021, June 7-11, 2021, Buffalo, NY, USA (Virtual Conference), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 63:1–63:9 (2021) DOI
  9. Crombez Loı̈c, Guilherme Dias da Fonseca, and Yan Gerard. Efficient Algorithms for Battleship. 10th International Conference on Fun with Algorithms, FUN 2021, May 30 to June 1, 2021, Favignana Island, Sicily, Italy, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 11:1–11:15 (2021) DOI
  10. 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
  11. Lukasz Bozyk, Oscar Defrain, Karolina Okrasa, and Michal Pilipczuk. On objects dual to tree-cut decompositions. CoRR abs/2103.14667 (2021) arXiv
  12. Hugo Jacob, Thomas Bellitto, Oscar Defrain, and Marcin Pilipczuk. Close relatives (of Feedback Vertex Set), revisited. CoRR abs/2106.16015 (2021) arXiv
  13. Marthe Bonamy, Oscar Defrain, Tereza Klimosová, Aurélie Lagoutte, and Jonathan Narboni. On Vizing’s edge colouring question. CoRR abs/2107.07900 (2021) arXiv
  14. 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
  15. Victor Chepoi, Kolja Knauer, and Manon Philibert. Labeled sample compression schemes for complexes of oriented matroids. CoRR abs/2110.15168 (2021) arXiv
  16. 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
  17. Crombez Loı̈c, Guilherme Dias da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, and Luc Libralesso. Shadoks Approach to Low-Makespan Coordinated Motion Planning. CoRR abs/2103.13956 (2021) arXiv
  18. Crombez Loı̈c, Guilherme Dias da Fonseca, and Yan Gerard. Greedy and Local Search Heuristics to Build Area-Optimal Polygons. CoRR abs/2106.14728 (2021) arXiv

2020

  1. François Brucker, Pascal Préa, and Célia Châtel. Totally Balanced Dissimilarities. J. Classif. 37, 1: 203–222 (2020) DOI
  2. Victor Chepoi, Kolja Knauer, and Manon Philibert. Two-Dimensional Partial Cubes. Electron. J. Comb. 27, 3: 3 (2020) DOI
  3. Victor Chepoi, Kolja Knauer, and Tilen Marc. Hypercellular graphs: Partial cubes without Q3- as partial cube minor. Discret. Math. 343, 4: 111678 (2020) DOI
  4. 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
  5. Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. On density of subgraphs of Cartesian products. J. Graph Theory 93, 1: 64–87 (2020) DOI
  6. Gautam K. Das, Guilherme Dias da Fonseca, and Ramesh K. Jallu. Efficient independent set approximation in unit disk graphs. Discret. Appl. Math. 280: 63–70 (2020) DOI
  7. Crombez Loı̈c, Guilherme Dias da Fonseca, and Yan Gerard. Efficiently Testing Digital Convexity and Recognizing Digital Convex Polygons. J. Math. Imaging Vis. 62, 5: 693–703 (2020) DOI
  8. Sarah Blind, Kolja Knauer, and Petru Valicov. Enumerating k-Arc-Connected Orientations. Algorithmica 82, 12: 3588–3603 (2020) DOI
  9. Stefan Felsner, Winfried Hochstättler, Kolja Knauer, and Raphael Steiner. Complete Acyclic Colorings. Electron. J. Comb. 27, 2: 2 (2020) DOI
  10. Kolja Knauer and Tilen Marc. On Tope Graphs of Complexes of Oriented Matroids. Discret. Comput. Geom. 63, 2: 377–417 (2020) DOI
  11. 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
  12. 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
  13. Rahul Arya, Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. Optimal Bound on the Combinatorial Complexity of Approximating Polytopes. Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, SIAM, 786–805 (2020) DOI
  14. 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
  15. Victor Chepoi, Kolja Knauer, and Manon Philibert. Ample completions of OMs and CUOMs. CoRR abs/2007.12527 (2020) arXiv
  16. Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. Distance labeling schemes for K_4-free bridged graphs. CoRR abs/2007.14192 (2020) arXiv
  17. Crombez Loı̈c, Guilherme Dias da Fonseca, and Yan Gerard. Efficient Algorithms for Battleship. CoRR abs/2004.07354 (2020) arXiv
  18. Stefan Felsner, Kolja Knauer, and Torsten Ueckerdt. Plattenbauten: Touching Rectangles in Space. CoRR abs/2007.07806 (2020) arXiv
  19. Garcı́a-Marco Ignacio and Kolja Knauer. On sensitivity in bipartite Cayley graphs. CoRR abs/2009.00554 (2020) arXiv
  20. 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

2019

  1. Sébastien Ratel. Density, VC-dimension, and graph labelings. Aix-Marseille University, France (2019)
  2. Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. On density of subgraphs of halved cubes. Eur. J. Comb. 80: 57–70 (2019) DOI
  3. 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
  4. 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
  5. Kolja Knauer and Nicolas Nisse. Computing metric hulls in graphs. Discret. Math. Theor. Comput. Sci. 21, 1 (2019) DOI
  6. Kolja Knauer and Petru Valicov. Cuts in matchings of 3-connected cubic graphs. Eur. J. Comb. 76: 27–36 (2019) DOI
  7. Kolja Knauer and Torsten Ueckerdt. Decomposing 4-connected planar triangulations into two trees and one path. J. Comb. Theory B 134: 88–109 (2019) DOI
  8. 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
  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. 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
  10. 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
  11. Crombez Loı̈c, Guilherme Dias da Fonseca, and Yan Gerard. Peeling Digital Potatoes. Proceedings of the 31st Canadian Conference on Computational Geometry, CCCG 2019, August 8-10, 2019, University of Alberta, Edmonton, Alberta, Canada, 124–132 (2019)
  12. Crombez Loı̈c, Guilherme Dias da Fonseca, and Yan Gérard. Efficient Algorithms to Test Digital Convexity. Discrete Geometry for Computer Imagery - 21st IAPR International Conference, DGCI 2019, Marne-la-Vallée, France, March 26-28, 2019, Proceedings, Springer, 409–419 (2019) DOI
  13. Ahmed Abdelkader, Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. Approximate Nearest Neighbor Searching with Non-Euclidean and Weighted Distances. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, SIAM, 355–372 (2019) DOI
  14. 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
  15. Victor Chepoi, Kolja Knauer, and Manon Philibert. Two-dimensional partial cubes. CoRR abs/1906.04492 (2019) arXiv
  16. 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
  17. Crombez Loı̈c, Guilherme Dias da Fonseca, and Yan Gérard. Efficient Algorithms to Test Digital Convexity. CoRR abs/1901.04738 (2019) arXiv
  18. Rahul Arya, Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. Optimal Bound on the Combinatorial Complexity of Approximating Polytopes. CoRR abs/1910.14459 (2019) arXiv
  19. 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
  20. 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
  21. Sarah Blind, Kolja Knauer, and Petru Valicov. Enumerating k-arc-connected orientations. CoRR abs/1908.02050 (2019) arXiv

2018

  1. Hans-Jürgen Bandelt, Victor Chepoi, and Kolja Knauer. COMs: Complexes of oriented matroids. J. Comb. Theory A 156: 195–237 (2018) DOI
  2. 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
  3. 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
  4. 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
  5. 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)
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. Distance and routing labeling schemes for cube-free median graphs. CoRR abs/1809.10508 (2018) arXiv
  12. Jérémie Chalopin and Victor Chepoi. 1-Safe Petri nets and special cube complexes: equivalence and applications. CoRR abs/1810.03395 (2018) arXiv
  13. 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
  14. Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. Approximate Convex Intersection Detection with Applications to Width and Minkowski Sums. CoRR abs/1807.00484 (2018) arXiv
  15. Crombez Loı̈c, Guilherme Dias da Fonseca, and Yan Gérard. Peeling Digital Potatoes. CoRR abs/1812.05410 (2018) arXiv
  16. 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
  17. Kolja Knauer, Piotr Micek, and Torsten Ueckerdt. The queue-number of planar posets. CoRR abs/1806.04489 (2018) arXiv
  18. Guyslain Naves and F. Bruce Shepherd. When Do Gomory-Hu Subtrees Exist? CoRR abs/1807.07331 (2018) arXiv