Fast diameter and radius BFS-based computation in (weakly connected)  real-world graphs: With an application to the six degrees of separation
games

Michele Borassi; Pierluigi Crescenzi; Michel Habib; Walter A. Kosters; Andrea Marino; Frank W. Takes

doi:10.1016/j.tcs.2015.02.033

Article Dans Une Revue Theoretical Computer Science Année : 2015

Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs: With an application to the six degrees of separation games

(1) , (2) , (3) , (4) , (5) , (4)

1
2
3
4
5

Michele Borassi

Fonction : Auteur
PersonId : 974705

IMT Institute of Advanced Studies

Pierluigi Crescenzi

Fonction : Auteur
PersonId : 974706

Dipartimento di Ingegneria dell'Informazione [Firenze]

Michel Habib

Fonction : Auteur
PersonId : 11388
IdHAL : michel-habib
ORCID : 0000-0002-8564-2314
IdRef : 067223613

Networks, Graphs and Algorithms

Walter A. Kosters

Fonction : Auteur
PersonId : 974707

Leiden Institute of Advanced Computer Science [Leiden]

Andrea Marino

Fonction : Auteur

Dipartimento di Informatica

Frank W. Takes

Fonction : Auteur
PersonId : 974708

Leiden Institute of Advanced Computer Science [Leiden]

Résumé

We discuss very effcient diameter computation algorithms and applied them on huge graphs.

Mots clés

Graphs Algorithms diameter computations

Domaines

Informatique [cs] Algorithme et structure de données [cs.DS]

Michel Habib : Connectez-vous pour contacter le contributeur

https://inria.hal.science/hal-01255125

Soumis le : mercredi 13 janvier 2016-11:08:15

Dernière modification le : lundi 15 avril 2024-11:02:04

Dates et versions

hal-01255125 , version 1 (13-01-2016)

Identifiants

HAL Id : hal-01255125 , version 1
DOI : 10.1016/j.tcs.2015.02.033

Citer

Michele Borassi, Pierluigi Crescenzi, Michel Habib, Walter A. Kosters, Andrea Marino, et al.. Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs: With an application to the six degrees of separation games. Theoretical Computer Science, 2015, 586, pp.21. ⟨10.1016/j.tcs.2015.02.033⟩. ⟨hal-01255125⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

UNIV-PARIS7 CNRS INRIA INRIA2

78 Consultations

0 Téléchargements