Calculation in Special Types of Graph
When the underlying graph is a tree (as is true for instance for the alkanes originally studied by Wiener), the Wiener index may be calculated more efficiently. If the graph is partitioned into two subtrees by removing a single edge e, then its Wiener index is the sum of the Wiener indices of the two subtrees, together with a third term representing the paths that pass through e. This third term may be calculated in linear time by computing the sum of distances of all vertices from e within each subtree and multiplying the two sums. This divide and conquer algorithm can be generalized from trees to graphs of bounded treewidth, and leads to near-linear-time algorithms for such graphs.
An alternative method for calculating the Wiener index of a tree, by Bojan Mohar and Tomaž Pisanski, works by generalizing the problem to graphs with weighted vertices, where the weight of a path is the product of its length with the weights of its two endpoints. If v is a leaf vertex of the tree then the Wiener index of the tree may be calculated by merging v with its parent (adding their weights together), computing the index of the resulting smaller tree, and adding a simple correction term for the paths that pass through the edge from v to its parent. By repeatedly removing leaves in this way, the Wiener index may be calculated in linear time.
For graphs that are constructed as products of simpler graphs, the Wiener index of the product graph can often be computed by a simple formula that combines the indices of its factors. Benzenoids (graphs formed by gluing regular hexagons edge-to-edge) can be embedded isometrically into the Cartesian product of three trees, allowing their Wiener indices to be computed in linear time by using the product formula together with the linear time tree algorithm.
Read more about this topic: Wiener Index
Famous quotes containing the words calculation, special, types and/or graph:
““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)
“Fashions change, and with the new psychoanalytical perspective of the postwar period [WWII], child rearing became enshrined as the special responsibility of mothers ... any shortcoming in adult life was now seen as rooted in the failure of mothering during childhood.”
—Sylvia Ann Hewitt (20th century)
“He’s one of those know-it-all types that, if you flatter the wig off him, he chatter like a goony bird at mating time.”
—Michael Blankfort. Lewis Milestone. Johnson (Reginald Gardner)
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)