empaktus's blog

By empaktus, history, 3 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.

Full text and comments »

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