EUVIMEDEUVIMED entdecken
Crossref

TRIM: An Efficient Framework for Exact Eccentricity Computation on Large-Scale Graphs

Dian Ouyang, Jiajie Lin, Wentao Li, Fan Zhang, Jianye Yang, Xi Luo

Proceedings of the VLDB Endowment · 01.12.2025 · 19 (4) · 644-656

DOI: 10.14778/3785297.3785306 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 18.03.2026. Verfasst von Dian Ouyang und 5 weiteren Autor:innen. Die Arbeit nennt 40 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In graph theory, the eccentricity of a vertex quantifies its centrality by measuring the maximum distance to any other vertex in the graph. This metric underpins important graph properties such as the diameter (maximum eccentricity) of the graph, which is defined by the minimum and maximum centrality values across all vertices. Due to the substantial time overhead caused by full-graph BFS traversals, researchers have focused on incorporating bounding techniques to accelerate algorithm execution. However, the state-of-the-art approach is unable to identify useless vertices and fails to terminate during the search since its bound update relies on complete traversals. In this paper, we propose a novel framework that uses vertex dominance to identify redundant vertices and introduces a new rule to ensure correct termination after skipping a vertex. In addition, we adopt a merging strategy to reduce the number of traversals. Our method achieves up to two orders of magnitude speedup in runtime compared to the state-of-the-art approach. while efficiently handling graph data at the 100-million scale.

Zitieren

APA

Ouyang, D., Lin, J., Li, W., Zhang, F., Yang, J., & Luo, X. (2025). TRIM: An Efficient Framework for Exact Eccentricity Computation on Large-Scale Graphs. Proceedings of the VLDB Endowment, 19(4), 644-656. https://doi.org/10.14778/3785297.3785306

Vancouver

Ouyang D, Lin J, Li W, Zhang F, Yang J, Luo X. TRIM: An Efficient Framework for Exact Eccentricity Computation on Large-Scale Graphs. Proceedings of the VLDB Endowment. 2025;19(4):644-656. doi:10.14778/3785297.3785306

BibTeX
@article{Ouyang2025,
  author = {Ouyang, Dian and Lin, Jiajie and Li, Wentao and Zhang, Fan and Yang, Jianye and Luo, Xi},
  title = {TRIM: An Efficient Framework for Exact Eccentricity Computation on Large-Scale Graphs},
  journal = {Proceedings of the VLDB Endowment},
  year = {2025},
  volume = {19},
  number = {4},
  pages = {644--656},
  doi = {10.14778/3785297.3785306}
}
Kostenlos starten →