Results

The project PN-IV-P8-8.3-PM-RO-FR-2024-0064, the title of which is ,,Locality Study of Some network Tasks (LoSST)’’, was divided in two main steps. The results obtained during the project are detailed in what follows:

Phase 1/2024, the title of which is ,,Gp-unimodality: Characterization and Recognition’’, has been divided in three main activities:

  • Activity 1.1, the title of which is ,,Structure of graphs with Gp-unimodal centrality functions’’, has resulted in a research report on the local properties of the eccentricity functions (also known as radius functions) in some graph classes that are studied in Metric Graph Theory. Furthermore, this main result was completed with a Python implementation of the decomposition algorithm for median graphs in so-called theta-classes.
  • Activity 1.2, the title of which is ,,Recognition of graphs with Gp-unimodal centrality functions’’, has resulted in a polynomial-time algorithm for computing the least value p such that all the radius functions of a graph G are Gp-unimodal. Furthermore, a preliminary experimental study on the local properties of the eccentricity function in random graphs was performed. The PhD students Elena Paraschiv and Maria Popa did a short research visit in France during this activity (12/02/2024-12/16/2024).
  • Activity 1.3, the title of which is ,,Project management and dissemination’’, has resulted in a new scientific article: ,,On Gp-unimodality of radius functions in graphs : structure and algorithms’’, co-authored by J. Chalopin, V. Chepoi, F.F. Dragan, G. Ducoffe and Y. Vaxes. Another scientific article: ,,Quasilinear-time eccentricities computation, and more, on median graphs’’, co-authored by Pierre Bergé (LIMOS), Guillaume Ducoffe (ICI București) and Michel Habib (IRIF) was published in the proceedings of the A* conference SODA 2025.

Phase 2/2025, the title of which is ,,Applications of Unimodality’’, has been divided in three main activities:

  • Activity 2.1, the title of which is ,,Algorithms for computing a most central vertex’’, has resulted in: (1) truly subquadratic-time algorithms for the exact computation of a central vertex (i.e., of minimum eccentricity) for several classes of graphs studied in Metric Graph Theory; (ii) linear-time, or almost linear-time, algorithms for the (exact or approximate) computation of a central vertex in some Gromov hyperbolic classes of graphs; and (3) quasilinear-time algorithms for the exact computation of a central vertex, respectively of the median, in the classes of pseudo-median graphs and quasi-median graphs. These main results were completed by a full implementation of the linear-time algorithm of Bénéteau et al. for the computation of the median in median graphs. The PhD students Elena Paraschiv and Maria Popa did a short research visit in France during this activity (10/14/2025-10/28/2025).
  • Activity 2.2, the title of which is ,,Unimodality properties of real datasets’’, has resulted in a theoretical study on the Gp-unimodalitaty of centrality indices (graph centrality and closeness centrality) in median graphs and in chordal graphs. The study of these classes of graphs was motivated by their applications in medicine and biology. Furthermore, a preliminary theoretical analysis of the local properties of the eccentricity function in dense random graphs was performed.
  • Activity 2.3, the title of which is ,,Project management and dissemination’’, has resulted in the publication on arXiv of our research report ,,On Gp-unimodality of radius functions in graphs : structure and algorithms’’. The final version of the report combines results from both phases of the project. Two more articles are in preparation. Furthermore, both partners have agreed to maintain their fruitful collaboration through various national and international project calls (IRN CNRS, IUF, ERC Synergy, etc.). The PhD student Elena Paraschiv attended in Iași to the symposium on French-speaking research in central and east Europe (SRSF-ECO’2025, 10/30/2025-10/31/2025).