Gallai–Edmonds decomposition
GPTKB entity
Statements (24)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
graph
|
| gptkbp:appliesTo |
finite undirected graphs
|
| gptkbp:citation |
Edmonds, J. (1965). Paths, trees, and flowers. Canadian Journal of Mathematics.
Gallai, T. (1965). Kritische Graphen. I. Magyar Tud. Akad. Mat. Kutató Int. Közl. |
| gptkbp:describes |
partition of vertices
|
| gptkbp:field |
graph theory
|
| gptkbp:hasApplication |
gptkb:algorithmic_graph_theory
combinatorics matching algorithms |
| https://www.w3.org/2000/01/rdf-schema#label |
Gallai–Edmonds decomposition
|
| gptkbp:introducedIn |
1965
|
| gptkbp:namedAfter |
gptkb:Jack_Edmonds
gptkb:Tibor_Gallai |
| gptkbp:partitionClasses |
A
C D |
| gptkbp:partitionType |
Dulmage–Mendelsohn decomposition
|
| gptkbp:relatedTo |
matching theory
vertex cover maximum matching factor-critical graph |
| gptkbp:usedFor |
analyzing maximum matchings
|
| gptkbp:bfsParent |
gptkb:Gabor_Gallai
|
| gptkbp:bfsLayer |
8
|