Undirected Wiener Index (Wiener Index)
Revision as of 10:25, 15 February 2023 by Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Undirected Wiener Index (Wiener Index)}} == 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 == <pre>n: number of vertices (number of non-hydrogen atoms in the molecule)</pre> == Table of Algorithms == Cur...")
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 |