Negative Triangle Detection

Given an $n$ node graph $G = (V, E)$ with edge weights $w: E \rightarrow W$ , determine whether there is a negative triangle, i.e. three vertices that form a triangle with total edge weights summing to a negative number.

Parameters

$n$ : number of nodes
$m$ : number of edges

Related Problems

Exact Triangle2
- Real Exact Triangle
- All-Edges Exact Triangle1
- - Real All-Edges Exact Triangle1
  - #Real All-Edges Exact Triangle

Triangle Detection6
- Negative Triangle Detection1
- - Negative Triangle Search1
  - Negative Triangle Listing
- Nondecreasing Triangle
- Minimum Triangle
- Triangle in Unweighted Graph
- Triangle Listing
- Triangle Collection*

Edge Triangle Detection

Edge Triangle Counting

Vertex Triangle Listing

Dynamic Vertex Triangle Listing

Triangle Collection

All-Color-Pairs Triangle Collection*

All-Color-Pairs Triangle Collection

$\Delta$ -Matching Triangles

All-Edges Monochromatic Triangle1
- #All-Edges Monochromatic Triangle

Minimum Weight Triangle

Combinatorial Triangle Detection

Insufficient data to display graph

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Insuffient Data to display table

Reductions Table

Displaying 27 of 27 reductions


Directed, Weighted APSP	Negative Triangle Detection	2018
Negative Triangle Detection	Distance Product Verification	2018
Distance Product	Negative Triangle Detection	2018
Negative Triangle Search	Negative Triangle Detection	2018
Negative Triangle Listing	Negative Triangle Detection	2018
Distance Product	Negative Triangle Detection	2018
Distance Product	Negative Triangle Detection	2018
Distance Product	Negative Triangle Detection	2018
Minimum Witness Finding	Negative Triangle Detection	2018
All Pairs Minimum Witness (APMW)	Negative Triangle Detection	2018
Metricity	Negative Triangle Detection	2018
Negative Triangle Detection	Metricity	2018
Negative Triangle Detection	Shortest Cycle	2018
Negative Triangle Detection	2D Maximum Subarray	2018
Negative Triangle Detection	Price Query	2018
Negative Triangle Detection	2D Maximum Subarray	2016
Negative Triangle Detection	Betweenness Centrality (BC)	2015
Negative Triangle Detection	Directed Radius	2015
Negative Triangle Detection	Undirected Radius	2015
Negative Triangle Detection	Directed Median	2015
Negative Triangle Detection	Undirected Median	2015
Negative Triangle Detection	All-Nodes Median Parity	2015
Negative Triangle Detection	Directed All-Nodes Positive Betweenness Centrality	2015
Negative Triangle Detection	Undirected All-Nodes Positive Betweenness Centrality	2015
Negative Triangle Detection	Negative Triangle Search
Negative Triangle Detection	Minimum Witness Finding
Triangle Detection	Negative Triangle Detection

Other relevant algorithms

Insuffient Data to display table