Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

Tytuł pozycji:

The Weighted Matching Approach to Maximum Cardinality Matching

Szczegóły
Abstrakt

Tytuł:: The Weighted Matching Approach to Maximum Cardinality Matching
Autorzy:: Gabow, H. N.
Data publikacji:: 2017
Słowa kluczowe:: weighted graph
cardinal numbers
algorithms
variables
linear models
Język:: angielski
Dostawca treści:: BazTech
: Artykuł

Przejdź do źródła

Several papers have achieved time O(√nm) for cardinality matching, starting from first principles. This results in a long derivation. We simplify the task by employing well-known concepts for maximum weight matching. We use Edmonds’ algorithm to derive the structure of shortest augmenting paths. We extend this to a complete algorithm for maximum cardinality matching in time O(√nm).

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies

Informacja

The Weighted Matching Approach to Maximum Cardinality Matching