ANR DISTANCIA Main/Publications

H. La and P. Valicov, Computer assisted discharging procedure on planar graphs: application to 2-distance coloring, (submitted).
M. Barbato, R. Grappe, M. Lacroix, E. Lancini, R. Wolfler Calvo, The Schrijver system of the flow cone in series–parallel graphs, Discrete Applied Mathematics, 2020.
M. Barbato, R. Grappe, M. Lacroix, E. Lancini, On k-edge-connected Polyhedra: Box-TDIness in Series-Parallel Graphs, ISCO 2020: 27-41.
M. Bonamy, B. Mohar, A. Wesolek, Limiting crossing numbers for geodesic drawings on the sphere, short version: Graph Drawing 2020.
V. Bartier, L. Bénéteau, M. Bonamy, H. La, J. Narboni, A note on deterministic zombies, (submitted).
V. Chepoi, K. Knauer, and M. Philibert, Ample completions of OMs and CUOMs, (submitted).
V. Dujmović, L. Esperet, G. Joret, C. Gavoille, P. Micek, P. Morin, Adjacency Labelling for Planar Graphs (and Beyond), short version: FOCS 2020.
M. Bonamy, M. Pilipczuk, J.S. Sereni, On the effect of symmetry requirement for rendezvous on the complete graph, (submitted).
M. Bonamy, C. Gavoille, M. Pilipczuk, Shorter Labeling Schemes for Planar Graphs, short version: SODA 2020.
M. Bonamy, P. Charbit, O. Defrain, G. Joret, A. Lagoutte, V. Limouzy, L. Pastor, J.-S. Sereni, Revisiting a theorem by Folkman on graph colouring, The Electronic Journal of Combinatorics (2020)
M. Bonamy, N. Bousquet, L. Esperet, C. Groenland, F. Pirot, A. Scott, Surfaces have (asymptotic) dimension 2, (submitted).
M. Bonamy, N. Morrison, A. Scott, Partitioning the vertices of a torus into isomorphic subgraphs, Journal of Combinatorial Theory, series A (2020).
J. Chalopin, V. Chepoi, A. Genevois, H. Hirai, and D. Osajda, Helly groups, (submitted).
N. Bousquet, W. Cames van Batenburg, L. Esperet, G. Joret, W. Lochet, C. Muller, F. Pirot, Packing and covering balls in graphs excluding a minor, Combinatorica (to appear).
V. Chepoi, A. Labourel, and S. Ratel, Distance labeling schemes for K4-free bridged graphs, (submitted), short version: SIROCCO 2020, pp.310-327.
F. Foucaud, H. Hocquard, S. Mishra, N. Narayanan, R. Naserasr, É. Sopena, P. Valicov, Exact square coloring of subcubic planar graphs, (to appear in Discrete Applied Mathematics)
S. Blind, K. Knauer, P. Valicov, Enumerating k-arc-connected orientations, Algorithmica 82 (2020), 3588-3603.
L. Bénéteau, J. Chalopin, V. Chepoi, Y. Vaxès, Medians in median graphs in linear time, (submitted), short version: ICALP 2020, pp.10:1-10:17.
A. Kosowski, P. Uznanski, L. Viennot, Hardness of exact distance queries in sparse graphs through hub labeling, PODC 2019.
L. Beaudou, G. Kahn, M. Rosenfeld, Bisplit graphs satisfy the Chen-Chvátal conjecture, DMTCS 21(1) (2019), #5
L. Beaudou, R. Brewster, On the multipacking number of grid graphs, DMTCS 21(3) (2019), #23.
S. Klavžar, K. Knauer, T. Marc On the Djoković-Winkler relation and its closure in subdivisions of fullerenes, triangulations, and chordal graphs, (submitted).
V. Chepoi, K. Knauer, and M. Philibert, Two-dimensional partial cubes, Electron. J. Combin. 27(3): P3.29 (2020).
S. Felsner, W. Hochstättler, K. Knauer, R. Steiner Complete Acyclic Colorings, (submitted).
O. Aichholzer, J. Cardinal, T. Huynh, K. Knauer, T. Mütze, R. Steiner, B. Vogtenhuber, Flip distances between graph orientations, WG 2019 (to appear).
G. Guégan, K. Knauer, J. Rollin, T. Ueckerdt, The interval number of a planar graph is at most three, J. Combin. Th. Ser. B (to appear).
S. Gupta, A. Kosowski, L. Viennot, Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond, short version: ICALP 2019, pp.143:1-143:15.
J. Chalopin, V. Chepoi, S. Moran, and M. Warmuth, Unlabeled sample compression schemes and corner peelings for ample and maximum classes (submitted), short version: ICALP 2019, pp.34:1-34:15.
F. Brucker, P. Préa, and C. Chatel, Totally balanced dissimilarities, J. Classification, 36 (2019), 1-20.
É. Bonnet, N. Bousquet, P. Charbit, S. Thomassé, and R. Watrigant, Parameterized complexity of independent set in H-free graphs, short vestion: IPEC 2018, pp.17:1-17:13.
M. Bonamy, E. Bonnet, N. Bousquet, P. Charbit, and S. Thomassé, EPTAS for max clique on disks and unit balls, short version: FOCS 2018, pp. 568-579.
J. Chalopin and V. Chepoi, 1-Safe Petri nets and special cube complexes: equivalence and applications, ACM Transactions on Computational Logic, Vol. 20, No. 3, Article 17, 49 pages.
J. Chalopin and V. Chepoi, A counterexample to Thiagarajan's conjecture, J. Comput. Syst. Sci. 113: 76-100 (2020).
J. Chalopin, V. Chepoi, F. Dragan, G. Ducoffe, A. Mohammed, and Y. Vaxès, Fast approximation and exact computation of negative curvature parameters of graphs, Discrete and Computational Geometry (2019). https://doi.org/10.1007/s00454-019-00107-9, short version: Symposium on Computational Geometry 2018, pp.22:1-22:15.
V. Chepoi, F. F. Dragan, M. Habib, Y. Vaxès, and H. Al-Rasheed, Fast approximation of centrality and distances in hyperbolic graphs, Journal of Graph Algorithms and Applications 23 (2019), pp.393-433, short version: COCOA 2018, pp. 3-18.
F. Dragan, M. Habib, and L. Viennot, Revisiting radius, diameter, and all eccentricity computation in graphs through certificates (submitted).
M. Bonamy, P. Ouvrard, M. Rabie, J. Suomela, and J. Uitto, Distributed recoloring (submitted), short version: DISC 2018, pp.12:1-12:17.
K. Knauer, P. Micek, and T. Ueckerdt, The queue-number of posets of bounded width or height, short version: Graph Drawing 2018, pp.200-212.
K. Knauer and N. Nisse, Computing metric hulls in graphs, DMTCS (accepted).
K. Knauer and T. Marc, On tope graphs of complexes of oriented matroids, Discrete & Computational Geometry (accepted).
I. García-Marco, K. Knauer, and L.P. Montejano, Chomp on generalized Kneser graphs and others, International Journal of Game Theory (accepted).
S. Fujita, M. Furuya, R. Naserasr, K. Ozeki. A new approach towards a conjecture on intersecting three longest paths, Journal of Combinatorics, 10 (2019), 221-234.
V. Chepoi, A. Labourel, and S. Ratel, Distance and routing labeling schemes for cube-free median graphs, Algorithmica (to appear), short version: MFCS 2019, pp.15:1-15:14.
V. Chepoi, A. Labourel, and S. Ratel, On density of subgraphs of Cartesian products, J. Graph Theory 93 (2020), 64--87.
V. Chepoi, A. Labourel, and S. Ratel, On density of subgraphs of halved cubes, European J. Combinatorics 80 (2019), 57-70 (memorial volume for Michel Deza).
D. Cornaz, R. Grappe, and M. Lacroix, Trader multiflow and box-TDI systems in series-parallel graphs, Discrete Optimization 31 (2019), 103-114.
G. Naves, B. Shepherd, H. Xia, Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators (submitted).
G. Naves, F. B. Shepherd, When Do Gomory-Hu subtrees exist? (submitted).