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)
“And weren’t there special cemetery flowers,
That, once grief sets to growing, grief may rest:
The flowers will go on with grief awhile,
And no one seem neglecting or neglected?
A prudent grief will not despise such aids.”
—Robert Frost (1874–1963)
“The American man is a very simple and cheap mechanism. The American woman I find a complicated and expensive one. Contrasts of feminine types are possible. I am not absolutely sure that there is more than one American man.”
—Henry Brooks Adams (1838–1918)
“When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
—Marshall McLuhan (1911–1980)