Undirected Wiener Index (Wiener Index)

From Algorithm Wiki
Jump to navigation Jump to search


Calculate the sum of the lengths of the shortest paths between all pairs of vertices in an undirected graph (typically in the chemical graph representing the non-hydrogen atoms in the molecule).

Related Problems

Related: Minimum Wiener Connector Problem


$n$: number of vertices (number of non-hydrogen atoms in the molecule)

Table of Algorithms

Currently no algorithms in our database for the given problem.

Reductions FROM Problem

Problem Implication Year Citation Reduction
Min-Weight k-Cycle if: to-time: $f(N,M)$ for N nodes, M edges
then: from-time: $\tilde{O}(f(N,M)+M)$
2018 https://arxiv.org/pdf/1712.08147v2.pdf, Theorem B.2 link