Wiener index and Diameter of a Planar Graph in Subquadratic Time

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

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 languageEnglish
Title of host publicationProceedings of the 25th European Workshop on Computational Geometry (EuroGC´09)
Number of pages4
Publication date2009
Pages25-28
Publication statusPublished - 2009
Event25th European Workshop on Computational Geometry - Brussels, Belgium
Duration: 16 Mar 200918 Mar 2009
Conference number: 25

Conference

Conference25th European Workshop on Computational Geometry
Nummer25
LandBelgium
ByBrussels
Periode16/03/200918/03/2009

ID: 12874118