LP&CO 2026 Lecture-28
Nishad-Kothari-IIT-Madras · 48:29 · Watch on YouTube
이 강의는 s–t 최단 경로 문제를 위한 쌍대 알고리즘(primal-dual algorithm)을 구축합니다. 여집합 완화(Complementary slackness, CS) 조건이 모든 단계를 안내합니다. 모두 영인 쌍대(dual)에서 시작하여, 알고리즘은 t가 도달 가능할 때까지 "타이트 그래프(tight graph)"에서 s를 포함하는 성분 주위의 컷의 레이블을 반복적으로 올립니다...