Calculation in Arbitrary Graphs
The Wiener index may be calculated directly using an algorithm for computing all pairwise distances in the graph. When the graph is unweighted (so the length of a path is just its number of edges), these distances may be calculated by repeating a breadth-first search algorithm, once for each starting vertex. The total time for this approach is O(nm), where n is the number of vertices in the graph and m is its number of edges.
For weighted graphs, one may instead use the Floyd–Warshall algorithm or Johnson's algorithm, with running time O(n3) or O(nm + n2 log n) respectively. Alternative but less efficient algorithms based on repeated matrix multiplication have also been developed within the chemical informatics literature.
Read more about this topic: Wiener Index
Famous quotes containing the words calculation and/or arbitrary:
““To my thinking” boomed the Professor, begging the question as usual, “the greatest triumph of the human mind was the calculation of Neptune from the observed vagaries of the orbit of Uranus.”
“And yours,” said the P.B.”
—Samuel Beckett (1906–1989)
“Pity on the person who has become accustomed to seeing in necessity something arbitrary, who ascribes to the arbitrary some sort of reason, and even claims that following that sort of reason has religious value.”
—Johann Wolfgang Von Goethe (1749–1832)