Metricity

Description

Given an $n\times n$ nonnegative matrix $A$, determine whether $A$ defines a metric on $(n)$, that is, that A is symmetric, has 0s on the diagonal, and its entries satisfy the triangle inequality.

Parameters

$n$: dimensionality of matrix

Table of Algorithms

Currently no algorithms in our database for the given problem.

Reductions TO Problem

Problem	Implication	Year	Citation	Reduction
Negative Triangle Detection	if: to-time: $O(n^{2}) + T(O(n), O(M))$ where $T(n,M)$ is nondecreasing then: from-time: $O(n^{2}) + T(O(n), O(M))$ where the metricity problem is on $(n)$ s.t. all distances are in $(-M, M)$	2018	https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 5.2	link

Reductions FROM Problem

Problem	Implication	Year	Citation	Reduction
Negative Triangle Detection	if: to-time: $O(n^{2}) + T(O(n), O(M))$ where the metricity problem is on $(n)$ s.t. all distances are in $(-M, M)$, and $T(n,M)$ is nondecreasing then: from-time: $O(n^{2}) + T(O(n), O(M))$	2018	https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 5.2	link