삽입 / 삭제가있는 경우 DAG에 대한 연결 정보를 효율적으로 유지 관리하는 알고리즘이 있습니까? 다음 작업을 효율적으로

방향성 비순환 그래프 가 주어지면 다음 작업을 효율적으로 지원할 수 있습니까?

G(V,E)
  • :를 결정은의 경로가있는 경우 G 노드로부터노드
    isConnected(G,a,b)

    G

    a

    b

  • : 선택된 행 에지에 B 그래프 G
    link(G,a,b)

    a

    b

    G

  • : 에지로부터 제거 을 에 B 의 G
    unlink(G,a,b)

    a

    b

    G

  • : G에 꼭짓점을 추가합니다
    add(G,a)

  • : G에서 꼭짓점을 제거합니다
    remove(G,a)

몇 가지 참고 사항 :

  • 만약 우리가 허용하지 않는다면 , 분리 세트 타입의 데이터 구조를 사용하여 연결 정보를 유지하는 것이 쉬운 것처럼 보일 것입니다.
    unlink

  • 물론, 그래프의 순 포인터 기반의 표현을 사용하여, 깊이 또는 너비 우선 탐색을 사용하여 구현 될 수있다. 그러나 이것은 비효율적입니다.
    isConnected

세 작업 모두에 대해 상각 된 상수 또는 로그 시간을 원합니다. 이게 가능해?

답변

설명한 문제는 완전 동적 DAG 도달 가능성 (DAG에서 완전 동적 전이 폐쇄라고도 함)입니다. 사람들은 삭제 만 가능한 버전 (감소 적 도달 가능성이라고 함)과 삽입 만 가능한 버전 (증분 적 도달 가능성이라고 함)을 연구하기 때문에 완전 동적이라고합니다.

업데이트 시간과 쿼리 시간 사이에는 몇 가지 장단점이 있습니다. 하자 모서리의 수와 수 n은 정점의 수. DAG의 경우 Demetrescu 및 Italiano (FOCS’00)는 O ( n 1.58 ) 시간의 업데이트 (가장자리 삽입 또는 삭제) 및 O ( n 0.58 ) 시간의 도달 가능성 쿼리 (노드 삽입 / 삭제도 지원 )를 지원하는 무작위 데이터 구조를 제공했습니다. O (1) 시간); 이 결과는 Sankowski (FOCS’04)에 의해 일반 방향 그래프로 확장되었습니다. 또한 DAG의 경우 Roditty (SODA’03)는 전이 폐쇄 매트릭스를 총 시간 O ( m n + I · n 2 + D )로 유지할 수 있음을 보여주었습니다 .

m

n

n1.58

n0.58

mn+I·n2+D

삽입 횟수, D 는 삭제 횟수이며 물론 쿼리 시간은 O ( 1 )입니다.

I

D

1

일반 유향 그래프를 들어, 다음의 (갱신 쿼리) 시간이 공지되어있다 (O ( ), O (1)) (Demetrescu 및 한국어 FOCS’00은 (상각) Sankowski FOCS’04 (최악의 경우)) ( O ( m √

n2

),O( √

mn

)) (Roditty, Zwick FOCS’02), (O (m+nlogn), O (n)) (Roditty, Zwick STOC’04), (O (n 1.58 ), O (n 0.58 )) 및Sankoowski (FOCS’04)에 의해(O (n 1.495 ), O (n 1.495 )).

O(n

m+nlog⁡n

n

n1.58

n0.58

n1.495

n1.495

업데이트 시간을 너무 많이 늘리지 않고 다항식 쿼리 시간을 얻는 것은 DAG의 경우에도 주요 문제입니다.

답변

지금까지 최고의 결과는 “완전 동적 전이 폐쇄를위한 동적 매트릭스 관리” 에서 논의되고 있다고 생각합니다 . 이 백서에서는 쿼리 시간과 O ( n 1.58 ) 업데이트 시간이 있는 무작위 알고리즘에 대해 설명합니다 .

O(n0.58)

O(n1.58)

(이것은 단지와 함께, 귀하의 질문의 첫 번째 버전을 포함 link하고 unlink있지만없이 add하고 remove.)

답변