Блог пользователя ikk

Автор ikk, 15 лет назад, По-английски

The rank of the Tutte matrix T of a graph G is equal to twice the size of a maximum matching of G.  There exists a nondeterministic algorithm based on this fact for maximum matching problem on a general graph G.  That is, repeatedly replace T's indeterminates with random real numbers and compute the rank of T, and let the size of maximum matching be the maximum rank / 2.  This works because the rank of T does not incrase by random assignments.

But the algorithm didn't work for me.  In particular, the graph with the adjacency matrix at the bottom of this code has a maximum matching of size 7, but the code reports it has 8.

What mistake did I make?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
for(int k = i; k < m; ++k)
		A[j][k] -= A[r][k] * A[j][i];
In this line you'll first change A[j][i] to 0 and then you'll be subtracting A[r][k] * 0 = 0.