La existencia de bipartito perfecto maridaje

Question

Deje que $B = G(L, R, E)$ ser un bipartito gráfico.Quiero saber si este grafo tiene un perfecto maridaje.Una forma de probar si este grafo tiene un perfecto maridaje del Salón del Matrimonio Teorema, pero es ineficiente (he.e $|\mathcal P(L)| = 2^{|L|}$ exámenes-no polinomio).Siempre puedo averiguar si un perfecto maridaje que existe mediante el cálculo de un máximo de cardinalidad de coincidencia y las pruebas de su perfección, pero esto implica el cálculo de la perfecta coincidencia.

Hay un eficiente forma de decidir si un perfecto coincidente bipartita existe sin el cómputo de la coincidencia de uno mismo?Idealmente me gustaría que un algoritmo, el cual es más rápido que los algoritmos como Hopcroft Karp o matriz de correspondencia basada en algoritmos, que explícitamente encontrar la coincidencia (he.e así que no la computación de la coincidencia de sentido).

Editar:La cursiva parte.

Answer 1

Una rápida revisión de la literatura sugiere que el mejor algoritmo para decidir si una densa bipartito gráfica tiene un perfecto maridaje es todavía la matriz de algoritmo, que se ejecuta en el tiempo $O(|V|^\omega)$.Usted puede reducir el espacio del algoritmo, ver El aislamiento, la Coincidencia y Contando por Allender, Reinhardt y Zhou. Un artículo reciente a partir de 2010, que se centra en grafos planares, sugiere que el resultado de Allender et al.es la mejor que se conoce.