Minimum Witness Finding: Revision history

10 April 2023

• curprev 08:2708:27, 10 April 2023‎ Admin talk contribs‎ 1,429 bytes +4‎ No edit summary

15 February 2023

• curprev 12:0412:04, 15 February 2023‎ Admin talk contribs‎ 1,425 bytes −10‎ No edit summary

• curprev 10:2910:29, 15 February 2023‎ Admin talk contribs‎ 1,435 bytes +1,435‎ Created page with "{{DISPLAYTITLE:Minimum Witness Finding (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 $(i,..."