|
| void | findMaximalMatching (const Graph &graph, ArrayBuffer< edge > &matching) |
| | Obtains a maximal matching in O(|E|) time.
|
| |
| int | findMaximumCardinalityMatching (const Graph &G, const List< node > &U, const List< node > &V, EdgeArray< bool > &matching) |
| | Finds a maximum cardinality matching in the bipartite graph G = (U+V, E) in O(sqrt(|U+V|) * |E|) time by using the Hopcroft-Karp-Karzanov algorithm.
|
| |
| template<typename EdgeContainer > |
| bool | isMatching (const Graph &graph, const EdgeContainer &matching) |
| | Checks in time O(|V| + size of matching) if the given set of edges represents a matching.
|
| |
| template<typename EdgeContainer > |
| bool | isMaximal (const Graph &graph, const EdgeContainer &matching) |
| | Checks in time O(|E|) if there are edges that could be added to matching.
|
| |
| template<typename EdgeContainer > |
| bool | isMaximal (const Graph &graph, const EdgeContainer &matching, edge &addable) |
| | Checks in time O(|E|) if there are edges that could be added to matching.
|
| |
| template<typename EdgeContainer > |
| bool | isMaximalMatching (const Graph &graph, const EdgeContainer &matching) |
| | Checks in O(|V| + |E|) time if matching is a maximal matching.
|
| |
| template<typename EdgeContainer > |
| bool | isPerfect (const Graph &graph, const EdgeContainer &matching) |
| | Checks in O(1) if matching (assuming it is a matching and the graph is simple and connected) is perfect.
|
| |
| template<typename EdgeContainer > |
| bool | isPerfectMatching (const Graph &graph, const EdgeContainer &matching) |
| | Checks in O(|V| + size of matching) if matching is a perfect matching.
|
| |
Simple algorithms for matchings.
