Who know Maximal Matching Problems O(n) solution?

Farid Ahmadov · Post by **Farid Ahmadov** » Tue Jul 29, 2003 8:11 pm

Hi. I know only O(n^3) solution for this problem.
How I can get O(n) solution.
Thanks.

Miguel Angel · Post by **Miguel Angel** » Thu Aug 07, 2003 4:58 pm

I don't think so, actually O(N^3) is well to solve it even 'cause that algorithm is called pseudopolynomial.
The unique way will be that the problems offers you some constraints that make such problem trivial and so a O(N) solution can be applied, but i can't figure out right now

.

makbet · Post by **makbet** » Fri Aug 08, 2003 11:47 am

Are you talking about normal or bipartie graphs? In the first case
O(n^3) is probably the best you can get. In the second case the fastest known algorithm is O(sqrt(V)*E)

nghiank · Post by **nghiank** » Sun Aug 10, 2003 8:30 am

makbet · Post by **makbet** » Sun Aug 10, 2003 10:32 am

Go find it yourself, it's called
Hopcroft-Karp's.

OJ Board

Who know Maximal Matching Problems O(n) solution?

Who know Maximal Matching Problems O(n) solution?

Noup