TY - GEN
T1 - Wiener index and Diameter of a Planar Graph in Subquadratic Time
AU - Wulff-Nilsen, Christian
N1 - Conference code: 25
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
M3 - Article in proceedings
SP - 25
EP - 28
BT - Proceedings of the 25th European Workshop on Computational Geometry (EuroGC´09)
T2 - 25th European Workshop on Computational Geometry
Y2 - 16 March 2009 through 18 March 2009
ER -