유향 그래프에서 모든 가능한 경로 중에서 공통 경로 찾기

Question

순환 방향 그래프의 각 가능한 모든 경로에서 항상 방문하는 공통 노드를 찾으려고합니다. 내 생각은 가능한 모든 경로를 계산 한 다음 공통 요소를 검색하는 것입니다. 그러나 a)은 매우 효율적으로 보이지 않으며 b)주기를 고려하지 않습니다.

목표 : 변경 방지 방법으로 oblivious hashing perimeter을 구현하는 것입니다. 이를 위해 제어 흐름 그래프에서 입력 불가 인 공통 기본 블록 세트를 식별해야합니다. 다른 말로하면, 주어진 입력에 대해 실행될 프로그램의 결정적 덩어리 (기본 블록 세트)를 찾고 싶습니다.

Answer 1

원하는 작업을 수행하려면 경로의 시작 정점과 끝 정점을 제공해야합니다. 그래서 문은 다음과 같습니다

그런 다음 당신이 정점 당신이 찾고있는 것을 볼 수 E.

세트의 모든 정점 집합 S의 모든 정점에서

을 통과 할 때 항상 전달되는 모든 정점을 찾기 for는 Vertex Separators입니다. 알고리즘은 최소 정점 분리자를 계산하기 위해 존재합니다.