Puterea modelelor de interval în problema calculării indicilor de centralitate

Guillaume DUCOFFE
Institutul Naţional de Cercetare Dezvoltare în Informatică – ICI Bucureşti
guillaume.ducoffe@ici.ro

Universitatea din București, Facultatea de Matematică și Informatică, București, România

Rezumat: Modelarea “structurii liniare” care este prezentă în mai multe sisteme, precum rețelele trofice, problemele de alocare a resurselor și ADN-ul, are la bază grafurile de interval (grafuri intersecție a unor intervale de pe o linie dreapta). Totodată, având în vedere că mulțimile de date reale pot conține greșeli și zgomot, este nevoie de a extinde rezultatele algoritmice obținute pentru grafurile de interval la unele clase de grafuri mai generale. Această problematică este abordată în contextul calculării excentricităților, datorită importanței acestora privind clasificarea nodurilor unei rețele. O astfel de generalizare este obținută de la grafurile de interval până la grafurile interval+ (obținute prin adăugarea a noduri într-un graf de interval). În special, un algoritm care rulează în timp cvasiliniar, pentru orice valoare fixată, este propus. Până în prezent, timpul de rulare al celui mai bun algoritm pentru această problema era cvadratic în numărul de noduri (Bentert & Nichterlein, 2022). Cu toate aceasta, este demonstrat sub unele ipoteze standard de complexitate că o astfel de generalizare nu este posibilă pentru grafurile al cărui număr de interval este limitat la o constantă.

Cuvinte cheie: grafuri de interval, număr de interval, algoritmi adaptivi, calcularea excentricităților, ipoteza timpului exponențial puternic.

Vizualizează articolul complet

COORDONATELE PENTRU CITAREA ACESTUI ARTICOL SUNT URMĂTOARELE:
Guillaume DUCOFFE, Puterea modelelor de interval în problema calculării indicilor de centralitate, Revista Română de Informatică şi Automatică (Romanian Journal of Information Technology and Automatic Control), ISSN 1220-1758, vol. 32(4), pp. 33-44, 2022. https://doi.org/10.33436/v32i4y202203