Can this problem be solved faster than O(n^2) ?

Правка en1, от empaktus, 2024-04-10 22:28:48

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 maight be probabilistic.

Теги flow, graphs, algorithm complexity

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский empaktus 2024-04-10 22:29:08 1 Tiny change: 'lgorithm maight be pr' -> 'lgorithm might be pr'
en1 Английский empaktus 2024-04-10 22:28:48 543 Initial revision (published)