In this paper we propose a new algorithm for computing the diameter of directed unweighted graphs. Even though, in the worst case, this algorithm has complexity O(nm), where n is the number of nodes and m is the number of edges of the graph, we experimentally show that in practice our method works in O(m) time. Moreover, we show how to extend our algorithm to the case of directed weighted graphs and, even in this case, we present some preliminary very positive experimental results.
ON COMPUTING THE DIAMETER OF REAL-WORLD DIRECTED (WEIGHTED) GRAPHS / P. CRESCENZI; R. GROSSI; L. LANZI; A. MARINO. - STAMPA. - (2012), pp. 99-110. (Intervento presentato al convegno 11TH INTERNATIONAL SYMPOSIUM ON EXPERIMENTAL ALGORITHMS) [10.1007/978-3-642-30850-5_10].
ON COMPUTING THE DIAMETER OF REAL-WORLD DIRECTED (WEIGHTED) GRAPHS
CRESCENZI, PIERLUIGI;LANZI, LEONARDO;MARINO, ANDREA
2012
Abstract
In this paper we propose a new algorithm for computing the diameter of directed unweighted graphs. Even though, in the worst case, this algorithm has complexity O(nm), where n is the number of nodes and m is the number of edges of the graph, we experimentally show that in practice our method works in O(m) time. Moreover, we show how to extend our algorithm to the case of directed weighted graphs and, even in this case, we present some preliminary very positive experimental results.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
