All Pairs Minimum Witness: Difference between revisions
(Created page with "{{DISPLAYTITLE:All Pairs Minimum Witness (Minimum Witness)}} == Description == Fix an instance of negative triangle with node sets $I, J, K$ and weight function $w$. Let $i \in I, j \in J, k \in K$. Recall that the triple $(i, j, k)$ is a negative triangle iff $(w(i, k) \odot w(k, j)) + w(i, j) < 0$. Fix a total ordering $<$ on the nodes in $K$ in the negative triangle instance. For any $i \in I, j \in J$, a node $k \in K$ is called a minimum witness for $(i, j)$ if $(...") |
No edit summary |
||
| Line 12: | Line 12: | ||
== Parameters == | == Parameters == | ||
n: number of vertices | |||
m: number of edges | |||
m: number of edges | |||
== Table of Algorithms == | == Table of Algorithms == | ||
Currently no algorithms in our database for the given problem. | Currently no algorithms in our database for the given problem. | ||
Revision as of 13:04, 15 February 2023
Description
Fix an instance of negative triangle with node sets $I, J, K$ and weight function $w$. Let $i \in I, j \in J, k \in K$. Recall that the triple $(i, j, k)$ is a negative triangle iff $(w(i, k) \odot w(k, j)) + w(i, j) < 0$. Fix a total ordering $<$ on the nodes in $K$ in the negative triangle instance. For any $i \in I, j \in J$, a node $k \in K$ is called a minimum witness for $(i, j)$ if $(i, j, k)$ is a negative triangle but $(i, j, k')$ is not a negative triangle for all $k' < k$ according to the ordering.
All Pairs Minimum Witness (APMW) is the problem of finding a minimum witness $k$ for each pair $(i,k)$ if such a $k$ exists for $(i,j)$.
Related Problems
Generalizations: Minimum Witness Finding
Parameters
n: number of vertices
m: number of edges
Table of Algorithms
Currently no algorithms in our database for the given problem.