1 Department of Computer Science, Faculty of Science, Københavns Universitet2 The APL Section, Department of Computer Science, Faculty of Science, Københavns Universitet3 Administration, Department of Computer Science, Faculty of Science, Københavns Universitet4 Administration, Department of Computer Science, Faculty of Science, Københavns Universitet
Consider the problem of computing the sum of distances between each pair of vertices of an unweighted graph. This sum is also known as the Wiener index of the graph, a generalization of a definition given by H. Wiener in 1947. A molecular topological index is a value obtained from the graph structure of a molecule such that this value (hopefully) correlates with physical and/or chemical properties of the molecule. The Wiener index is perhaps the most studied molecular topological index with more than a thousand publications. It is open whether the Wiener index of a planar graph can be obtained in subquadratic time. In my talk, I will solve this open problem by exhibiting an O(n2 log log n / log n) time algorithm, where n is the size of the graph. A simple modification yields an algorithm with the same time bound that computes the diameter (maximum distance between any vertex pair) of a planar graph. I will also sketch the main ideas involved in obtaining O(n2(log log n)4/log n) time algorithms for planar graphs with arbitrary non-negative edge weights.
Proceedings of the 25th European Workshop on Computational Geometry (eurogc´09), 2009, p. 25-28
Main Research Area:
25th European Workshop on Computational Geometry, 2009