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)
“We’ve got to figure these things a little bit different than most people. Y’know, there’s something about going out in a plane that beats any other way.... A guy that washes out at the controls of his own ship, well, he goes down doing the thing that he loved the best. It seems to me that that’s a very special way to die.”
—Dalton Trumbo (1905–1976)
“As for types like my own, obscurely motivated by the conviction that our existence was worthless if we didn’t make a turning point of it, we were assigned to the humanities, to poetry, philosophy, painting—the nursery games of humankind, which had to be left behind when the age of science began. The humanities would be called upon to choose a wallpaper for the crypt, as the end drew near.”
—Saul Bellow (b. 1915)
“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)