Paper Info
Title
On the Solvability of the Six Degrees of Kevin Bacon Game - A Faster Graph Diameter and Radius Computation Method.
Abstract
In this paper, we will propose a new algorithm that computes the radius and the diameter of a graph G = (V, E), by finding bounds through heuristics and improving them until exact values can be guaranteed. Although the worst-case running time is O(vertical bar V vertical bar.vertical bar E vertical bar), we will experimentally show that, in the case of real-world networks, it performs much better, finding the correct radius and diameter value after 10-100 BFSes instead of vertical bar V vertical bar BFSes (independent of the value of vertical bar V vertical bar), and thus having running time O(vertical bar E vertical bar). Apart from efficiency, compared to other similar methods, the one proposed in this paper has three other advantages. It is more robust (even in the worst cases, the number of BFSes performed is not very high), it is able to simultaneously compute radius and diameter (halving the total running time whenever both values are needed), and it works both on directed and undirected graphs with very few modifications. As an application example, we use our new algorithm in order to determine the solvability over time of the "six degrees of Kevin Bacon" game.
Year
Venue
Field
2014
Lecture Notes in Computer Science
Discrete mathematics,Graph,Combinatorics,Six degrees of separation,Distance,Heuristics,Mathematics,Computation
DocType
Volume
ISSN
Conference
8496
0302-9743
Citations 
PageRank 
References 
5
0.43
7
Authors
6
Name
Order
Citations
PageRank
Michele Borassi1404.13
Pierluigi Crescenzi2100295.31
Michel Habib371.12
Walter A. Kosters431032.97
Andrea Marino518523.48
Frank W. Takes65712.92