| 词条 | 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] References1. ^{{cite journal |last1=Szabó |first1=Jácint |last2=Loebl |first2=Martin |last3=Janata |first3=Marek |title=The Edmonds–Gallai Decomposition for the k-Piece Packing Problem |journal=The Electronic Journal of Combinatorics |date=14 February 2005 |volume=12 |url=https://pdfs.semanticscholar.org/f1bf/38b09e05dcced7a2ed8e25a2b7b1911e859e.pdf |accessdate=23 January 2019 |language=en}} 2. ^{{Cite book|last=Paluch|first=Katarzyna|date=22 May 2013|title=Capacitated Rank-Maximal Matchings|journal=Algorithms and Complexity|volume=7878|language=en|publisher=Springer, Berlin, Heidelberg|pages=324–335|doi=10.1007/978-3-642-38233-8_27|series=Lecture Notes in Computer Science|isbn=978-3-642-38232-1}} {{Math-stub}} 2 : Graph algorithms|Matching |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。