Informatyka bipartite-matching

1

Jak szybko możemy obliczyć rozmiar maksymalnego dopasowania na nieważonym grafie dwustronnym?

Czy istnieje sposób na obliczenie wielkości maksymalnego dopasowania na nieważonym grafie dwustronnym bardziej efektywnie (np. Szybciej) niż obliczenie maksymalnego dopasowania? Jest to dalekie ujęcie, ale często interesującym problemem jest unikanie takich niepotrzebnych obliczeń. Motywacja Problem, który próbuję rozwiązać, to match-2, w którym oba zestawy mają różne rozmiary. Muszę ustalić, czy …

11 algorithms graphs optimization matching bipartite-matching

2

Ograniczenie maksymalnego przepływu do dopasowania dwustronnego?

Istnieje słynna i elegancka redukcja od maksymalnego problemu dwustronnego dopasowania do problemu maksymalnego przepływu: tworzymy sieć z węzłem źródłowym , węzłem końcowym i jednym węzłem dla każdego elementu, który ma być dopasowany, a następnie dodajemy odpowiednie krawędzie.sssttt Z pewnością istnieje sposób na ograniczenie maksymalnego przepływu do maksymalnego dopasowania dwustronnego w …

9 reductions network-flow bipartite-matching

2

Rozmiar maksymalnego dopasowania na wykresie dwudzielnym

Czy w mojej obserwacji mam rację, że liczność maksymalnego dopasowania MMM wykresu dwudzielnego G(U,V,E)G(U,V,E)G(U, V, E) jest zawsze równy min(|U|,|V|)min(|U|,|V|)\min(|U|, |V|)?

9 graph-theory graphs bipartite-matching

Pytania otagowane jako bipartite-matching