ART

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 Texts in Mathematics

Graduate Studies in Mathematics

Mathematics Encyclopedia

World

Index

Hellenica World - Scientific Library

Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License