갈라이-에드몬드 분해

Gallai–Edmonds decomposition

그래프 이론에서, Galai-Edmonds 분해는 그래프의 정점을 특정 특성을 만족하는 하위 집합으로 분할하는 것이다.그것은 초당적 그래프에서 일반 그래프로의 덜마게-멘델손 분해를 일반화한 것이다.[1]

그것은 티보르 갈라이와 잭 에드몬드에 의해 독립적으로 증명되었다.

그것은 꽃 알고리즘을 사용하여 찾을 수 있다.

갈라이-에드몬드 분해 정리의 연장선은 카타지나 팔루치의 "Capaced Lank-Maximal Matchings"[2]에 제시되어 있다.

참조

  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. Vol. 7878. Springer, Berlin, Heidelberg. pp. 324–335. doi:10.1007/978-3-642-38233-8_27. ISBN 978-3-642-38232-1.


Stub icon

이 수학 관련 논문은 단조롭다.위키피디아를 확장하여 도울 수 있다.