Edge-Wiener Index of Benzenoid Systems in Linear Time
Presented by Prof. Sandi KLAVžAR
Type: Oral presentation
The edge-Wiener index of a graph $G$ is defined as the Wiener index of the line graph of $G$. An algorithm will be presented that, for a given benzenoid system $G$ with $m$ edges, computes the edge-Wiener index of $G$ in $O(m)$ time. The key to the algorithm is a reduction of the problem to three different weighted trees. In addition to the previously used weighted vertex- and edge-Wiener indices, the so-called weighted vertex-edge-Wiener index will be introduced and essentially used in the algorithm.