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

Nondeterministic algorithm for maximum matching problem on a general graph
Автор ikk, 13 лет назад, По-английски

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
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 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.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Oops!  Thank you for pointing this out.  The rest of the code seems correct.  (Your comment doesn't appear on English Codeforces, although it itself is in English, by the way.)
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Oh, sorry, I forgot to switch the comments' language. By default it is Russian in my case, even though the original topic was in English.
      → Ответить