함축 그래프 할당

의미 그래프는 각 노드가 참 또는 거짓으로 지정된 방향 그래프이며 u -> v 모서리는 if u is true then v is true을 의미합니다. 함축 그래프 할당

이 나는 일반적인 의미 그래프의 할당 및 (A 2 SAT 문제에서 발생하는 의미 그래프와 같은) 특별한 경우에 대한 O(n) 알고리즘을 찾기 위해 간단한 O(n^2) 알고리즘을 알고있다.

O(n) 알고리즘이 암시 적 그래프 할당을 찾았습니까?

2014-09-20 Corei13

할당에 대한 요구 사항을 지정하지 않았습니다. – piotrekg2

2-SAT 문제와 동등하지 않은 암시 그래프의 간단한 예를 들려 줄 수 있습니까? (나는 모든 암시 그래프가 2-SAT와 같다고 생각했고 Tarjan의 강하게 연결된 구성 요소 알고리즘에 의해 O (n)에서 모두 풀 수있다.) –

@ piotrekg2, 각 모서리는 요구 사항을 지정한다. 노드 u에서 노드 v까지의 가장자리는 u가 true로 지정되면 v가 true 여야 함을 의미합니다. – Corei13

암시 그래프의 할당은 Tarjan strongly connected components 방법을 사용하여 찾을 수 있습니다.이 방법은 2-SAT 인스턴스의 변환을 통해 생성 된 그래프뿐만 아니라 모든 암시 그래프에 적용 할 수 있기 때문에 찾을 수 있습니다. 이 방법은 적은 수의 그래프 변환 단계로 구성되며, 모든 단계에서 입력 크기에 선형적인 시간이 필요합니다. 따라서 알고리즘은 전체적으로 O (n) 런타임이 필요합니다.

출처

2014-09-21 00:33:27

답변

관련 문제