Minimum Triangle (Graph Triangle Problems)

From Algorithm Wiki
Jump to navigation Jump to search


Find the triangle in a graph with minimum weight

Related Problems

Generalizations: Triangle Detection

Related: Negative Triangle Detection, Negative Triangle Search, Negative Triangle Listing, Nondecreasing Triangle, Triangle in Unweighted Graph, Triangle Collection*


$n$: number of nodes

$m$: number of edges

Table of Algorithms

Currently no algorithms in our database for the given problem.

Reductions TO Problem

Problem Implication Year Citation Reduction
Second Shortest Simple Path if: to-time: $T(n,W)$ where there are $n$ nodes and integer weights in $({0}, W)$
then: from-time: $T(O(n), O(nW))$ for $n$ node graph with integer weights in $(-W, W)$
2018, Theorem 5.5 link