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)
“The arbitrary division of one’s life into weeks and days and hours seemed, on the whole, useless. There was but one day for the men, and that was pay day, and one for the women, and that was rent day. As for the children, every day was theirs, just as it should be in every corner of the world.”
—Alice Caldwell Rice (1870–1942)