설명한 문제는 완전 동적 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

$m$

$m$n

$n$

$n$n1.58

$n^{1.58}$

$n^{1.58}$n0.58

$n^{0.58}$

$n^{0.58}$mn+I⋅n2+D

$mn+I·n^2+D$

$mn+I·n^2+D$ 삽입 횟수, D 는 삭제 횟수이며 물론 쿼리 시간은 O ( 1 )입니다.I

$I$

$I$D

$D$

$D$1

$1$

$1$

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

$n^2$

$n^2$ ),O( √mn−−√

$m\sqrt{n}$

$m\sqrt{n}$ )) (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−−√

$O(\sqrt{n}$

$O(\sqrt{n}$m+nlogn

$m+n\log n$

$m+n\log n$n

$n$

$n$n1.58

$n^{1.58}$

$n^{1.58}$n0.58

$n^{0.58}$

$n^{0.58}$n1.495

$n^{1.495}$

$n^{1.495}$n1.495

$n^{1.495}$

$n^{1.495}$

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

---

답변