2009/06/15 23:15
최근에 우연히 찾은 자료..
minimum path cover 문제를 max flow를 응용하여 풀 수 있다고 한다..~
문제에 대한 정의와 증명과 결론은 첨부파일에 자세히 나와있다..
뭐 다 외계어로 써있다는게 좀 아쉽긴 하지만..
어쨋든..
bipartite graph에서 minimum vertex cover = maximum bipartite matching
이란 사실을 안 이후에 또 하나의 충격적인 발견이다..~ ㅎㅎ
max flow가 응용될수 있는 문제가 정말 많구만..~
관련문제로 LA 3126 - Taxi Cab Scheme 이 있다..~
ps3-solns.pdfminimum path cover 문제를 max flow를 응용하여 풀 수 있다고 한다..~
문제에 대한 정의와 증명과 결론은 첨부파일에 자세히 나와있다..
뭐 다 외계어로 써있다는게 좀 아쉽긴 하지만..
어쨋든..
bipartite graph에서 minimum vertex cover = maximum bipartite matching
이란 사실을 안 이후에 또 하나의 충격적인 발견이다..~ ㅎㅎ
max flow가 응용될수 있는 문제가 정말 많구만..~
관련문제로 LA 3126 - Taxi Cab Scheme 이 있다..~
'Problem Solving > Algorithm notes' 카테고리의 다른 글
| 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 |
Trackback Address :: http://helloneo.pe.kr/trackback/279
