ѧ
JOURNAL OF SOFTWARE
1999 1 No.1 1999



ͼı߼ƥ䲢㷨Ӧ
Ҽһۡǫƽ
ժҪEREW PRAM(exclusive-read and exclusive-write parallel random access machine)мģ,ԷΧܹһͼı߼ƥ,ʱ临ΪO(logn),ʹO((n+m)/logn)ѡٲ㷨.
ؼʡͼ㷨,߼ƥ.
ͼšTP301
A Parallel Maximal Matching Algorithm for Undirected Graphs with Applications
MA Jun1 IWAMA Kazuo2 GU Qian-ping3
Abstract A fast and optimal parallel maximal matching algorithm is proposed for a class of graphs. It runs in O(logn) time with O((m+n)/logn) processors on a EREW PRAM (exclusive-read and exclusive-write parallel random access machine).
Key wordsParallel graph algorithms, maximal matching.
G(V,E)Ϊͼ,V={1,2,...,n}ΪGĶ㼯,ԡV,Աʾ.EΪGı߼,n=|V|,m=|E|.ӼMEΪGıƥ,e1,e2M,e1e2޹ͬ.MGκαƥ,MΪGļƥMM(maximal matching).MMĲ㷨ѳΪӦⲢĻ㷨.1,2Ŀǰ,EREW PRAM(exclusive-read and exclusive-write parallel random access machine)Ĳмģ,MMķõ㷨ΪʹO(n+m),ʱ临ΪO(log4n)Ĳ㷨.2ݱ,ڷΧܹһͼ,MM²㷨,㷨㲽ȴǰ㷨ڸͼϼO(logn),Ϊڸͼϵ㷨.
1
߼E=F1...Fk,FiΪɭҵij,FiFj=.ı߷ָ,ɭkķָΪGĲü(Arboricity).ɭĿΪa(G).覰={G|GΪͼa(G)=(1)},֪ƽͼ(Genus)ͼ󶥵ͼ.3,4AV,(A)={x|(x,)E,ԡAxA}Ϊ㼯ATi=(Vi,Ei,ri)ΪGһ,ViV,EiE,riΪTiĸ.depth()ΪԵri·ϵı.depth(ri)=0.FΪGһ,FGk(>1)T1...Tk,㣺 E(Ti)E(Tj)=,ij; V(T1)...V(Tk)=V(G).FһάF(1..n)ʾ,F(i)=j,ҽTk,jΪiĸ.F(ri)=ri.
1. 5ݡW(n)ΪPRAMģ,ڣ(1)ʱڿɲɵĲ,p̨PRAM,W(n)ڣ(W(n)/p)ʱڱp̨.
2ƥĸЧ㷨
㷨. Matching
: ͼGڽӾ.
: GһƥM.
(1) i:=1;G1:=G;M:=;ԡV,㶥degree(v).
(2.1) Gi=,򷵻;
(2.2) ùForest,GiһF1i.
(2.3) ԡV(Ti),TiF1i,root(),root()ΪTiĸ.ÿһ(,w)Ti,û,w,w,ԡ,TiΪŷͼCi,ͨCiroot()е͵Tiÿ.5ȻCiԭΪTi.
(2.4) ùF-Matching,ҳF1iһƥM1i.
(2.5) ͼGi(V,E),E={(,w)|(,w)E(Gi),F1iroot()root(w)Ҧ,wV(Mi)}.
(2.6) ùForest,GiһF2i.
(2.7) ùF-Matching,ҳF2iһƥM2i.
(2.8) Mi:=M1iM2i.
(2.9) ɾGiһ˵V(Mi)ı߼.ƲͼΪGi+1;M:=MMi; goto (2.1).
end Matching.
Procedure Forest
 : ͼGiڽӾ.
: F(1..n)ʾGiFi.
(0) ÿԡGi,F()=;
(1) 覣i()={x|(x,)E(Gi)ΪGiе};wΪi()о󶥵Ķ,degree(w)degree(),F()=w;
(2) for ԡʦ(Gi) par-do if F(F())= and (w<) then F()=; endif; endfor;
(3) if F()= then ѡ wʦi(),F()=w; endif;
end Forest.
Procedure F-Matching
: F(1..n)ʾFi.
: FiһƥMi.
Local array B(1..n,1..2) of integer;
Sub-Procedure Sort_Matching
(1) Bֵ򲢴浽B
(2) For all i,2in par-do if B(i,1)=B(i-1,1) then B(i,1):=;
(3) For all i,1in par-do
if B(i,1)١ then {(B(i,1),B(i,2))Mi;ǶB(i,1)B(i,2)ΪMiĶ};endif;
end Sort_Matching;
Sub-Procedure Match(x)
if x=0 then
for 1in par-do
if (F(i)=i) or (depth(i)Ϊż) then B(i,1):=
else {B(i,1):=F(i); B(i,2):=i;}; endif;
ù Sort_Matching; endfor;
else for 1in par-do
if (F(i)=i) or (depth(i)Ϊ) or (iF(i)ΪMiĶ) then
B(i,1):= else {B(i,1):=F(i); B(i,2):=i;} endif;
ù Sort_Matching; endfor;
end Match(x);
/steps of algorithm F-Matching/
(1) for each ԡV(Gi) and ԡV(Tj) par-do
depth(),depth()ΪTjFi;ǦΪMiĶ. endfor;
(2) for x=0 to 1 do ùMatch(x);
end F-Matching.
ͼ1㷨Matchingһִйͼ.

3㷨Matching۷
㷨Matchingĵ2ѭĵiִΪ׶i.Ȼ.
3.1. MEΪG(V,E)һƥ,ҽMΪһƥ,Gеı,һ˵M.
3.2. F1i(F2i)ΪGi(Gi)и.
֤Ȼ,ڹForestĲ(1)(2),GiĶӵF1i.(2)ɾܵĳΪĻ·,<ϵΪԷǶԳƺʹݵ.˹̽,F1i޻·.֤ͬF2iΪGiи.
3.3. M1i(M2i)ΪF1i(F2i)ϵļƥ.
֤ڹF-MatchingĲ(2)(3),F1iеÿe=,F(v,F(v)ͼΪM1i)ͼΪM1iı,eδܳΪM1iı,ҽeһ˵V(M1i).3.1,֤.֤ͬM2iΪF2iļƥ.
㷨MatchingĲ(2.9),ɵõ3.1.
3.1. ڽ׶i,F1i,F2iı߽ɾ.
Gie=(,w),,wV(Mi),eGi+1,eڽ׶iGiɾ,һ˵V(Mi).3.13.3,ֱƳ3.1.
3.1. M=iMiΪGһƥ.
3.4. EREW PRAMмģ,㷨Matchingÿ׶ε,O(logn)ʱڱO((m+n)/logn).
֤:֪nԪdepth()root()ŷ·ļ,O(logn)ʱڱO((m+n)/logn)ɣ5,ĹO(n+m),ɶ1.1,֤.
3.5. GiΪͨͼ,SiΪڽ׶iɾı߼,ֻSiеı,ԽGiһ.
֤Mi:=M1iM2ieE(Gi),ڽ׶i,eɾҽeһ˵V(Mi).Si=S1S2,eS1(S2),ҽeһ˵V(M1i)(V(M2i)).Fi=F1iF2i,k(1),Ȼ,E(F1i)E(F2i)=.k֤.
(1) k=1,Fi=F1i,ΪGi.S2=..k=2,㷨Matchingĵ(2.5)(2.6)ִп֪,E(Gi)={(,w)|,wֱΪT1T2Ķ,Ҧ,wV(Mi)}.S2٧,E(Gi)٧,ڱeS2,ʹT1T2{e}ΪGiһ.Ƶ,Ƴk=3ʱҲ.
(2) kt(t>2),֤k=t+1ʱҲ.
Ȼ,TxTy֮ޱS2,ɹɼ,ͼGi-TxGi-Ty.ڹ Forestִ,e󶥵<3,eΪ,֪Gi-TxGi-TyGiоΪ(һΪ,ɹɼ,),شڦԡTxwTy,䶥Giо2,Giһvw·P,Pı߾Ϊ.ҲΪ.ɹɷԭ,֤.
3.2. 㷨MatchingĽ׶һa(G).
֤Gɰ·ֽΪF1,F2,...,Fa(G):ÿGi֧ͨCl.ҳһTl,Fi:=Tl; Gi+1:=Gi-Fi;ظ˹ֱGi=.
Ai,BiֱΪ㷨㷨Matchingĵiɾı߼,4.5,AiBi,1ia(G),㷨MatchingĽ׶ᳬa(G).
3.3С.
3.3. 㷨Matchingڣ((n+m)/logn)CREW(concurrent-read and exclusive-write) PRAMģ,ڣ(a(G)logn)ʱ.
4ＰӦ
ɶ3.3ͼϦĶ,ͼGʦ,㷨MatchingھУ((n+m)/logn)EREW PRAMмģϵʱΪ(logn).Ȼ(m)ΪMMʱ½,ǵ㷨ΪϦϵѲ㷨.ط֪MMõĲ㷨2,69ƽͼϵִ,Щ㷨ִʱΪO(log2n).ǵĲ㷨ڼϦΪ㷨.Ʋ,ʹöʽǰ,EREW PRAMϲڱȣ(logn)ĶMMĲ㷨.
ף1иһGļ󶥵㲻·MVDP(maximal vertex disjointed path)Ĳ㷨,CREW PRAMϵִʱΪ(log4n),log4nΪмMMʱ.ȻGʦ,Ӧǵ㷨ʹMVDPļʱٵ(logn).µMVDP㷨ֿɸĽڼϦ϶Ĳʱ䣺01ҵȡͼ͹ܶٻ·.1
оõȻѧ𡢹863߿ƼĿɽʡȻѧɽѧ˲Ż.
߽ܣ,1956,ʿ,,ҪоΪ㷨,˹.
Ҽһ,1951,ʿ,,ʿʦ,ҪоΪ㷨,˹.
ǫƽ,1956,ʿ,,ҪоΪ㷨,˹.
ͨѶϵ:,250100,ɽѧѧϵ
ߵλɽѧѧϵϡ250100
Ҽһۡѧѧϵձ
ǫƽѧϵձ
E-mail: majun@sdu.edu.cn
ο
1Goldberg A V, Plotkin S A. Sublineartime parallel algorithms for matching and related problems. Journal of Algorithms, 1993,14:180213
2Iseaeli A, Shiloach Y. An improved parallel algorithm for maximal matching. Information Processing Letters, 1986,22:5760
3Chiba Norishige, Nishizeki Takao. Arboricity and subgraph listing algorithms. SIAM (Society for Industrial and Applied Mathematics) Journal of Computers, 1988,14(1):210223
4Harary F. Graph Theory, Revised. Reading, MA: Addison-Wesley Publishing Company, 1972. 35130
5Jaja J. An introduction to parallel algorithms. Reading, MA: Addison-Wesley Publishing Company, 1992. 120230
6Chen Z. A fast and efficient NC algorithm for maximal matching. Information Processing Letters, 1995,55:303307
7Han Y. An improvement on parallel computation of a maximal matching. Information Processing Letters, 1995,56:343348
8Iseaeli A, Itai A. A fast and simple randomized parallel algorithm for maximal matching. Information Processing Letters, 1986,22:7780
9Kelsen P. An optimal parallel algorithm for maximal matching. Information Processing Letters, 1994,55:223228
1997-03-27յԭ,1998-01-05յ޸ĸ
