empaktus's blog

Can this problem be solved faster than O(n^2) ?
By empaktus, history, 7 months ago, In English

I have a list of pairs of strings (or pairs of hashes) called V. I want to create a list W by removing elements from V such that W has as many pairs as possible and: There are no i,j such that W[i].first==W[j].first There are no i,j such that W[i].second==W[j].second I know it can be solved with max-flow, but the complexity would be at least O(|V|^2) because that would be the amount of edges in the graph. Is there any algorithm faster than that?, the algorithm might be probabilistic.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it +9 Vote: I do not like it

This is literally maximum matching. But the complexity should be $$$O(V \sqrt{V})$$$ if one uses Dinic/Hopcroft-Karp for solving the maximum matching.

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The amount of edges would be |V|.

→ Reply