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.
2012
Experimental Algorithms
11TH INTERNATIONAL SYMPOSIUM ON EXPERIMENTAL ALGORITHMS
P. CRESCENZI; R. GROSSI; L. LANZI; A. MARINO
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/655824
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 22
  • ???jsp.display-item.citation.isi??? ND
social impact