최근에 우연히 찾은 자료..



minimum path cover 문제를 max flow를 응용하여 풀 수 있다고 한다..~
문제에 대한 정의와 증명과 결론은 첨부파일에 자세히 나와있다..
뭐 다 외계어로 써있다는게 좀 아쉽긴 하지만..

어쨋든..
bipartite graph에서 minimum vertex cover = maximum bipartite matching
이란 사실을 안 이후에 또 하나의 충격적인 발견이다..~ ㅎㅎ
max flow가 응용될수 있는 문제가 정말 많구만..~

관련문제로 LA 3126 - Taxi Cab Scheme 이 있다..~


'Problem Solving > Algorithm notes' 카테고리의 다른 글

Primality Testing (Miller-Rabin)  (0) 2010.03.23
Modular Exponentiation (Big Mod)  (2) 2010.02.19
KMP (Knuth-Morris-Pratt) Algorithm  (0) 2009.11.15
Sorting Algorithm O(n^2)  (0) 2009.08.31
Bell Number  (0) 2009.07.12
Finding Minimum Path Cover in DAG  (0) 2009.06.15
Plane Equation (평면의 방정식)  (0) 2009.04.16
Ellipse (타원)  (0) 2009.04.15
Modular Arithmetic 1탄 - Extended Euclid  (2) 2009.02.22
Combination 개수 구하기 (Pascal's Triangle)  (2) 2009.02.07
Josephus Problem  (2) 2009.01.01

Leave a Comment


to Top