Undirected Wiener Index: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 10: | Line 10: | ||
== Parameters == | == Parameters == | ||
n: number of vertices (number of non-hydrogen atoms in the molecule) | $n$: number of vertices (number of non-hydrogen atoms in the molecule) | ||
== Table of Algorithms == | == Table of Algorithms == | ||
Latest revision as of 09:24, 10 April 2023
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 |