Undirected Wiener Index: Difference between revisions
Jump to navigation
Jump to search
(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...") |
No edit summary |
||
| Line 10: | Line 10: | ||
== Parameters == | == Parameters == | ||
n: number of vertices (number of non-hydrogen atoms in the molecule) | |||
== Table of Algorithms == | == Table of Algorithms == | ||
Revision as of 13:03, 15 February 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 |