Gallai–Edmonds decomposition

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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] 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.

[2] 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.