Abstract
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.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 25th European Workshop on Computational Geometry (EuroGC´09) |
| Number of pages | 4 |
| Publication date | 2009 |
| Pages | 25-28 |
| Publication status | Published - 2009 |
| Event | 25th European Workshop on Computational Geometry - Brussels, Belgium Duration: 16 Mar 2009 → 18 Mar 2009 Conference number: 25 |
Conference
| Conference | 25th European Workshop on Computational Geometry |
|---|---|
| Number | 25 |
| Country/Territory | Belgium |
| City | Brussels |
| Period | 16/03/2009 → 18/03/2009 |