当前位置:首页 >> 学科竞赛 >>

动态图 Several Techniques for Maintaining Fully Dynamic Graphs


Several Techniques for Maintaining Fully Dynamic Graphs
M×? <xuyinzhan@gmail.com>
??? ??

February 11, 2015

Dynamic Graphs

Fully Dynamic Graph

s: 3?§kí>?\>??" Techniques: Sampling Clustering and Topology Tree Sparsi?cation O?ine Techniques

Dynamic Graph Connectivity

í>\>§??ü?:??5" Partially dynamic??|±\>¤?‘o??? 8§?? ? ?u ü:??3???8?p=?"

Level

‰z^>? ??0 log n?m ?",^> ?mO\ ~ " -Gi ?d ? u ui > ¤ f?§Fi ?Gi ¤? "

???‘X ??4?)

Invariant

Gi

??é????k2i ?!:"

F0 ? F1 ? . . . ? Flog n §=Fi = Flog n ∩ Gi §…Flog n ?± ? ?> Glog n ? )¤? " ??§éz??Gi ‘o?? ??¤" ? ?é??z?:?á???

Connected

??u ?v ??é?" ?3Flog n ?u ?v ??áu????" O (log n).

Insert

\?^>e = (u , v )" kòe ? ??log n§2 \ #Flog n ?Glog n ? " O (log n).

Glog n ?§??

Delete

òe = (u , v )l??í " kòe l ? ?í " ee ?3Flog n ?§K ?? ??5?C§dg??(?"? K?

Delete

·??é ?^e O?>"5?ù^> ?7,?u ue " 3éO?> ???I?÷v??¤? ü^5?" ?gllevel (e ) log n?éù^O?>"

Delete
??31i ?éO?>" ?"?”??5/§

1. -Tu ???u ?§Tv ???v -|Tv | ≤ |Tu |.

2. du 5Tu ?Tv ?3???é??§?d|Tu | + |Tv | ≤ 2i § ¤±|Tv | ≤ 2i ?1 " rTv \ 1i ? 1? ??vké??? §?? §¤±?±rTv ?? 1i ? ?" 3. éu??31i >(x , y )§…x 3Tv ??
ey 3Tu §Kr(x , y )\\ Fi , Fi +1 , . . . , Flog n ?§?(?ù ???" ?Kò(x , y ) ???i ? 1.

Details

^??ê? ?ê?( ?U ¤éF ??" z?^>??? eKlog n §zg??E,??log n§¤±? E,??O (log2 n)

Clustering and Topology Tree

±? ? )¤??~" \>!í>!?U> §‘o?

)¤?

Transformation

?L=z§?z?: ?ê u u3 ò?? ?ê?n :v § ¤v0 , v1 , . . . , vn?1 "3vi ?vi +1 ?m? > ?∞ >"e ??k?^>(u , v )§KòéA ux , vy ?m ?? > >" ??±dV\??#: ??§ò ?=z?é??" #? :ê?>ê??O (m)§…ü? ? )¤?( ??? "

Simpli?cation

í>?ò?^>> U?+∞ \>(u , v , x )?u ?v ¤ :Lp?#\??:§ùü??m? ?+∞ >"ù???K?MST / "? 2r> U?x " ? ????U> ??"

Algorithm 1

Preprocessing time O (m) Update time O (m 3 ) Space requirement O (m)
2

Topological Partitions

3? )¤??í???>8E §? ?e z?é??:ê? 3z ?3z ? 2?m"z ? ò?3? ??" z??é?? ‰vertex ?§é?? 8? ‰topological partition of order z"

Topological Partitions

?? )¤?? ??“f???§?1dfs " XJ??f? ? ?u uz §?rù?f?????vertex ???KUY48" ? ???é?3z ?3z ? 2?m 8?§±9??:ê?U uz 8???¤3 8?¤"XJ uz §@o?rù?8?? ?? ??8???" ù? E?O (m) "

Topological Partitions

Lemma
d??L§/¤ é??? 3z 3z ? 2?m"

Proof.
)¤??z?: ?ê???3§ ? ?ê?1§?dz?:? ??kü??f? ?¤" ? ? @?A? é??§O é?????d??:?ù? :ü??f é?? ¤§???1 + 2(z ? 1) = 2z ? 1 ? /¤ é?????(2z ? 1) + (z ? 1) = 3z ? 2

Maintain the Key Information

???é üü? Vi , Vj ?m ? >Eij §?e5" ??ê?O ( m z) 2 ?mE,??O (m + ( m z) )

Update Operations

1. O\??> 2. ~ ??> 3. ~ ??> 4. O\??>

Operation 1

O\??> " éMST ??k??K?"

Operation 2

~ ??> " ??éMST / E¤K?§???U?^MST ‘o"

> §N?

Operation 3

~

?^??>

?§?U?r?^?>O?K"

1. é ù^?> 2. O?K

Find the Edge

?????> LCT? 6?k^ù??{§ ??ù???B ‰{"

Switch the Edge

b ^(u , v )O?(x , y )" XJx , y ?3????§@o? / ???UC mE,??O (z )" ?? ???x , y 3????"

§ù? ?

Split a Cluster

XJx , y 3???? Vi §??r(x , y )íK§?rVi ? ¤ü? ?Vi 1 , Vi 2 ? ?I?‘oVi 1 ?Vi 2 ???¤k??m ? >" ??z?O ( m z) q?¤k?à3V ? >§?#?O (z )"?z?:?ê?? ?3¤"

Merge Two Clusters

? ?ru , v ¤3 ???" ùp??V\?ü??m >=?"

Consider Sizes of Clusters

? ????§ü?# ?? ? uz "ù??r ? ?? ???"?? XJL?§2^dfs ?{? ¤ü? ?" Special Case? ? §,???Uvk? é??"ù ?§?? –ru , v ??=?§2 ??"

Operation 4

O\?^?> >"

?§?U?rù??>íK§\\,????

1. é ù^??> 2. O?K??Operation 3?? ?¤

Find the Edge

í??>(x , y )?r¤k??¤ü?8?" q?¤ki , j §? Vi , Vj 3?O3??8?p"é ? ^Eij " eù^Eij u(x , y ) > §@o?^ù^>O?(x , y ) 2 ?mE,??O (z + ( m z) )

?

Complexity

z = O (m 3 )§K?±? zg???mE,?O (m 3 )§??n ?mE,?O (m)" 2 ?mE,??O (( m z ) + m) = O (m) 2 z >êO\O (m 3 )??\>???,??K?MST § ?S ????>êO\ ¤§?-#?Jz ? E ?( "

2

2

Algorithm 2

Preprocessing time O (m) √ Update time O ( m log m) Space requirement O (m)

External Degree

??? ?ê???k…?k?à3ù??S >ê"

Simply-Connected Topological Partition

??simply-connected topological partition?topological partitionaq§?dO ( m z )?? ?O (z ) ?/¤"????3 u§??simply-connected topological partitionz?? ?ê–? ?3.

Simply-Connected Topological Partition

???topological partition Eaq" ?? )¤?? ??“f???§?1dfs " XJ??f? ? ?u uz §????f? ?ê?3§?r ù?f????????KUY48" e? ?¤3 ??ê??3…:ê uz §K?rù??2?? c/¤ ?????" ù? E?O (m) "

Simply-Connected Topological Partition

Lemma
d??L§¤/¤ é??§?o!:ê3z o!:ê uz …?ê?3" 3z ? 2?m§?

Simply-Connected Topological Partition

Proof.
XJ??f???g/¤?§`?§ ?ê u3…!:ê uz "@o§ù?f?éI??ê z???1§!:ê z? ??z ? 1" @oéuI?¤/¤ ?§?ê???3§!:ê?? ?2z ? 1§??^?" éu? ?¤/¤ ?§e?ê???2§:ê???z ? 1§@ o??? ?ê???3§!:ê???3z ? 2"

Lemma
d??L§ E é???ê?O ( m z )"

Proof.
ò E? é?? ???:§? é???m??^>" ù /¤ ?????ê?3 ?"-?ê?x :kVx ?" ù???§?ê u3 :§??? ??– z ?:§? m dV1 + V2 = O ( z )" V1 + 2V2 + 3V3 = 2(m ? 1) V1 + V2 + V3 = m ?± V1 = V3 + 2§¤±V3 < V1 = O ( m z )§? m m d(V1 + V2 ) + V3 = O ( m ) + O ( ) = O ( ). z z z

Add an Edge

\>??±? ???5ü??" XJ¤k: ?ê??3§@o¤k:?ü?C??? ?= ?" ?Ké ???ê u3 :???dfs E?"

Delete an Edge

í??^>(x , y )§?U??x ?y ¤3 ???{??ê u3… ? uz " ‘ ù???§?Iò§???? ???§? ?2?u?ê u3…? uz G " e??? ??u3z ? 2§KI??^simply-connected topological partition ???{?l"

Topology Trees

Topology trees???ésimply-connected topological partition3z = 2? 48( §=??/?1simply-connected topological partition§?? ???/( " zg?1y? §3? ??m?>§/¤# ?§???1 y?"

Multi-Level Topological Partition

1. éuz??i §1i

?? 5:8 ??y?"

2. 10 ??ü?!:" 3. éu??3?u0 ?§§?±eü????
d31i ? 1 2?3?4??? ¤§…ù?#/¤ ? ?ê??L3" ??3i ? 1 ?§…§ ?ê?3"

Topology Tree

???T

topology tree?

1. S?!:???k4??f§…¤k“f?3?? ?" 2. ??31i !:éA3multi-level topological partition? 1i ?" 3. ??31i > 0 ?" !: ?féAu/¤ù?? @

Depth

Lemma
XJn????T ?O (log n)" !:ê§@oT éA topology tree ?

Depth

Lemma
XJn????T ?O (log n)" !:ê§@oT éA topology tree ?

Proof.
XJ31i :ê?ni "-?ê?j :kVj ?" V1 = V3 + 2`??ê?3 !:??? 1 2 ni §Kni +1 ?? 1 1 3 ?ni ? 2 ( 2 ni ) = 4 ni "

Generation Time

Lemma
??topology tree EE,??O (n) "

Proof.


O
i =0

3 n ( )i 4

= O (4n) = O (n)

Critical Operations

-? ???3? )¤??í??^>§±9O\?^>±? ü?)¤?" ùü???? ·?I?|±???? topology tree.

Di?culty

?U/ J:3utopology treek?ê??"??ü???U ? —? ?ê?u3§? ????U? —!:êL "

Merge

\\?^>? §?? , ù ??W "

? ?êl3C?4"-level?

Lemma
W 7,U?¤ü??ê?{ ?W ?W "

Deal with Degree
Proof.
?????"'X?

Deal with Degree
”ù rW CW , W ? §ò§? I?? ?? W I ?"ù??§W I??UI?? " ? ?I E??W I? topological partition§ù??±^? ?J L ?{" du? W I?q?C???!:§?d?3topology tree? le ??gUC" ?#L ??ê??2k?K"ù?2ée??ù W ?1 ? ??" z?gUC?O (1) § êq?O (log n) §?d?n?ê ?mE,??O (log n).

Merge

òp? $ @?topology tree 2?1±?? ??" o?mE,??O (log n).

? \ ,?? éAp?"

Split

í??^>§????ù^> ??? §ù ? ¤topology tree? ?^??" ù?? ???±3O (log n)?m ¤"

??/

Deal with Degree

? ? §!:?ê?~?O"?d§?{ ???U?,?d ??!:|¤ ?§?êl3C? 2§ù ?7,?3?^ ? ???" -level? ù ??W "-W ??W 3?? §… ?W lca?$ :§7,?3ù ??W ?W ?mk>??" òW ?W ??§?N #/¤ ?§?g ??#" ?#L ??ê??2k?K"ù?2ée??ù W ?1 ? ??" ?d?mE,??O (log m)"

Procedure

kéu ? ? )¤???simply-connected topological partition§2??ù?#? topology tree"

Heaps

é1?gy? z???§‘o??topology tree" ?A¤éA topology tree z??!:x §“L ?A x ¤k “f ? ?" 2 § ?#? E,?C? @ Algorithm 1? ( m z) ? ? m O ( z · log√ m). √ ?d?z = m log m§üg?? E,?? m log m.

Algorithm 3

Preprocessing time O (m) √ Update time O ( m) Space requirement O (m)

The 2-Dimensional Topology Tree

-Vα ?Vβ ?3topology tree??? ü?!:§@o 32-dimensional topology tree??k??IP?Vα × Vβ !:§ L?k?à3Vα ,?à3Vβ @ ??>?> ? >" e??!:?Vα × Vα …Vα 3topology tree?k? fVα1 , Vα2 , . . . , Vαr §@oVα × Vα k? f{Vαi × Vαj |1 ≤ i ≤ j ≤ r }. aq/§Vα × Vβ k?f{Vαi × Vβj |1 ≤ i ≤ rα , 1 ≤ j ≤ rβ }. 2-dimensional topology tree “f“L ?Eij ???J L i ?j ü??m ? >¤"

Maintenance

?Utopology tree??A/K?2-dimensional topology tree" topology tree? Cz??l? ,??!:Vα ?1" 32-dimensional topology tree?§?U ?/XVr × Vβ !:§ ??Vr = Vα ?Vr ?Vα yk"@o? ?U :ê?level?u uVα :ê§ topology tree? o:ê?O ( m z ). qXJ?U2-dimensional topology tree ,?!:§@o§ I ????? ?U§?d‘o2-dimensional topology tree?O ( m z) "

Find the Replacement Edge

¤kù ê?( ??? )????5? ???í?? ) ¤?? ?^>§?é § O?>" í>? §topology tree?C?Tα ?Tβ ?O;?X: 8Vα ?Vβ " ?”??5 §-Tα ? u uTβ §@o?? 32-dimensional topology tree???¤k/XVα × Vr !:= ?" ?mE,??O ( m z)

The End

-z =



m§K?±

√ ??zg?#E,??O ( m) ‰{"

Open Question

???J simply-connected topological partition????? ?O3uz???ê???3"ù?5??§k?oAO^? Q?

Sparsi?cation

Sparsi?cation?Lò ?=z?D??§l ? 5 zg?# ??E,?lf (n, m)C?f (n, O (n)). 3ùpJ n?Sparsi?cation ?{" 1. Basic Sparsi?cation 2. Stable Sparsi?cation 3. Asymmetric Sparsi?cation

Certi?cate

éu??? 5?P ????G §G ??certi?cate??? ?G §? G k5?P …= G k5?P . G ?I??G f?"

Strong Certi?cate

éu??? 5?P ????G §G ??strong certi?cate?? ??G k??:8 ?G §? éu??H §G ∪ H k5?P … = G ∪ H k5?P . G ?H k?? :8§??? >8" G ?I??G f?"

Property

Lemma
35?P e§eG ?G strong certi?cate§G ?G certi?cate§@oG ?G strong certi?cate. strong

Property

Lemma
35?P e§eG ?G strong certi?cate§H ?H strong certi?cate§@oG ∪ H ?G ∪ H strong certi?cate.

Sparse Certi?cates

XJk??~êc §? éu????n??: ?G §?Ué ??:ê??Lcn strong certi?cate§@o@?ù?5 ?P ?sparse certi?cates "

Sparsi?cation Tree

zgò ? :8????/?¤ü??§?48y?"ù ? n /¤?? ? ( §l??l?i !:êk 2 i ?"

Sparsi?cation Tree

^aq??2-dimension topology tree ( §éu??ü??? :8y???? :Vα ?Vβ §·?3>8y???3ù? ME??:Eαβ §§?? ¤k?à3Vα ??à3Vβ >" Eαβ I??Eγδ §??γ ?δ ?O?α?β 3>8y??? I ?" z?!:Eαβ k0?3?α = β ¤?4??f"

Sparsi?cation Tree

@ ?mvk> :8?m E ??? ME "?dí> ? ??U?r, E í?§\> ???U?O\, E " qkz?^>éAuO (log n)?!:§¤±ù?( ?mE, ??O (m log n)"

Lemma
31i ?l0m?¤ Eαβ ¤/¤ ?f? :ê??? 2in ?1 .

Proof.
n Vα ?Vβ ?O???k 2 i ?!:"

Basic Sparsi?cation

^5\?· ?? ?{"

Well Behaved Time Bound

éu???m?.T (n)§e?3~ê0 < c < 1§? T(n 2 ) < cT (n)§??T (n)?well behaved" ???‘???well behaved" éê???O?? …ú ?ê§???well behaved"

Basic Sparsi?cation

ké ???? >8 y??§ù?? ?éA ?? ?" zg?U?^>§??K?ù???O (log n) ?:" éuz?:§??ù?>8 ?f? sparse certi?cates"@ oéu??:§?I?r§ ¤k?f sparse certi?cates?? 52??gsparse certi?cates"? ? sparse certi?cates §2??‰Y"

Time Complexity

e???:ê?n§>ê?m ? sparse certi?catesE,? ?f (n, m)§…f ?well behaved" n ?1i sparse certi?cates?§:ê? 2in ?1 §>ê?O ( 2i )§?d o ?mE,??


O(
i =0

f(

n 2i ?1

, O(

n ))) = O (f (n, O (n))) 2i "

ù

?Ur 5km

E,???m

Sample

? ???5" \>í>§??ü:??3??é???" vk\>í>??§zg?#??dfs ?H"?mE,? ?O (n + m) "

Sparse Certi?cates

ùp sparse certi?cate?? ? ??4?)¤? §??? ??z??é???^??)¤?L?" w,strong?sparse" é ??1>8 y?"

Operation

?U>8 ??§3>8y???l.???g?U"zgò? ?: ¤k f )¤? ? >???5§23ù???5 ???)¤? " 31i §??5 )¤? ??? 2in ?1 "?düg?U?mE, ??


O(
i =0

f(

n 2i ?1

,4

n 2i ?1

)) = O (n)

Stable Sparsi?cation

^5\???k? ?{ ?

??{"

Further Re?nement

-A???C???G §?ê??G strong certi?cates ??? ê" XJA÷vé??G ???e ∈ G §A(G )?A(G ? e )?kO (1)^ >??§?A?stable " ~?A(G ) = G ,·?I?A??sparse "

Stable Sparsi?cation

>8y??? z? §??kO (1)^>UC" I?5? ?§XJù?O (1) = s §@o1i s ^>UC??? 1i ? 1 ks 2 ^>UC§\Oe5?é?" ?ù >?? UC ?í?-E?? Cz¤? kO (1)§?dz? ??í?? v^ ??"

Time Complexity

e ? ?basic sparsi?cationaq§??zg?#??^? ?{‘o@ UC >v "

Sample

Dynamic MSF ù> A?ê=r ?=C? ? ? )¤? " ? ??/`?ù§e??????? ? )¤? ?> ??Uà: i;SüS"

?

Property

Lemma
-T ?G ?? )¤? §e ∈ T " @o?oT ? e ?G )¤? §T ? e + f ?? )¤? " ?

Lemma
XJT ?G MSF§T ?G MSF§@ oT ∪ T MSF?G ∪ G MSF"

Maintain

?U?^>§l. ??g?#" ??z?>88? MSF§? ??¤k?f MSF2??g" ?mE,??


O(
i =0

n 2i ?2

) = O (n 2 )

1

More Insertion

í?? ?-? Asymmetric Sparsi?cation

Di?erent Sparsi?cation Tree

ò??¤O ( m n )?f?§? ¤kf???U? ?kn^>§? ??–?kn^> f?" 2òù f???“!:§ E???§z?S?!:“L ? éA“f ?8"ù??????ùp#?? sparsi?cation tree.

Modi?cation

Insertion ? 3 f??V\?^>§XJL?§?r§? ¤ü?" Deletion í??^>§? 3 f??<?^>§? ù? f??"XJ f???§?r,??f??? f?§r 5ù?íK" 3ù>???z?f?S?X?‘o"üüwK? f??ê§ ?O (log m n ).

Pros and Cons

?y'aq2-dimension topology tree ( ?{ü§~ê? § ?m?O (m). Certi?cates??‘ ?O\ ~ 5 §?do E,???? ??O (log m n ).

Outline

‘o??? \ ??? ?( " XJ?k\>§??I‘où???? ?( ? E,?é `D¤§?P?e\ = >" ?k í> ????#sparsi?cation tree§?r3 L?\ >??" ? \> ??~p"

Help to Improve Space

^basic?stable sparsi?cation?§?r!:? ? ^asymmetric sparsi?cation?"

O( n m )§?

2

Property
Lemma
basic?stable sparsi?cation3ù?( ? ?m?O (m). ¤?

Proof.
basic?stable sparsi?cation 1i !:?ê?O (4i )§1i certi?cates o? ?O (2i × n). 2 2i ×n n n2 3!:? ? n m ?§ 4i = 2i = m .
i

(2j × n) = O (2i × n) = O (m)
j =0

Property

Lemma
d( ?asymmetric sparsi?cation E,??O (f (n)) ?f (m)?sparsi?cation?c‰{ E,?"¤

Property
Proof.

n 3? ?O ( n m )m?§:ê?O ( m )§>ê?O (m)" 2 m2 Uìasymmetric sparsi?cation E,?O?§?f ( n m ) log n2 ?O#Pf ?well behaved§???f ( n 2 ) < cf (n)§? ?0 < c < 1. ??k
m m n2 m2 ) log 2 ) = O (f (n)c log n log ) = O (f (n)) m n n

2

2

O (f (

5?§??em < n§??^?1ù?X `z §¤±3?? @?m ≥ n.

Details

du?mE,?ü? O (m)§?d??nE,??ü? O (m)" 2 3\>í> L§?§O ( n m ) >.?U?Cz"ù??3eZ g??? -? ?ê?( =?"

Dynamic Connectivity Training

Problem A

‘o????? é???ê§U|±\>?í>" 1 ≤ N , M ≤ 300000.

Solution

??

Solution

‘oUí??m? ? ??)¤?"

Problem B

‘o??????x ?ê§U|±\>" 1 ≤ N , M ≤ 100000.

Solution

?

8

Problem C

‰????§zg?n??ù ??? XJO\?|>(1, p1 ), (2, p2 ), ..., (K , pK )§ò?k? x" 1 ≤ N , K ≤ 100000.

Solution

J?"

Problem D

‘o????? x?ê§U|±\>?í>" 1 ≤ N , M ≤ 100000.

Solution

?Problem A? ??"

Problem E

‰????§zg?XJíKc ^>§ù??????é?" 1 ≤ c ≤ 4, 1 ≤ n ≤ 10000, 1 ≤ m ≤ 100000.

Solution

??‰{??A?? "

Solution

, k??‘?z ‰{§?k‘Bé???)¤?§, ?? > ?‘?§?> ??CX§ ??> ? ???" ù f)¤ ??/z?: ¤k >????00? d § ?±^ê?8B{zg K??“f"u??k??(J?éu ??)¤??÷v??ù?5?"

Solution

????>8???4 Ur ??m >8" eù?>8?Ur ??m§Kí ù?>8 ?’?k?? )¤?"éuù?)¤? ??>??‘? "@olù ?? >???eZ^>§????0 V?? 21 w. XJU?m§K???7,?0. ??? ?w ?U…m 8? ? ( V? ?1 1 ? v i =0 (1 ? 2w ?i ).

T HAN K YOU !

References

[1] Feigenbaum J, Kannan S. Dynamic graph algorithms[J]. 2000. [2] Frederickson G N. Data structures for on-line updating of minimum spanning trees, with applications[J]. SIAM Journal on Computing, 1985, 14(4): 781-798. [3] Eppstein D, Galil Z, Italiano G F, et al. Sparsi?cation)a technique for speeding up dynamic graph algorithms[J]. Journal of the ACM (JACM), 1997, 44(5): 669-696.


相关文章:
更多相关标签: