Temat: maximal matching - Prolib Integro

Skocz do pozycji: 1.

Tytuł:: The hardness of the independence and matching clutter of a graph
Autorzy:: Hambardzumyan, S.
Mkrtchyan, V. V.
Musoyan, V. L.
Sargsyan, H.
Tematy:: clutter
hardness
independent set
maximal independent set
matching
maximal matching; Pokaż więcej
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Powiązania:: https://bibliotekanauki.pl/articles/952814.pdf Link otwiera się w nowym oknie
Opis:: A clutter (or antichain or Sperner family) L is a pair (V, E), where V is a finite set and E is a family of subsets of V none of which is a subset of another. Usually, the elements of V are called vertices of L, and the elements of E are called edges of L. A subset se of an edge e of a clutter is called recognizing for e, if se is not a subset of another edge. The hardness of an edge e of a clutter is the ratio of the size of e's smallest recognizing subset to the size of e. The hardness of a clutter is the maximum hardness of its edges. We study the hardness of clutters arising from independent sets and matchings of graphs.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 2.

Tytuł:: Skojarzenia w teorii grafów
Matching in graph theory
Autorzy:: Niedzielski, Krzysztof
Opis:: Python implementation of selected graph algorithms for matchingsis presented. Matching in an undirected graph is a subset of edgesin which at most one edge is incident to any graph vertex.Finding a maximum matching in graph is an important stepin many approximation algorithms (Chinese postman problem and travelling salesman problem among others) and for some types of graphs it can help in solving other difficult problems in polynomial time, for example in finding minimal vertex cover.Algorithms for finding a maximum matching in various graphs are implemented. Dynamic programming is used to find a maximum matching in trees.Finding a maximum matching in the bipartite graphs leads to the maximum flow problem in flow networks.For this reason, a few algorithms concerning this problem are shown:Ford-Fulkerson algorithm (a recursive version),Edmonds-Karp algorithm, and Dinic algorithm.The most important algorithm that allows to find a maximum matchingin general graphs is the Edmonds blossom algorithm.Its implemetation is described in detail, because various methodsare based on it.Its invention proved for the first time that a maximum matching could be found in polynomial time.Matching in weighted bipartite graphs is related to theassignment problem, which is an important subject in the realm ofcombinatorial optimization. Hungarian algorithm used to solve this problem is shown.In the case of general weighted graphs,a greedy algorithm for finding a minimum weight matching is discussed.
W pracy przedstawiono implementację w języku Python wybranychalgorytmów związanych ze skojarzeniami. Skojarzenie topodzbiór krawędzi w grafie nieskierowanym, dla którego co najwyżejjedna krawędź łączy się z którymkolwiek wierzchołkiem grafu.Odnalezienie największego skojarzenia w grafie stanowi ważny krokw wielu algorytmach aproksymacyjnych, np. dla problemuchińskiego listonosza, czy problemu komiwojażera.Dla pewnych typów grafów znajomość największego skojarzenia pozwala rozwiązywać inne trudne problemy w czasie wielomianowym,np. problem minimalnego pokrycia wierzchołkowego.Zaimplementowano algorytmy pozwalające na odnajdywanie skojarzenianajwiększego w różnych rodzajach grafów. Zastosowano technikę programowania dynamicznego do stworzeniaalgorytmu znajdującego największe skojarzenie dla drzew.Wyszukiwanie skojarzenia największego w grafach dwudzielnychmożna sprowadzić do problemu wyznaczania maksymalnego przepływuw sieci przepływowej. W związku z tym zaimplementowano kilka algorytmówzwiązanych z tą tematyką. Zaprezentowano algorytm Edmondsa-Karpa,algorytmu Dynica i rekurencyjną implementację metody Forda-Fulkersona.Kluczowym algorytmem pozwalającym na znalezienie skojarzenianajwiększego w dowolnym grafie nieskierowanym jestalgorytm kwiatowy Edmondsa.Jego wynalezienie udowodniło, że największe skojarzenie można znaleźćw czasie wielomianowym, co dało początek nowym metodom w teorii grafów.W pracy przedstawiono implementację algorytmu Edmondsawraz ze szczegółowym opisem.Skojarzenia w grafach dwudzielnych ważonych są związane z problememprzyporządkowania, stanowiącym ważne zagadnienieoptymalizacji kombinatorycznej. Przedstawiono implementacjęalgorytmu węgierskiego znajdującego skojarzenie o~najmniejszej wadze.Dla przypadku ogólnych grafów ważonych pokazano algorytm zachłannyznajdujący przybliżone rozwiązanie tego problemu.
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego

Inne

na półce

Skocz do pozycji: 3.

Tytuł:: The matching extendability of 7-connected maximal 1-plane graphs
Autorzy:: Huang, Yuanqiu
Zhang, Licheng
Wang, Yuxi
Tematy:: perfect matching
7-connected maximal $1$-plane graph
matching extendability; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/59896520.pdf Link otwiera się w nowym oknie
Opis:: A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. A graph, together with a 1-planar drawing is called 1-plane. A graph is said to be $k (\ge 1)$-extendable if every matching of size $k$ can be extended to a perfect matching. It is known that the vertex connectivity of a 1-plane graph is at most 7. In this paper, we characterize the $k$-extendability of $7$-connected maximal $1$-plane graphs. We show that every $7$-connected maximal $1$-plane graph with even order is $k$-extendable for $1\le k\le 3$. And any $7$-connected maximal $1$-plane graph is not $k$-extendable for $4\le k\le 11$. As for $k\ge 12$, any $7$-connected maximal $1$-plane graph with $n$ vertices is not $k$-extendable unless $n=2k$.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Informacja

Wyszukujesz frazę "maximal matching" wg kryterium: Temat