Menu
The Wiener polarity index of a graph \( G \) is the number of unordered pairs of vertices \( u, v \) such that the distance between \( u \) and \( v \) is three, which was introduced by Harold Wiener in 1947. A linear time algorithm for computing the Wiener polarity index of trees was described, and also an algorithm which computes the index \( W_p(G) \) for any given connected graph \( G \) on \( n \) vertices in time \( O(M(n)) \) was presented, where \( M(n) \) denotes the time necessary to multiply two \( n \times n \) matrices of small integers (which is currently known to be \( O(n^{2.376}) \)). In this paper, we establish one polynomial algorithm to calculate the value of the Wiener polarity index of a bipartite graph.