Shortest Cycle (Graph Cycles)
Revision as of 10:29, 15 February 2023 by Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Shortest Cycle (Graph Cycles)}} == Description == Given a graph $G=(V,E)$ with non-negative weights, find a minimum weight cycle. == Related Problems == Subproblem: Shortest k-Cycle == Parameters == <pre>n: number of vertices m: number of edges</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions FROM Problem == {| class="wikitable sortable" style="text-align:center;" width="100%"...")
Description
Given a graph $G=(V,E)$ with non-negative weights, find a minimum weight cycle.
Related Problems
Subproblem: Shortest k-Cycle
Parameters
n: number of vertices m: number of edges
Table of Algorithms
Currently no algorithms in our database for the given problem.
Reductions FROM Problem
| Problem | Implication | Year | Citation | Reduction |
|---|---|---|---|---|
| Negative Triangle Detection | if: to-time: $T(n,M)$ where there are $n$ nodes and weights in $({1}, M)$ then: from-time: $T(n, O(M))$ where there are $n$ nodes and weights in $(-M, M)$ |
2018 | https://dl-acm-org.ezproxy.canberra.edu.au/doi/pdf/10.1145/3186893, Theorem 5.3 | link |