Undirected Wiener Index (Wiener Index)
Jump to navigation
Jump to search
Description
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
Parameters
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 |