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)
“What causes adolescents to rebel is not the assertion of authority but the arbitrary use of power, with little explanation of the rules and no involvement in decision-making. . . . Involving the adolescent in decisions doesn’t mean that you are giving up your authority. It means acknowledging that the teenager is growing up and has the right to participate in decisions that affect his or her life.”
—Laurence Steinberg (20th century)