Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
An Exact Algorithm for Diameters of Large Real Directed Graphs
verfasst von : Takuya Akiba, Yoichi Iwata, Yuki Kawata
Erschienen in: Experimental Algorithms
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We propose a new algorithm to compute the diameters of large real directed graphs. In contrast to recent algorithms, the proposed algorithm is designed for general directed graphs, i.e., it does not assume that given graphs are undirected or strongly connected. Experimental results on large real graphs show that the proposed algorithm is several orders of magnitude faster than the naive approach, and it reveals the exact diameters of large real directed graphs, for which only lower bounds have been known.