기능을 구현하는 동안 노드의 제거는이 문제에

Question

그래서 내가 도망을 가입 한 후 나머지 서브 그래프를 결정

한다고 가정 내가 서로 연결되어 일부 노드의 임의의, 무향 그래프가 있습니다.

어떤 경로를 따라 서로에게 도달 할 수있는 모든 노드 그룹을 하나의 집합이라고 부릅시다.

이제 그래프에 하나의 집합 만 포함되어 있다고 가정합니다. 즉, 모든 노드는 다른 모든 노드에서 연결할 수 있습니다.

임의의 노드 A를 가져 와서 세트에서 제거하면 어떤 세트가 남아 있는지 신속하고 효율적으로 결정해야합니다. A가 집합의 컷 포인트 일 경우 집합을 두 개 이상의 작은 집합으로 분할해야합니다. 다른 노드에 연결 새 모서리의 수와 새로운 노드 B를 추가, 집합에서 제거하고 나머지 세트를 결정

• 및
• : 단순히 효율적이 일을하는 방법이 필요합니다.

두 가지 작업을 적당히 빠르게 수행 할 수 있어야합니다. 본질적으로 O (log (n)) 또는 O (1) 솔루션을 찾고 있습니다. 이 그래프는 클 수 있으므로 O (n) 해를 사용할 수 없습니다. 나는 특히 메모리 오버 헤드에 관심이 없다. 누구든지 올바른 방향으로 데이터 구조/알고리즘을 사용하여 여기에 사용할 수 있습니까? 나는 Union-Find와 Djikstra 같은 것을 이미 생각해 왔지만, 그들은 나의 필요에 부합하지 않는다. 노드가 추가되거나 제거 될 때마다 전체 그래프에서 전체 연결 확인을 실행하고 싶지 않습니다.

Answer 1

매우 좋은 paper by Henzinger and King가 있습니다. 나는 그것이 당신의 질문에 직접적으로 대답한다고 생각합니다.

이 방법은 에지 삭제 (정점 삭제는 모든 에지를 삭제하는 것과 동일 함) 및 O (log (n)/loglog (n)) 최악의 경우에 O (log^3 쿼리 당 케이스 복잡성 (동일한 연결된 구성 요소에서 v 및 u)

또한,이 문제의 많은 변형 예가 제시되어있다. 삭제 만 허용되는 경우 더 빨리 수행 할 수 있습니다.