최대 중량 일치

컴퓨터 과학에서 최대 무게 일치 문제는 가중 그래프에서 가중치의 합이 최대화된 일치점을 찾는 문제다.

특별한 경우는 할당 문제인데, 입력은 초당적 그래프로 제한되고 일치는 두 칸막이 중 작은 칸막이의 카디널리티로 제한된다.또 다른 특별한 경우는 가중치가 없는 그래프에서 일치하는 최대 카디널리티를 찾는 문제인데, 이는 모든 가장자리 무게가 동일한 경우에 해당한다.

알고리즘

초당적이지 않은 그래프에서 최대 일치 또는 최대 중량 일치를 찾는 $O{\displaystyle ({}^{}}$ )${\displaystyle O(V^{2}E)$ 시간$$ 알고리즘이 있다. 잭 에드먼즈 때문이며, 경로, 나무, 꽃 방법 또는 단순히 에드먼드의 알고리즘으로 불리며, 양방향 에지를 사용한다.동일한 기법의 일반화는 또한 발톱이 없는 그래프에서 최대 독립 집합을 찾는 데 사용될 수 있다.

보다 정교한 알고리즘이 존재하며 듀안과 페티가^[1] 검토한다(표 III 참조).이들의 작업은 최대 중량 일치 문제에 대한 근사 알고리즘을 제안하며, 이 알고리즘은 고정 오류 바인딩에 대해 선형 시간으로 실행된다.

참조