Rezultate

Proiectul PN-IV-P8-8.3-PM-RO-FR-2024-0064, cu titlul ,,Studiul despre proprietățile locale ale unor probleme ale rețelelor (LoSST)’’, a fost împărțit în două etape. Rezultatele obținute sunt detaliate, în cele ce urmează, în conformitate cu planul de realizare a proiectului.

Etapa 1/2024, denumită ,,Unimodalitate în Gp : Caracterizare şi Recunoaştere’’, a fost compusă din trei activități principale:

  • Activitatea 1.1, intitulată ,,Structura grafurilor ale căror funcții de centralitate sunt Gp-unimodale’’, a avut ca rezultat principal un raport de cercetare despre proprietățile locale ale funcțiilor de excentricitate ale unor clase de grafuri studiate în teoria metrică a grafurilor (Metric Graph Theory). Totodată, un alt rezultat obținut în cadrul acestei activități a constat într-un cod sursă pentru a descompune grafurile mediane (una dintre clasele mai sus menționate).
  • Activitatea 1.2, intitulată ,,Recunoaşterea grafurilor ale căror funcții de centralitate sunt Gp-unimodale’’, a avut ca rezultat principal un algoritm în timp polinomial pentru calcularea valorii minime p astfel încât toate funcțiile de excentricitate ale unui graf G sunt Gp-unimodale. Totodată, s-a și realizat un studiu experimental preliminar despre proprietățile locale ale funcțiilor de excentricitate ale unor grafuri aleatoare. În cadrul acestei activități, doctorantele Elena Paraschiv şi Maria Popa au efectuat o vizită de durată scurtă (2.12.2024-16.12.2024) la partenerul francez.
  • Activitatea 1.3, intitulată ,,Gestionarea proiectului și Diseminare’’, a avut ca rezultat principal redactarea unui articol științific nou, cu titlul ,,On Gp-unimodality of radius functions in graphs : structure and algorithms’’, al cărui autori sunt J. Chalopin, V. Chepoi, F.F. Dragan, G. Ducoffe şi Y. Vaxes. Dintre aceștia toți sunt membri ai proiectului, cu excepția lui F.F. Dragan. Totodată, articolul ,,Quasilinear-time eccentricities computation, and more, on median graphs’’, având ca co-autori Pierre Bergé (LIMOS), Guillaume Ducoffe (ICI București) şi Michel Habib (IRIF) a fost publicat în proceeding-urile conferinței de clasă A* SODA 2025.

Etapa 2/2025, denumită ,,Aplicațiile proprietății de unimodalitate’’, a fost compusă din trei activități principale:

  • Activitatea 2.1, intitulată ,,Algoritmi pentru calcularea vârfului cel mai central’’, a avut următoarele rezultate principale : (1) unii algoritmi în timp subcvadratic pentru calcularea exactă a unui vârf central (al cărui excentricitatea este minimă) în mai multe clase de grafuri studiate în teoria metrică a grafurilor (Metric Graph Theory) ; (ii) unii algoritmi în timp liniar, sau cvasi-liniar, pentru calcularea exactă și/sau aproximată a unui vârf central în unele clase de grafuri hiperbolice ; și (3) unii algoritmi în timp cvasi-liniar pentru calcularea exactă a unui vârf central, respectiv a unui vârf median, în clasele de grafuri pseudo-median și cvasi-median. Aceste rezultate teoretice au fost completate cu implementarea unui algoritm în timp liniar pentru calcularea unui vârf median al unui graf median; acest algoritm a fost prezentat și analizat formal într-un articol științific al partenerului francez. În cadrul acestei activități, doctorantele Elena Paraschiv şi Maria Popa au efectuat o vizită de durată scurtă (14.10.2025-28.10.2025) la partenerul francez.
  • Activitatea 2.2, intitulată ,,Proprietățile locale ale unor mulțimi de date reale’’, a avut ca rezultat principal un studiu teoretic despre proprietățile de Gp-unimodalitate ale indicilor de centralitate (excentricitate și apropiere/closeness) pentru grafurile median și grafurile cordal. Motivația pentru studierea claselor de grafuri mai sus menționate vine din aplicațiile lor în domeniile medical și biologic. Totodată, s-a și realizat un studiu teoretic preliminar despre proprietățile locale ale funcțiilor de excentricitate ale unor grafuri aleatoare dense.
  • Activitatea 2.3, intitulată ,,Gestionarea proiectului și Diseminare’’, a avut ca rezultat principal publicarea unui raport tehnic pe serverul arXiv, cu titlul ,,On Gp-unimodality of radius functions in graphs : structure and algorithms’’. Articolul științific corespunzător, care combină unele rezultate obținute în ambele etape ale proiectului, a fost trimis spre publicare la o revistă de top. Pe baza multiplelor rezultate obținute în cadrul acestui proiect, mai sunt două articole care se află în curs de redactare. Totodată, am convenit să prelungim parteneriatul cu echipa franceză în cadrul mai multor apeluri de proiecte (IRN CNRS, IUF, ERC Synergy, etc.). În cadrul acestei activități, doctoranda Elena Paraschiv a participat la o conferință la Iași despre cercetarea francofonă în Europa Centrală și de Est (SRSF-ECO’2025, 30.10.2025-31.10.2025).