Publication list of V. Chepoi

J. Chalopin, V. Chepoi, N. Nisse, Y. Vaxes Cop and robber games when the robber can hide and ride (submitted).

V. Chepoi, D. Osajda, Dismantlability of weakly systolic complexes and applications (submitted).

N. Catusse, V. Chepoi, Y. Vaxes, Embedding into the rectilinear plane in optimal O(n^2) time (submitted).

H.-J. Bandelt, V. Chepoi, D. Eppstein, Combinatorics and geometry of finite and infinite squaregraphs (submitted).

V. Chepoi, F. Dragan, B. Estellon, M. Habib, Y. Vaxes, Diameters, centers, and approximating trees of delta-hyperbolic geodesic spaces and graphs. Symposium on Computational Geometry, SoCG'2008, pp.59-68.

V. Chepoi, M. Seston, Seriation in the presence of errors: an approximation algorithm for fitting Robinson structures to dissimilarity matrices, Algorithmica (to appear), short version: STACS'2009.

V. Chepoi, F. Dragan, B. Estellon, M. Habib, Y. Vaxès, Y. Xiang, Additive spanners and distance and routing labeling schemes for delta-hyperbolic graphs (submitted).

V. Chepoi, N. Creignou, M. Hermann, and G. Salzer, Helly property and satisfiability of Boolean formulas defined on set systems, European J. Combinatorics (to appear), short version: ISMVL'2008, pp. 100-105.

V. Chepoi, K. Nouioua, E. Thiel and Y. Vaxès, Pareto envelopes in simple polygons, (submitted), short version: European Workshop on Computational Geometry, EWCG'2008.

V. Chepoi, B. Estellon, Packing and covering delta-hyperbolic spaces by balls, APPROX-RANDOM'07, August 20-22, 2007, Princeton, USA.

V. Chepoi, T. Févat, E. Godard, and Y. Vaxès, A self-stabilizing algorithm for the median problem in partial rectangular grids and their relatives, (submitted) short version: SIROCCO'07, 2007, pp. 81-95.

V. Chepoi, K. Nouioua, Pareto envelopes in R^3 under l_1 and l_infty distance functions, (slides) Symposium on Computational Geometry SoCG'2007, pp. 284-293.

V. Chepoi, B. Fichet, M. Seston, Seriation in the presence of errors: NP-hardness of l_infty-fitting Robinson structures to dissimilarity matrices. J. Classification (to appear).

V. Chepoi, B. Estellon, Y. Vaxes, On covering planar graphs with a fixed number of balls, Discr. Comput. Geometry 37 (2007), 237-244.

V. Chepoi, B. Estellon, K. Nouioua, Y. Vaxes, Mixed covering of trees and the augmentation problem with odd diameter constraints Algorithmica 45 (2006), 209-226.

V. Chepoi, B. Estellon, Y.Vaxes, Approximation algorithms for forests augmentation ensuring two disjoint paths of bounded length, Theoretical Computer Science 401 (2008), 131-143. short version WADS'2005, pp. 282-293.

V. Chepoi, K. Nouioua, Y.Vaxes, A rounding algorithm for approximating minimum Manhattan networks, Theoretical Computer Science, 390 (2008), 56-69 and short version APPROX-RANDOM'2005, pp. 40-51.

H.-J. Bandelt, V. Chepoi, Metric graph theory and geometry: a survey, Surveys on Discrete and Computational Geometry: Twenty Years Later, J.E. Goodman, J. Pach, and R. Pollack (eds), Contemp. Math., 453 (2008), pp. 49-86.

V. Chepoi, F. Dragan, Y.Vaxes, Distance and routing problems in plane graphs of non-positive curvature, J. Algorithms 61 (2006) 1-30.

H.-J. Bandelt, V. Chepoi, The algebra of metric betweenness I: subdirect representation and retracts Europ. J. Combin. 28 (2007), 1640-1661.

H.-J. Bandelt, V. Chepoi, The algebra of metric betweenness II: axiomatics of weakly median graphs. Europ. J. Combin. 29, (2008), 676-700.

V. Chepoi, Basis graphs of even Delta-matroids. J. Combin. Th. Ser B 97 (2007), 175-192.

H.-J. Bandelt, V. Chepoi, A. Dress, J. Koolen, Combinatorics of lopsided sets, Europ. J. Combin. 27(2006), 669-689.

V. Chepoi, F. Dragan, Y.Vaxes, Distance-based location update and routing in irregular cellular networks, SAWN'05, pp. 380-387.

V. Chepoi, F. Dragan, Y. Vaxès. Addressing, distances and routing in triangular systems with applications in cellular and sensor networks, Wireless Networks 12 (2006) 671-679, also WMAN'04.

V. Chepoi, C.Fanciullini, Y.Vaxes, Median problem in some plane triangulations and quadrangulations, Comput. Geometry 27(2004) 193-210.

V. Chepoi, H. Noltemeier, Y. Vaxes, Upgrading trees under diameter and budget constraints, Networks 41(2003) 24-35.

V. Chepoi, F. F. Dragan, Chenyu Yan, Additive sparse spanners for graphs with bounded length of largest induced cycle. Theor. Comput. Sci. 347(2005), 54-75, also CIAC'03 pp. 96-107.

V. Chepoi, Y. Vaxes, On covering planar bridged triangulations with balls, J. Graph Th. 44(2003), 65-80.

H.-J. Bandelt, V. Chepoi, 1-Hyperbolic graphs, SIAM J. Discr. Math. 16(2003) 323-334.

V. Chepoi, F.Dragan, Y.Vaxes, Center and diameter problem in planar quadrangulations and triangulations, SODA'02, pp. 346-355.

V. Chepoi, A. Rollin, Interval routing in some planar networks, Theor. Comput. Sci. 290(2003) 1503-1540, also SIROCCO'01, pp. 89-104.

V. Chepoi, Y. Vaxes, Augmenting trees to meet connectivity and diameter constraints, Algorithmica 33 (2002), 243-262.

H.-J. Bandelt, V. Chepoi, Graphs with connected medians, SIAM J. Discr. Math. 16(2002), 268-282.

V. Chepoi, F. Dragan, Finding a central vertex in HHD-free graphs, Discr. Appl. Math. 131 (2003), 93-111.

H.-J. Bandelt, V. Chepoi, A. Dress, J. Koolen, Geometry of lopsided sets (in preparation).

V. Chepoi, Graphs of some CAT(0) complexes, Adv. Appl. Math. 24(2000), 125-179.

H.-J. Bandelt, V. Chepoi, A. Karzanov, A characterization of minimizable metrics in the multifacility location problem, Europ. J. Combin. 21 (2000), 715-725.

V. Chepoi, F. Dragan, A note on distance approximating trees, Europ. J. Combin. 21 (2000), 761-766.

H.-J. Bandelt and V. Chepoi, Decomposition and l_1-embedding of weakly median graphs, Europ. J. Combin. 21 (2000), 701-714.

V. Chepoi and B. Fichet, l_infty-Approximation via subdominants, J. Math. Psychology 44(2000), 600-616.

A. Brandstaedt, V. Chepoi, and F. Dragan, Distance approximating trees for chordal and dually chordal graphs, J. Algorithms, 30 (1999), 166-184, also    ESA'97, pp. 78-91.

V. Chepoi, On distance-preserving and domination orderings, SIAM J. Discr. Math., 11 (1998), 414-436.

H.-J. Bandelt, V. Chepoi, Embedding into the rectilinear grid, Networks 32(1998), 127-132.

H.-J. Bandelt, V. Chepoi, M. Laurent, Embedding into rectilinear spaces, Discr. Comput. Geometry 19(1998), 595-604.

V. Chepoi, A note on r-dominating clique problem, Discr. Math. 183 (1998), 47-60.

A. Brandstädt, Dragan F.F., Chepoi V.D., Voloshin V.I, Dually chordal graphs, SIAM J. Discr. Math. 11 (1998), 437-455, also WG'93 pp. 237-251.

A. Brandstaedt, V. Chepoi, F. Dragan, The algorithmic use of the hypertree structure and maximum neighbourhood orderings,  Discr. Appl. Math. 83 (1998), 121-155, also WG'94 pp. 70-80.

V. Chepoi, B. Fichet, A note on circular decomposable metrics, Geom. Dedicata 69 (1998), 237-240.

A. Brandstaedt, V. Chepoi, F. Dragan, Clique r-domination and clique r-packing problems on dually chordal graphs,  SIAM J. Discr. Math. 10(1997), 109-127.

V. Chepoi, A T_X approach to some results on cuts and metrics, Adv. Appl. Math. 19(1997), 453-470.

V. Chepoi, Bridged graphs are cop-win graphs: an algorithmic proof, J. Combin. Th., Ser B 69 (1997), 97-100.

V. Chepoi, Peakless functions on graphs, Discr. Appl. Math. 73(1997), 175-189.

V. Chepoi, B. Fichet, Recognition of Robinsonian dissimilarities, J. Classif. 14(1997), 311-325.

V. Chepoi, M. Deza, V. Grishukhin, Clin d'oeil on L_1-embeddable planar graphs, Discr. Appl. Math. 80(1997), 3-19.

V. Chepoi, S. Klavzar, Distances in benzenoid systems: Further developments, Discr. Math. 192 (1998) 27-39.

V. Chepoi, A multifacility location problem on median spaces, Discr. Appl. Math. 64(1996), 1-29.

V. Chepoi, On staircase starshapedness in rectilinear spaces, Geom. Dedicata 63(1996), 321-329.

V. Chepoi, S. Klavzar The Wiener Index and the Szeged Index of Benzenoid Systems in Linear Time J. Chem. Inf. and Comp. Sci. 37(4) (1997), 752-755.

V. Chepoi, V. Patlatii, C. Prisacaru L_1-embeddability of rectilinear polygons with holes J. Geometry 56 (1996), 18-24.

V. Chepoi, O.Topala Tverberg numbers for cellular bipartite graphs, Archiv der Mathematik 66 (1996), 258-264.

V. Chepoi, On distances in benzenoid systems, J. Chem. Inf. and Comp. Sci. 36(6) (1996), 1169-1172.

H.-J. Bandelt, V. Chepoi, Embedding metric spaces in the rectilinear plane: a six--point criterion, Discr. Comput. Geometry 15(1996), 107-117.

H.-J. Bandelt, V. Chepoi, Graphs of acyclic cubical complexes, Europ. J. Combin. 17(1996), 113-120.

H.-J. Bandelt, V. Chepoi, Cellular bipartite graphs, Europ. J. Combin. 17(1996), 121-134.

H.-J. Bandelt, V. Chepoi, A Helly theorem in weakly modular spaces, Discr. Math. 125(1996) 25-39.

A. Brandstaedt, V. Chepoi, F. Dragan, Perfect elimination orderings of chordal powers of graphs, Discr. Math. 124 (1996), 273-278.

V. Chepoi, F. Dragan, Condorcet and median points of simple rectilinear polygons, Location Science 4(1996) 21-35, also MFCT'95, pp. 181-190.

V. Chepoi, On starshapedness in products of interval spaces, Archiv der Mathematik 64 (1995), 264-268.

V. Chepoi, Separation of two convex sets in convexity structures, J. Geometry 50 (1994), 30-51.

V. Chepoi, F. Dragan, Computing the median point of a simple rectilinear polygon, Inf. Proc. Lett. 49 (1994), 281-285.

V. Chepoi, F. Dragan, A linear algorithm for computing a central vertex of a chordal graph, ESA'94, 159-170.

V. Chepoi, On a property of a space of orderings, Automation and Remote Control 8 (1993), 131-136 (Russian, English transl.).

V. Chepoi, Centers of triangulated graphs, Math. Notes 43 (1988), 143-151.

V. Chepoi, Isometric subgraphs of Hamming graphs and d-convexity, Cybernetics 1(1988), 6-10.

V. Soltan, V. Chepoi, Conditions for invariance of set diameter under d-convexification in a graph, Cybernetics 6(1983), 14-18.

V. Chepoi, Classification of graphs by metric triangles, Metody Diskretnogo Analyza 49 (1989), 75-93 (Russian).

V. Chepoi, F. Dragan, A linear time algorithm for computing the link central point of a simple rectilinear polygon (unpublished manuscript) (1993).