| HAL-Inria | Publications, software ... of Inria's scientists |
Journal articles
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
1
Pierluigi Crescenzi
2
Michel Habib
3
Walter Kosters
4
Andrea Marino
5
Frank Takes
4
3
GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Michele Borassi 1
Mail :
Author
Pierluigi Crescenzi 2
Mail :
Author
Michel Habib 3
Mail :
Author IdHAL : michel-habib
Walter A. Kosters 4
Mail :
Author
Andrea Marino 5
Author
Frank W. Takes 4
Mail :
Author
1
IMT Institute of Advanced Studies (Piazza S. Ponziano, 6 - 55100 Lucca - Italy)
2
DINFO - Dipartimento di Ingegneria dell'Informazione [Firenze] (Via di S. Marta, 3 - 50139 Firenze - Italy)
- Università degli Studi di Firenze = University of Florence [Firenze] (Piazza di San Marco, 4, 50121 Firenze FI, Italie - Italy)
3
GANG - Networks, Graphs and Algorithms (France)
- LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications (Université Paris Diderot, Bât. Sophie Germain, case postale 7014, 75205 Paris cedex 13 - France)
- UPD7 - Université Paris Diderot - Paris 7 (5 rue Thomas-Mann - 75205 Paris cedex 13 - France)
- CNRS - Centre National de la Recherche Scientifique : UMR7089 (France)
- Inria Paris-Rocquencourt (INRIA Rocquencourt : Domaine de Voluceau, Rocquencourt B.P. 105 78153 le Chesnay Cedex - France)
- Inria - Institut National de Recherche en Informatique et en Automatique (Domaine de Voluceau Rocquencourt - BP 105 78153 Le Chesnay Cedex - France)
4
LIACS - Leiden Institute of Advanced Computer Science [Leiden] ( Niels Bohrweg 1 2333 CA Leiden - Netherlands)
- Universiteit Leiden [Leiden] (P.O. Box 9500 2300 RA Leiden - Netherlands)
5
ISLab - Dipartimento di Informatica (Information Systems and knowledge management - Via Festa del Perdono 7 - 20122 Milano - Italy)
- Università degli studi di Milano [Milano] (Via Festa del Perdono 7 - 20122 Milano - Italy)
Abstract : We discuss very effcient diameter computation algorithms and applied them on huge graphs.
Document type :
Journal articles
Complete list of metadatas
https://hal.inria.fr/hal-01255125
Contributor : Michel Habib <>
Submitted on : Wednesday, January 13, 2016 - 11:08:15 AM
Last modification on : Wednesday, April 15, 2020 - 9:56:12 AM
Contributor : Michel Habib <>
Submitted on : Wednesday, January 13, 2016 - 11:08:15 AM
Last modification on : Wednesday, April 15, 2020 - 9:56:12 AM
Links full text
Identifiers
- HAL Id : hal-01255125, version 1
- DOI : 10.1016/j.tcs.2015.02.033
Collections
CNRS | UNIV-PARIS7 | INRIA | USPC
Citation
Michele Borassi, Pierluigi Crescenzi, Michel Habib, Walter 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, Elsevier, 2015, 586, pp.21. ⟨10.1016/j.tcs.2015.02.033⟩. ⟨hal-01255125⟩
Metrics
Record views