In graph theory, the Gallai–Edmonds decomposition is a partition of the vertices of a graph into subsets satisfying certain properties. It is a generalization of Dulmage–Mendelsohn decomposition from bipartite graphs to general graphs.[1]
It was proved independently by Tibor Gallai and Jack Edmonds.
It can be found using the blossom algorithm.
An extension of the Gallai–Edmonds decomposition theorem to multi-edge matchings is given in Katarzyna Paluch's "Capacitated Rank-Maximal Matchings".[2]
References
Szabó, Jácint; Loebl, Martin; Janata, Marek (14 February 2005). "The Edmonds–Gallai Decomposition for the k-Piece Packing Problem". The Electronic Journal of Combinatorics. 12. doi:10.37236/1905. S2CID 11992200.
Paluch, Katarzyna (22 May 2013). Capacitated Rank-Maximal Matchings. Algorithms and Complexity. Lecture Notes in Computer Science. 7878. Springer, Berlin, Heidelberg. pp. 324–335. doi:10.1007/978-3-642-38233-8_27. ISBN 978-3-642-38232-1.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
