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 cannot set aside an hour for discussion with our children and hope that it will be a time of deep encounter. The special moments of intimacy are more likely to happen while baking a cake together, or playing hide and seek, or just sitting in the waiting room of the orthodontist.”
—Neil Kurshan (20th century)
“Our major universities are now stuck with an army of pedestrian, toadying careerists, Fifties types who wave around Sixties banners to conceal their record of ruthless, beaverlike tunneling to the top.”
—Camille Paglia (b. 1947)
“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)