Statements (52)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
graph
|
| gptkbp:application |
gptkb:stable_marriage_problem
resource allocation scheduling assignment problem network flows |
| gptkbp:complexity |
finding a maximum matching is polynomial time
finding a perfect matching is polynomial time finding a maximum weighted matching is polynomial time |
| gptkbp:defines |
a set of edges without common vertices in a graph
|
| gptkbp:field |
gptkb:mathematics
graph theory |
| gptkbp:hasType |
bipartite matching
maximum matching stable matching perfect matching maximal matching minimum maximal matching near-perfect matching weighted matching |
| https://www.w3.org/2000/01/rdf-schema#label |
matching (graph theory)
|
| gptkbp:namedFor |
gptkb:Philip_Hall
|
| gptkbp:property |
no two edges share a vertex
|
| gptkbp:relatedConcept |
gptkb:factor_(graph_theory)
edge coloring independent set vertex cover matroid |
| gptkbp:relatedTo |
graph
edge vertex |
| gptkbp:subclassOf |
independent edge set
|
| gptkbp:supportsAlgorithm |
gptkb:Hopcroft–Karp_algorithm
gptkb:Edmonds'_blossom_algorithm gptkb:Hungarian_algorithm |
| gptkbp:theory |
gptkb:Hall's_marriage_theorem
gptkb:König's_theorem gptkb:Berge's_lemma gptkb:Tutte's_theorem gptkb:Gallai's_theorem |
| gptkbp:type |
edge set
|
| gptkbp:usedIn |
biology
chemistry combinatorial optimization economics operations research social sciences theoretical computer science |
| gptkbp:bfsParent |
gptkb:3-Dimensional_Matching
gptkb:matching_polytope gptkb:Edmonds'_matching_polytope |
| gptkbp:bfsLayer |
7
|