%!PS-Adobe-2.0 %%Creator: dvips(k) 5.86 Copyright 1999 Radical Eye Software %%Title: sPpr.dvi %%Pages: 8 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%EndComments %DVIPSWebPage: (www.radicaleye.com) %DVIPSCommandLine: dvips -t letter -o sPpr.ps sPpr.dvi %DVIPSParameters: dpi=600, compressed %DVIPSSource: TeX output 2002.10.18:1516 %%BeginProcSet: texc.pro %! /TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S N}B/A{dup}B/TR{translate}N/isls false N/vsize 11 72 mul N/hsize 8.5 72 mul N/landplus90{false}def/@rigin{isls{[0 landplus90{1 -1}{-1 1}ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{ landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[ matrix currentmatrix{A A round sub abs 0.00001 lt{round}if}forall round exch round exch]setmatrix}N/@landscape{/isls true N}B/@manualfeed{ statusdict/manualfeed true put}B/@copies{/#copies X}B/FMat[1 0 0 -1 0 0] N/FBB[0 0 0 0]N/nn 0 N/IEn 0 N/ctr 0 N/df-tail{/nn 8 dict N nn begin /FontType 3 N/FontMatrix fntrx N/FontBBox FBB N string/base X array /BitMaps X/BuildChar{CharBuilder}N/Encoding IEn N end A{/foo setfont}2 array copy cvx N load 0 nn put/ctr 0 N[}B/sf 0 N/df{/sf 1 N/fntrx FMat N df-tail}B/dfs{div/sf X/fntrx[sf 0 0 sf neg 0 0]N df-tail}B/E{pop nn A definefont setfont}B/Cw{Cd A length 5 sub get}B/Ch{Cd A length 4 sub get }B/Cx{128 Cd A length 3 sub get sub}B/Cy{Cd A length 2 sub get 127 sub} B/Cdx{Cd A length 1 sub get}B/Ci{Cd A type/stringtype ne{ctr get/ctr ctr 1 add N}if}B/id 0 N/rw 0 N/rc 0 N/gp 0 N/cp 0 N/G 0 N/CharBuilder{save 3 1 roll S A/base get 2 index get S/BitMaps get S get/Cd X pop/ctr 0 N Cdx 0 Cx Cy Ch sub Cx Cw add Cy setcachedevice Cw Ch true[1 0 0 -1 -.1 Cx sub Cy .1 sub]/id Ci N/rw Cw 7 add 8 idiv string N/rc 0 N/gp 0 N/cp 0 N{ rc 0 ne{rc 1 sub/rc X rw}{G}ifelse}imagemask restore}B/G{{id gp get/gp gp 1 add N A 18 mod S 18 idiv pl S get exec}loop}B/adv{cp add/cp X}B /chg{rw cp id gp 4 index getinterval putinterval A gp add/gp X adv}B/nd{ /cp 0 N rw exit}B/lsh{rw cp 2 copy get A 0 eq{pop 1}{A 255 eq{pop 254}{ A A add 255 and S 1 and or}ifelse}ifelse put 1 adv}B/rsh{rw cp 2 copy get A 0 eq{pop 128}{A 255 eq{pop 127}{A 2 idiv S 128 and or}ifelse} ifelse put 1 adv}B/clr{rw cp 2 index string putinterval adv}B/set{rw cp fillstr 0 4 index getinterval putinterval adv}B/fillstr 18 string 0 1 17 {2 copy 255 put pop}for N/pl[{adv 1 chg}{adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{adv rsh nd}{1 add adv}{/rc X nd}{ 1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]A{bind pop} forall N/D{/cc X A type/stringtype ne{]}if nn/base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{A A length 1 sub A 2 index S get sf div put }if put/ctr ctr 1 add N}B/I{cc 1 add D}B/bop{userdict/bop-hook known{ bop-hook}if/SI save N @rigin 0 0 moveto/V matrix currentmatrix A 1 get A mul exch 0 get A mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N/eop{ SI restore userdict/eop-hook known{eop-hook}if showpage}N/@start{ userdict/start-hook known{start-hook}if pop/VResolution X/Resolution X 1000 div/DVImag X/IEn 256 array N 2 string 0 1 255{IEn S A 360 add 36 4 index cvrs cvn put}for pop 65781.76 div/vsize X 65781.76 div/hsize X}N /p{show}N/RMat[1 0 0 -1 0 0]N/BDot 260 string N/Rx 0 N/Ry 0 N/V{}B/RV/v{ /Ry X/Rx X V}B statusdict begin/product where{pop false[(Display)(NeXT) (LaserWriter 16/600)]{A length product length le{A length product exch 0 exch getinterval eq{pop true exit}if}{pop}ifelse}forall}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale Rx Ry false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR Rx Ry scale 1 1 false RMat{BDot} imagemask grestore}}ifelse B/QV{gsave newpath transform round exch round exch itransform moveto Rx 0 rlineto 0 Ry neg rlineto Rx neg 0 rlineto fill grestore}B/a{moveto}B/delta 0 N/tail{A/delta X 0 rmoveto}B/M{S p delta add tail}B/b{S p tail}B/c{-4 M}B/d{-3 M}B/e{-2 M}B/f{-1 M}B/g{0 M} B/h{1 M}B/i{2 M}B/j{3 M}B/k{4 M}B/w{0 rmoveto}B/l{p -4 w}B/m{p -3 w}B/n{ p -2 w}B/o{p -1 w}B/q{p 1 w}B/r{p 2 w}B/s{p 3 w}B/t{p 4 w}B/x{0 S rmoveto}B/y{3 2 roll p a}B/bos{/SS save N}B/eos{SS restore}B end %%EndProcSet TeXDict begin 40258431 52099146 1000 600 600 (sPpr.dvi) @start %DVIPSBitmapFont: Fa cmbx9 9 7 /Fa 7 58 df<147814F81303131FEA03FFB5FCA3EAFC1F1200B3B2007FB512FEA41F317A B02C>49 D51 D<000C140ED80FE013FE90B5FC5D5D5D5D5D92C7FC14FC14F091 C8FC1380A6EB87FE9038BFFFC090B512F09038FC0FF89038E003FE01C07F497E01001480 000E6D13C0C8FCA216E0A3121FEA7F807F487EA316C05B5CD87F801480D87C0014006C5B 393F8007FE391FE01FFC0007B512F06C14C0C691C7FCEB1FF823327CB02C>53 DI<123C 123F90B612F8A44815F016E016C0168016005D007CC7127E00785C4A5A00F8495A48495A 4A5A4A5AC7FC4AC7FC147E14FE5C13015C1303A2495AA2130FA2131FA25C133FA4137FA9 6D5AA2010FC8FC25337BB12C>III E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fb cmr5 5 2 /Fb 2 51 df<1360EA01E0120F12FF12F11201B3A3387FFF80A2111C7B9B1C>49 DI E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fc cmsy7 7 3 /Fc 3 49 df0 D<1338A50060130C00F8133E00FC137E00FE13 FE383FBBF83807FFC000011300EA007C48B4FC000713C0383FBBF838FE38FE00FC137E00 F8133E0060130C00001300A517197B9A22>3 D<13E0EA01F0EA03F8A3EA07F0A313E0A2 120F13C0A3EA1F80A21300A25A123EA35AA3127812F8A25A12100D1E7D9F13>48 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fd cmsl10 10 34 /Fd 34 122 df<15C01401EC0780EC0F00141E5C5C5C495A495A13075C49C7FC5B131E5B 137C137813F85B12015B12035B1207A2485AA348C8FCA3123EA45AA512FC5AA85AA97EA3 1278A47EA37EA37E7E7F12037F6C7E120013707F13181A5275BD20>40 D<130613076D7E6D7E806D7E147014781438143C80A380A3EC0780A415C0A31403A91407 A8140FA21580A4EC1F00A4143EA35CA35CA25C13015C13035C13075C130F91C7FC131E13 3E133C5B13F85B485A485A485A48C8FC121E5A5A12E05A1A527FBD20>I44 DI48 D<15C014031407141F14FF90B5FC15803801FE3FC7 FCA3147F1500A55C5CA513015CA513035CA513075CA5130F5CA5131F5CA3133F497EB612 F0A215E01C3878B72A>II<166016E0150115031507150F16C0151F153F 157F15FFEC01DF913803BF80153F1406140C141C14389138707F00146014C0EB0180EB03 005B010E13FE5B13185B5B5B0001495AEA0380130012065A5A0038495A5A5AB712F8A3C7 3807F8005DA4140FA25DA4EC3FF0011FB512C0A325397BB82A>52 D57 D<160EA2161EA2163E163F5EA25EA25D83ED037FA21506A2150C83ED183FA21530A21560 83EDC01F14011580140303007F5C0206130F140E140C141C021880023813071430147014 6091B6FC835B913880000349C7FCA2130683491401A25BA24981A201708013F0486C4A13 80D80FFC4A13C0B56C017F13FF93B6FC18FE383C7DBB3E>65 D67 D<017FB612F017FE717E0100D9C0007F6E 48EB1FE0EF07F002FF6E7E92C76C7E717E8484F03F805B5C19C0181FA219E013035CA513 074A153FA5010F17C04A157FA31980A2011F16FF4A1600A24D5AA24D5A013F5E4A140760 4D5A4D5A173F017F4B5A4A02FEC7FC4C5AEE07F8EE1FF0D801FFECFFC0B8C8FC16FC16C0 3B397DB83F>I<017FB500C0B61280A24C150001009026C0000113806E486D90C7FC5F14 FF92C75BA417035B4A5DA4170713034A5DA4170F13074A5D91B7FCA302F8C7121F130F4A 5DA4173F131F4A5DA4177F133F4A5DA417FF137F4A92C8FCA448486C01037FB60081B6FC A203015C41397DB83E>72 D<013FB512E0A25B9039007FE0006E5AA2147F5DA514FF92C7 FCA55B5CA513035CA513075CA5130F5CA5131F5CA5133F5CA4EBFFE0007FEBFFC0A2B6FC 23397EB81E>I<90267FFF80923803FFFE81610100F0FE00027FEE0DFCDA6FE0151B14EF 02CFEE33F8A2DAC7F01563A219C71301028792380187F0DA83F8EC0307A21806190F9026 0381FC140C02015F1818A218306E6C151F491660010604C05BA2037FEB0180A294380300 3F130E010C03065CED3F805F5F197F011C6D6C5A011895C7FC5FA25FDB0FE05C0138ECE1 80013002E3C75AA216E6ED07F604FC1301137001604A5C150301F05C00015DD807FCEE07 FEB500E0D9C003B512FC150116804F397DB84C>77 D79 D<017FB612E017FC17FF01 00D9C00013C06E48EB1FE0EF0FF002FFEC07F892C7EA03FCA318FEA25B5CA418FC010315 075C18F8EF0FF0A2EF1FE00107ED3FC04AEC7F00EE01FEEE0FF891B612E094C7FCD90FF8 C9FC5CA5131F5CA5133F5CA5137F5CA448487EB67EA337397DB839>I83 D<14FF010713E090381F 01F8903878007C01F8137E01FE7F0001801680A35BEA007090C7FCA4EC0FFF49B5FC9039 0FFC3F00EB7FC03801FE00EA03F848485B485A4848137E485A007F150690C7FC15FE48EC FC0C481301A21403007F9038077C18140E3A3F801C7E303A1FC0F83FF03A07FFE01FC0C6 9038000F8027277CA52A>97 D99 DI<147F903803 FFE090380F81F090383E00FC49137C48487F4848133F0007805B48481480121F5B123FA2 48C7FCA3B71200A248C9FCA65A7EA2007E140EA25D6C14186C14386D5B6C6C485A3907E0 03802601F01FC7FC38007FFCEB1FE021277BA525>I<157F913801FFC0913807C1E09138 1F87F0EC3F0F147E14FCA2D901F813E0ED07C04948C7FCA413075CA5130F5CA20007B512 E0A326001FC0C7FC5CA5133F91C8FCA55B137EA513FE5BA512015BA4487EB512F0A3243B 7EBA19>IIII<90390FC03FC0 D803FFEBFFF0489038C3C0F89138CF007C26003FDC137E6D5A02F0133E4A133F5C5E4948 137EA291C7FCA316FE5B017E5CA4150113FE495CA415031201495CA400031407B500E1B5 12C0A202C114802A257EA42E>110 DI<903901F80FE0017FEB3F FC01FFEBF03F9139FBC00F80902607FF0013C06D48EB07E04AEB03F05C4A14F816010107 15FC5CA5130F5CA41603011F15F85CEE07F0A2EE0FE0A2013FEC1FC01780163F6EEB7F00 16FE9138E001F890397F7003F090397E3C0FC0DA0FFFC7FCEC03F891C9FC13FEA25BA412 01A25BA2487EB512E0A32E3581A42E>I<90381F807C3903FF81FF489038878F80EC8E1F 39003F9C3FEB1F3814709138601F00ECE0044AC7FC133F5CA291C8FCA35B137EA513FE5B A512015BA4487EB512F0A321257EA421>114 D<903803FE0C90380FFF9C90383E01FCEB F0004848137C4848133C1538485AA215181538487E1530D807F0130013FCEBFFE06C13FC 14FFC614806D13C0011F13E01300EC0FF01407003013031401A31238007814E0A3007CEB 03C0EC0780127EB4EB1F0038F3C07C38E1FFF038C03F801E277DA521>I<1306A4130EA2 130C131CA2133C137C13FC5B12031207001FB5FCB6FCA23803F8005BA512075BA5120F5B A5001F130C1380A4141C003F131813007E1438EB80301470380FC0E03807C1C03803FF80 38007E00183479B220>I119 D<90B538803FFE5A150026000FF8EB0FF06D48EB07C017801700010314065EA26E5B0101 143816305E8001005CA24B5A1503027E90C7FC1506A25D147F6E5A1538153015E0141F5D A25D140F92C8FC140EA2140CA25C143814305CA2003E5B127E38FE018049C9FC5BEAFC0E EA701C1378EA3FE0EA0F802F3580A32C>121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fe cmr7 7 6 /Fe 6 53 df<140EB3A2B812E0A3C7000EC8FCB3A22B2B7DA333>43 D48 D<13381378EA01F8121F12FE12E01200B3AB487EB512F8A215267BA521 >I<13FF000313E0380E03F0381800F848137C48137E00787F12FC6CEB1F80A4127CC7FC 15005C143E147E147C5C495A495A5C495A010EC7FC5B5B903870018013E0EA0180390300 030012065A001FB5FC5A485BB5FCA219267DA521>I<13FF000313E0380F01F8381C007C 0030137E003C133E007E133FA4123CC7123E147E147C5C495AEB07E03801FF8091C7FC38 0001E06D7E147C80143F801580A21238127C12FEA21500485B0078133E00705B6C5B381F 01F03807FFC0C690C7FC19277DA521>I<1438A2147814F81301A2130313071306130C13 1C131813301370136013C012011380EA03005A120E120C121C5A12305A12E0B612E0A2C7 EAF800A7497E90383FFFE0A21B277EA621>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Ff cmr8 8 52 /Ff 52 122 df<123C127EB4FCA21380A2127F123D1201A312031300A25A1206120E5A5A 5A126009157A8714>44 DI<123C127E12FFA4127E123C08087A 8714>I<15C0140114031580A214071500A25C140EA2141E141CA2143C143814781470A2 14F05CA213015CA213035C130791C7FCA25B130EA2131E131CA2133C1338A21378137013 F05BA212015BA212035BA2120790C8FC5A120EA2121E121CA2123C1238A212781270A212 F05AA21A437CB123>II<130C133C137CEA03FC12FFEAFC7C 1200B3B113FE387FFFFEA2172C7AAB23>III< 140EA2141E143EA2147E14FEA2EB01BE1303143E1306130E130C131813381330136013E0 13C0EA0180120313001206120E120C5A123812305A12E0B612FCA2C7EA3E00A9147F9038 1FFFFCA21E2D7EAC23>I<000CEB0180380FC01F90B512005C5C14F014C0D80C7EC7FC90 C8FCA8EB1FC0EB7FF8380DE07C380F801F01001380000E130F000CEB07C0C713E0A21403 15F0A4127812FCA448EB07E012E0006014C00070130F6C14806CEB1F006C133E380780F8 3801FFE038007F801C2D7DAB23>II<12 30123C003FB512F8A215F05A15E039700001C000601480140348EB0700140E140CC7121C 5C143014705C495AA2495AA249C7FCA25B130E131EA2133EA3133C137CA413FCA913781D 2E7CAC23>I57 D64 D<4A7E4A7EA34A7EA24A7EA3EC1BF81419 A2EC30FCA2EC70FEEC607EA24A7EA349486C7EA2010380EC000FA201066D7EA3496D7EA2 011FB57EA29038180001496D7EA349147EA201E0147F4980A20001ED1F801203000716C0 D80FF0EC3FE0D8FFFC0103B5FCA2302F7EAE35>I67 DIIIIII78 DII82 D<90383F80303901FFF0703807C07C390F000EF0001E13 074813034813011400127000F01470A315307EA26C1400127E127FEA3FE013FE381FFFE0 6C13FC6C13FF00011480D8003F13E013039038003FF0EC07F81401140015FC157C12C015 3CA37EA215787E6C14706C14F06CEB01E039F78003C039E3F00F0038E07FFE38C00FF01E 2F7CAD27>I<007FB712F8A29039000FC003007C150000701638A200601618A200E0161C A248160CA5C71500B3A94A7E011FB512E0A22E2D7EAC33>III<13FF000713C0380F01F0381C00F8003F137C80A2143F001E7FC7FCA4EB07FF13 7F3801FE1FEA07F0EA1FC0EA3F80EA7F00127E00FE14065AA3143F7E007E137F007FEBEF 8C391F83C7FC390FFF03F83901FC01E01F207D9E23>97 DII<15F8141FA214011400ACEB0FE0EB7FF83801 F81E3803E0073807C003380F8001EA1F00481300123E127EA25AA9127C127EA2003E1301 7EEB8003000F13073903E00EFC3A01F03CFFC038007FF090391FC0F800222F7EAD27>I< EB1F80EBFFF03803E0783807C03E380F801E381F001FEC0F80123E007E130715C0127C12 FCA3B6FCA200FCC8FCA5127EA2003E14C0123F6C1301390F80038001C013003803E00F38 01F03C38007FF8EB1FC01A207E9E1F>II<013F13F89038 FFC3FE3903E1FF1E3807807C000F140C391F003E00A2003E7FA76C133EA26C6C5A000713 78380FE1F0380CFFC0D81C3FC7FC90C8FCA3121E121F380FFFF814FF6C14C04814F0391E 0007F848130048147C12F848143CA46C147C007C14F86CEB01F06CEB03E03907E01F8039 01FFFE0038003FF01F2D7E9D23>III107 DI<2607C07FEB07F03BFFC3FFC03FFC903AC783F0783F3C0FCE01 F8E01F803B07DC00F9C00F01F8D9FF8013C04990387F000749137EA249137CB2486C01FE EB0FE03CFFFE0FFFE0FFFEA2371E7E9D3C>I<3807C0FE39FFC3FF809038C703E0390FDE 01F0EA07F8496C7EA25BA25BB2486C487E3AFFFE1FFFC0A2221E7E9D27>II<3807C0FE39FFC7FF809038CF03E0390FDC01F03907F800FC4913 7E49133E49133FED1F80A3ED0FC0A8151F1680A2ED3F00A26D137E6D137C5D9038FC01F0 9038CE07E09038C7FF80D9C1FCC7FC01C0C8FCA9487EEAFFFEA2222B7E9D27>I<380781 F838FF87FEEB8E3FEA0F9CEA07B813B0EBF01EEBE000A45BB0487EB5FCA2181E7E9D1C> 114 D<3801FE183807FFB8381E01F8EA3C00481378481338A21418A27E7EB41300EA7FF0 6CB4FC6C13C06C13F0000113F838001FFC130138C0007E143EA26C131EA27EA26C133CA2 6C137838FF01F038E3FFC000C0130017207E9E1C>I<1360A413E0A312011203A2120712 1FB512F0A23803E000AF1418A714383801F03014703800F860EB3FE0EB0F80152A7FA81B >II<3AFFFC01FFC0A23A0FE0007E00000714 7C15380003143015706C6C1360A26C6C5BA390387C0180A26D48C7FCA2EB3F07EB1F06A2 EB0F8CA214DCEB07D8A2EB03F0A36D5AA26D5A221E7F9C25>I<3BFFFC3FFE07FFA23B0F E003F001F801C09038E000F00007010114E0812603E00314C0A2913807F8012701F00678 1380A29039F80E7C030000D90C3C1300A290397C181E06A2151F6D486C5AA2168C90391F 600798A216D890390FC003F0A36D486C5AA36DC75A301E7F9C33>I<3AFFFC01FFC0A23A 0FE0007E000007147C1538000314306D137000011460A26C6C5BA2EBFC01017C5BEB7E03 013E90C7FCA2EB1F06A2148EEB0F8CA2EB07D8A2EB03F0A36D5AA26D5AA2495AA2130391 C8FC1278EAFC06A25B131CEA7838EA7070EA3FE0EA0F80222B7F9C25>121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fg cmsy6 6 4 /Fg 4 123 df<136013701360A20040132000E0137038F861F0387E67E0381FFF803807 FE00EA00F0EA07FE381FFF80387E67E038F861F038E060700040132000001300A2137013 6014157B9620>3 D120 D<136013F0A81360A4387C63E0B512F0A2387C 63E038006000A313F0B3A21360A7142F7CA31E>I<136013F0A61360A3B512F0A3380060 00A313F0A6136090C7FC136013F0A61360A3B512F0A338006000A313F0A61360142F7CA3 1E>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fh cmcsc10 10 14 /Fh 14 115 df<121C127FEAFF80A5EA7F00121C090977881B>46 D49 DII< 151C153CA2157C15FCA214011403A21407140F141D141914311471146114C11301EB0381 14011307130E130C131813381330136013E0EA01C01380EA03005A12065A121C5A123012 705AB712FEA3C73801FC00AB4A7E49B512FCA327397DB82E>I<00061406D80780131E90 38F801FC90B5FC5D5D15C05D4AC7FC38067FF090C9FCABEB03FC90381FFF8090387C07E0 9038E001F03907C000F8497F90C7127E0006147FC8EA3F80A216C0151FA216E0A4123E12 7F487EA490C713C048143F126016800070147F6C150015FE6C5C000F495A39078007F039 03F01FE06CB512806C6C48C7FCEB0FF0233A7BB72E>I76 D<003FB812FCA3D9C001EB800390C790C7FC007C173E0078171E0070170EA300 601706A400E01707481703A4C81500B3B0020313C0010FB612F0A338397CB841>84 D<1407A24A7EA34A7EA3EC37E0A2EC77F01463A2ECC1F8A201017F1480A2903803007EA3 01067FA2010E80010C131FA2496D7EA2013FB57EA29038300007496D7EA3496D7EA20001 8149130012036D801207D81FE0903801FF80D8FFF8010F13F8A22D2C7DAB33>97 D101 D104 D109 D111 D114 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fi cmsy10 10 9 /Fi 9 104 df<007FB81280B912C0A26C17803204799641>0 D<126012F812FEEA7F80EA 3FE0EA0FF8EA03FEC66C7EEB3FE0EB0FF8EB03FE903800FF80EC3FE0EC0FF8EC03FE9138 00FF80ED3FE0ED0FF8ED03FE923800FF80EE3FE0EE0FF8EE03FE933800FF80EF3FC0171F EF7F80933801FF00EE07FCEE1FF0EE7FC04B48C7FCED07FCED1FF0ED7FC04A48C8FCEC07 FCEC1FF0EC7FC04948C9FCEB07FCEB1FF0EB7FC04848CAFCEA07FCEA1FF0EA7FC048CBFC 12FC1270CCFCAE007FB81280B912C0A26C1780324479B441>21 D<020FB6128091B712C0 1303010F1680D91FF8C9FCEB7F8001FECAFCEA01F8485A485A485A5B48CBFCA2123EA25A A2127812F8A25AA87EA21278127CA27EA27EA26C7E7F6C7E6C7E6C7EEA00FEEB7F80EB1F F86DB71280010316C01300020F1580323279AD41>26 D<1478A414F85CA213015C130349 5AA2495A49CCFC5B137E5B485A485AEA0FE0003FBA12FEBCFCA2003F19FED80FE0CCFCEA 03F06C7E6C7E137E7F7F6D7E6D7EA26D7E1301801300A2801478A4482C7BAA53>32 D54 D<0060161800F0163CB3B26C167CA2007C16 F8A26CED01F0003F15036C6CEC07E06C6CEC0FC0D807F0EC3F80D803FE903801FF003A00 FFC00FFC6DB55A011F14E0010391C7FC9038007FF82E347CB137>91 DI102 D<12FCEAFFC0EA07F0EA01 FCEA007E7F80131F80130FB3A7801307806D7E6D7EEB007EEC1FF0EC07F8EC1FF0EC7E00 495A495A495A5C130F5CB3A7131F5C133F91C7FC137E485AEA07F0EAFFC000FCC8FC1D53 7ABD2A>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fj cmr10 10 77 /Fj 77 123 df11 DI14 D<127812FCA27E7EEA7F80121FEA0FC0EA07E0 EA03F012001378133C131E13060F0F77B92A>18 D<001C131C007F137F39FF80FF80A26D 13C0A3007F137F001C131C00001300A40001130101801380A20003130301001300485B00 061306000E130E485B485B485B006013601A197DB92A>34 D<121C127FEAFF80A213C0A3 127F121C1200A412011380A2120313005A1206120E5A5A5A12600A1979B917>39 D<146014E0EB01C0EB0380EB0700130E131E5B5BA25B485AA2485AA212075B120F90C7FC A25A121EA2123EA35AA65AB2127CA67EA3121EA2121F7EA27F12077F1203A26C7EA26C7E 1378A27F7F130E7FEB0380EB01C0EB00E01460135278BD20>I<12C07E12707E7E7E120F 6C7E6C7EA26C7E6C7EA21378A2137C133C133E131EA2131F7FA21480A3EB07C0A6EB03E0 B2EB07C0A6EB0F80A31400A25B131EA2133E133C137C1378A25BA2485A485AA2485A48C7 FC120E5A5A5A5A5A13527CBD20>II<15301578B3A6007FB812F8B912FCA26C17F8C80078C8FCB3 A6153036367BAF41>I<121C127FEAFF80A213C0A3127F121C1200A412011380A2120313 005A1206120E5A5A5A12600A19798817>II<121C127FEAFF80A5 EA7F00121C0909798817>I<150C151E153EA2153C157CA2157815F8A215F01401A215E0 1403A215C01407A21580140FA215005CA2141E143EA2143C147CA2147814F8A25C1301A2 5C1303A2495AA25C130FA291C7FC5BA2131E133EA2133C137CA2137813F8A25B1201A25B 1203A25B1207A25B120FA290C8FC5AA2121E123EA2123C127CA2127812F8A25A12601F53 7BBD2A>IIIII<1538 A2157815F8A2140114031407A2140F141F141B14331473146314C313011483EB03031307 1306130C131C131813301370136013C01201EA038013005A120E120C5A123812305A12E0 B712F8A3C73803F800AB4A7E0103B512F8A325397EB82A>I<0006140CD80780133C9038 F003F890B5FC5D5D158092C7FC14FC38067FE090C9FCABEB07F8EB3FFE9038780F803907 E007E090388003F0496C7E12066E7EC87EA28181A21680A4123E127F487EA490C7130048 5C12E000605C12700030495A00385C6C1303001E495A6C6C485A3907E03F800001B5C7FC 38007FFCEB1FE0213A7CB72A>II<12301238123E00 3FB612E0A316C05A168016000070C712060060140E5D151800E01438485C5D5DC712014A 5A92C7FC5C140E140C141C5CA25CA214F0495AA21303A25C1307A2130FA3495AA3133FA5 137FA96DC8FC131E233B7BB82A>III<121C127FEAFF80A5EA7F00121CC7FCB2121C127FEAFF80A5EA7F00121C092479A317> I<121C127FEAFF80A5EA7F00121CC7FCB2121C127F5A1380A4127F121D1201A412031300 A25A1206A2120E5A121812385A1260093479A317>I<007FB812F8B912FCA26C17F8CCFC AE007FB812F8B912FCA26C17F836167B9F41>61 D<1538A3157CA315FEA34A7EA34A6C7E A202077FEC063FA2020E7FEC0C1FA2021C7FEC180FA202387FEC3007A202707FEC6003A2 02C07F1501A2D901807F81A249C77F167FA20106810107B6FCA24981010CC7121FA2496E 7EA3496E7EA3496E7EA213E0707E1201486C81D80FFC02071380B56C90B512FEA3373C7D BB3E>65 DI<913A01FF800180020FEBE003027F13F8903A01FF807E 07903A03FC000F0FD90FF0EB039F4948EB01DFD93F80EB00FF49C8127F01FE153F120148 48151F4848150FA248481507A2485A1703123F5B007F1601A35B00FF93C7FCAD127F6DED 0180A3123F7F001F160318006C7E5F6C7E17066C6C150E6C6C5D00001618017F15386D6C 5CD91FE05C6D6CEB03C0D903FCEB0F80902701FF803FC7FC9039007FFFFC020F13F00201 1380313D7BBA3C>IIIIIII75 DIIII82 DI<003FB812E0A3D9C003EB001F273E0001FE130348EE01F00078160000701770A300 601730A400E01738481718A4C71600B3B0913807FF80011FB612E0A335397DB83C>IIII91 D<3901800180000313033907000700000E130E485B001813180038133800301330007013 7000601360A200E013E0485BA400CE13CE39FF80FF806D13C0A3007F137FA2393F803F80 390E000E001A1974B92A>II96 DIIIII<147E903803 FF8090380FC1E0EB1F8790383F0FF0137EA213FCA23901F803C091C7FCADB512FCA3D801 F8C7FCB3AB487E387FFFF8A31C3B7FBA19>IIIIIII<2703F00FF0EB1FE000FFD9 3FFCEB7FF8913AF03F01E07E903BF1C01F83803F3D0FF3800FC7001F802603F70013CE01 FE14DC49D907F8EB0FC0A2495CA3495CB3A3486C496CEB1FE0B500C1B50083B5FCA34025 7EA445>I<3903F00FF000FFEB3FFCECF03F9039F1C01F803A0FF3800FC03803F70013FE 496D7EA25BA35BB3A3486C497EB500C1B51280A329257EA42E>II<39 03F01FE000FFEB7FF89038F1E07E9039F3801F803A0FF7000FC0D803FEEB07E049EB03F0 4914F849130116FC150016FEA3167FAA16FEA3ED01FCA26DEB03F816F06D13076DEB0FE0 01F614C09039F7803F009038F1E07E9038F0FFF8EC1FC091C8FCAB487EB512C0A328357E A42E>II<3807E01F00FFEB7FC09038E1E3E09038E387F0380FE707EA03E613EE9038 EC03E09038FC0080491300A45BB3A2487EB512F0A31C257EA421>II<1318A51338A31378A313F812 0112031207001FB5FCB6FCA2D801F8C7FCB215C0A93800FC011580EB7C03017E13006D5A EB0FFEEB01F81A347FB220>IIIII< B538803FFEA33A0FF8000FF06C48EB07C00003EC03806C7E16007F00001406A2017E5BA2 137F6D5BA26D6C5AA2ECC070010F1360A26D6C5AA214F101035BA2D901FBC7FCA214FF6D 5AA2147CA31438A21430A214701460A25CA2EA7C0100FE5B130391C8FC1306EAFC0EEA70 1C6C5AEA1FF0EA0FC027357EA32C>I<003FB512FCA2EB8003D83E0013F8003CEB07F000 38EB0FE012300070EB1FC0EC3F800060137F150014FE495AA2C6485A495AA2495A495A49 5AA290387F000613FEA2485A485A0007140E5B4848130C4848131CA24848133C48C7127C 48EB03FC90B5FCA21F247EA325>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fk cmmi7 7 7 /Fk 7 116 df<903B3FFFE00FFFC0A2010190390001FC006D4814F017C0027F495A4CC7 FC6E130E6F5A021F5B6F5A5E91380FE1C0EDE380DA07F7C8FC15FE6E5A5D6E7EA2811403 EC077F140E4A7E02187FEC301F02607F14C049486C7EEB030001066D7E5B01386D7E5B01 F06D7E485AD80FF0497ED8FFFC90381FFFE0A232287DA736>88 D<130E131F5BA2133E13 1C90C7FCA7EA03E0487EEA0C78EA187C1230A212605B12C0A2EA01F0A3485AA2485AA2EB C180EA0F81A2381F0300A213066C5A131CEA07F06C5A11287DA617>105 D<1407EC0F80141FA21500140E91C7FCA7EB03E0EB07F8EB0C3C1318EB303E136013C0A2 48485AA2C7FCA25CA4495AA4495AA4495AA4495AA21238D87C1FC7FC12FC133E485AEA70 F8EA7FE0EA1F80193380A61B>I<133EEA07FEA2EA007CA213FCA25BA21201A25BA21203 EC07809038E01FC0EC38600007EB61E014C3EBC187EBC307D80FC613C09038CC038001B8 C7FC13E0487E13FEEB3F80EB0FC0486C7E1303003E1460A2127EECC0C0127CECC18012FC 903801E30038F800FE0070137C1B297CA723>I<9038F007C03901FC1FF039031E787800 06EBE03C90381FC01C000CEB801E14005B0018141F133E1200137E153E137CA213FC157C 5B1578000114F0A2EC01E0EC03C03903FC07809038FE1F00EBE7FCEBE1F0D807E0C7FCA2 5BA2120FA25B121FEAFFF8A22025809922>112 D<3807803E390FE0FF803818F3C13930 F703C0EBFE073860FC0F13F8158039C1F0070091C7FC1201A2485AA4485AA4485AA448C8 FCA2120E1A1B7D991F>114 DI E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fl cmmi10 10 32 /Fl 32 123 df<121C127FEAFF80A5EA7F00121C0909798817>58 D<121C127FEAFF80A213C0A3127F121C1200A412011380A2120313005A1206120E5A5A5A 12600A19798817>I<9339FF8001C0030F13E0037F9038F80380913A01FF807E07913A07 F8000F0FDA1FE0EB079FDA3F80903803BF0002FFC76CB4FCD901FC80495A4948157E495A 495A4948153E017F163C49C9FC5B1201484816385B1207485A1830121F4993C7FCA2485A A3127F5BA312FF90CCFCA41703A25F1706A26C160E170C171C5F6C7E5F001F5E6D4A5A6C 6C4A5A16076C6C020EC8FC6C6C143C6C6C5C6CB4495A90393FE00FC0010FB5C9FC010313 FC9038007FC03A3D7CBA3B>67 D71 D<0103B5D8F803B512F8495DA290260007F8C73807F8004B5DA2020F150F615DA2021F15 1F615DA2023F153F615DA2027F157F96C7FC92C8FCA24A5D605CA249B7FC60A202FCC712 0101031503605CA201071507605CA2010F150F605CA2011F151F605CA2013F153F605CA2 017F157F95C8FC91C8FC496C4A7EB690B6FCA345397DB845>I<0107B512FCA216F89039 0007F8005DA2140FA25DA2141FA25DA2143FA25DA2147FA292C7FCA25CA25CA21301A25C A21303A25CA21307A25CA2130FA25CA2131FA25CA2133FA25CA2137FA291C8FC497EB6FC A326397DB824>I<0203B512FCA3DA000113006F5AA215015EA315035EA315075EA3150F 5EA3151F5EA3153F5EA3157F93C7FCA35D5DA31401A25DA21403120FD83F805B127FEBC0 07D8FF805BA24A5AEB001F00FC5C00E0495A006049C8FC007013FE383801F8381E07F038 07FFC0D801FEC9FC2E3B7AB82E>I<902603FFF891381FFFF8496D5CA2D9000703011300 6FEC007C02061678DA0EFF157081020C6D1460A2DA1C3F15E0705CEC181F82023815016F 6C5C1430150702706D1303030392C7FC02607FA2DAE0015C701306ECC0008201016E130E EF800C5C163F0103EDC01C041F131891C713E0160F49EDF03818300106140717F8010E02 031370EFFC60130CEE01FE011C16E004005B011815FF177F1338600130153FA20170151F 95C8FC01F081EA07FCB512E01706A245397DB843>78 D<4BB4FC031F13F09238FE01FC91 3903F0007EDA07C0EB1F80DA1F80EB0FC0023EC7EA07E002FCEC03F0495A4948EC01F849 5A4948EC00FC495A49C912FE49167E13FE49167F1201485AA2485AA2120F5B001F17FFA2 485AA34848ED01FEA400FFEE03FC90C9FCA2EF07F8A2EF0FF0A218E0171F18C0EF3F806C 167F180017FE4C5A6C6C5D1603001F4B5A6D4A5A000FED1F806C6C4AC7FC6D147E0003EC 01F8D801FC495AD8007EEB0FC090263F807FC8FC903807FFF801001380383D7CBA3F>I< 0103B7FC4916E018F8903B0007F80007FC4BEB00FE187F020FED3F80F01FC05DA2021F16 E0A25DA2143FF03FC05DA2027FED7F80A292C8130018FE4A4A5A604AEC07F04D5A0101ED 3FC04CB4C7FC91B612FC17E0D903FCCAFCA25CA21307A25CA2130FA25CA2131FA25CA213 3FA25CA2137FA291CBFC497EB6FCA33B397DB835>I<0103B612F849EDFF8018E0903B00 07F8001FF84BEB03FCEF00FE020F157FA24BEC3F80A2021F16C0A25DA2143FF07F805DA2 027FEDFF006092C7485A4D5A4A4A5A4D5A4AEC1F80057FC7FC0101EC07F891B612E094C8 FC9139FC000FC00103EC03F0707E4A6D7E831307177E5C177F010F5D5F5CA2011F1401A2 5CA2133F16034A4A1360A2017F17E019C091C71401496C01011480B61503933900FE0700 EF7E0ECAEA1FFCEF07F03B3B7DB83F>82 D<92391FE00380DBFFFC130002036D5A91390F E01F8F91393F0007DF027EEB01FE02F81300495A4948147E177C4948143C495AA2011F15 3891C8FCA3491530A28094C7FC80806D7E14FEECFFE06D13FE6DEBFFC06D14F06D806D80 021F7F02037FEC003F03037F1500167F163F161FA3120C160FA2001C151F94C7FCA3003C 153EA25E003E5D127E007F4A5A6D495A6DEB0FC0D8F9F0495AD8F0FE01FEC8FC39E03FFF F8010F13E0D8C00190C9FC313D7CBA33>I<267FFFFC91383FFFC0B55DA2000390C83807 FC006C48ED03E06060000094C7FC5F17065FA25F6D5DA26D5D17E05F4C5AA24CC8FC6E13 06A2013F5C161C16185EA25E6E5BA2011F495A150393C9FC1506A25D6E5AA2010F5B1570 15605DA2ECE18002E3CAFC14F3EB07F614FE5C5CA25C5CA26D5AA25C91CBFC3A3B7CB830 >86 D<49B500F890387FFFF095B5FC1AE0D90003018090380FFC004BC713E00201ED0780 4EC7FC6E6C140E606F5C705B606F6C485A4D5A031F91C8FCEEE0065F6F6C5A5F03075B70 5A16F96FB45A94C9FC6F5AA36F7EA34B7FED037F9238063FC0150E4B6C7E1538ED700F03 E07F15C04A486C7EEC0300020613034A805C4A6D7E14704A1300494880495A49C86C7E13 0E011E153F017E4B7ED803FF4B7E007F01E0011FEBFFC0B5FC6144397EB845>88 DI101 D103 DI<14E0EB03F8A21307A314F0EB01C090C7FCAB13F8EA03FEEA070F000E1380 121C121812381230EA701F1260133F00E0130012C05BEA007EA213FE5B1201A25B12035B A20007131813E01438000F133013C01470EB806014E014C01381EB838038078700EA03FE EA00F815397EB71D>I<150FED3F80A2157FA31600151C92C7FCABEC0F80EC3FE0ECF0F0 903801C0F849487E14005B130E130C131CEB1801133801305BA2EB0003A25DA21407A25D A2140FA25DA2141FA25DA2143FA292C7FCA25CA2147EA214FEA25CA21301001E5B123F38 7F83F0A238FF87E0495A00FE5BD87C1FC8FCEA707EEA3FF8EA0FC0214981B722>II109 DI<90390F8003F090391FE00FFC903939F03C1F903A70F8700F80903AE0FDE0 07C09038C0FF80030013E00001491303018015F05CEA038113015CA2D800031407A25CA2 0107140FA24A14E0A2010F141F17C05CEE3F80131FEE7F004A137E16FE013F5C6E485A4B 5A6E485A90397F700F80DA383FC7FC90387E1FFCEC07E001FEC9FCA25BA21201A25BA212 03A25B1207B512C0A32C3583A42A>112 D<3903E001F83907F807FE390E3C1E07391C3E 381F3A183F703F800038EBE07F0030EBC0FF00705B00601500EC007E153CD8E07F90C7FC EAC07EA2120013FE5BA312015BA312035BA312075BA3120F5BA3121F5B0007C9FC21267E A425>114 D<14FF010313C090380F80F090383E00380178131C153C4913FC0001130113 E0A33903F000F06D13007F3801FFE014FC14FF6C14806D13C0011F13E013039038003FF0 14071403001E1301127FA24814E0A348EB03C012F800E0EB07800070EB0F006C133E001E 13F83807FFE0000190C7FC1E267CA427>I<13F8D803FE1438D8070F147C000E6D13FC12 1C1218003814011230D8701F5C12601503EAE03F00C001005B5BD8007E1307A201FE5C5B 150F1201495CA2151F120349EC80C0A2153F1681EE0180A2ED7F0303FF130012014A5B3A 00F8079F0E90397C0E0F1C90393FFC07F8903907F001F02A267EA430>117 D<01F8EB03C0D803FEEB07E0D8070F130F000E018013F0121C12180038140700301403D8 701F130112601500D8E03F14E000C090C7FC5BEA007E16C013FE5B1501000115805B1503 16001203495B1506150E150C151C151815385D00015C6D485A6C6C485AD97E0FC7FCEB1F FEEB07F024267EA428>I<01F816F0D803FE9138E001F8D8070F903801F003000ED98003 14FC121C12180038020713010030EDE000D8701F167C1260030F143CD8E03F163800C001 005B5BD8007E131F183001FE5C5B033F1470000117604991C7FCA218E000034A14C04913 7E17011880170318005F03FE1306170E000101015C01F801BF5B3B00FC039F8070903A7E 0F0FC0E0903A1FFC03FFC0902703F0007FC7FC36267EA43B>I<903907E001F090391FF8 07FC9039783E0E0F9039E01F1C1FD801C09038383F803A03800FF07F0100EBE0FF5A000E 4A1300000C157E021F133C001C4AC7FC1218A2C7123FA292C8FCA25CA2147EA214FEA24A 130CA20101141C001E1518003F5BD87F81143801835C00FF1560010714E03AFE0E7C01C0 D87C1C495A2778383E0FC7FC391FF00FFC3907C003F029267EA42F>I<13F8D803FE1470 D8070F14F8000EEB8001121C121800381403003015F0EA701F1260013F130700E0010013 E012C05BD8007E130F16C013FE5B151F000115805BA2153F000315005BA25D157EA315FE 5D1401000113033800F80790387C1FF8EB3FF9EB0FE1EB00035DA2000E1307D83F805B00 7F495AA24A5A92C7FCEB003E007C5B00705B6C485A381E07C06CB4C8FCEA01FC25367EA4 29>II E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fm cmti10 10 45 /Fm 45 123 df12 D<150C151C153815F0EC01E0EC03C0EC0780EC0F00141E5C147C5C5C495A1303 495A5C130F49C7FCA2133EA25BA25BA2485AA212035B12075BA2120F5BA2121FA290C8FC A25AA2123EA2127EA2127CA412FC5AAD1278A57EA3121C121EA2120E7EA26C7E6C7EA212 001E5274BD22>40 D<140C140E80EC0380A2EC01C015E0A2140015F0A21578A4157C153C AB157CA715FCA215F8A21401A215F0A21403A215E0A21407A215C0140F1580A2141F1500 A2143EA25CA25CA2495AA2495A5C1307495A91C7FC5B133E133C5B5B485A12035B48C8FC 120E5A12785A12C01E527FBD22>I44 D<387FFFF8A2B5FCA214F0150579941E>I<120EEA3F80127F12FFA31300127E123C0909 778819>I48 D50 D<16E0ED01F01503A3150716E0A3150F16C0A2151F1680A2ED3F00A3157EA2157C15FC5D 14015D14035D14075D140F5D141F92C7FC143EA25CECF81C153E903801F07EEB03E014C0 90380780FE130F49485A133EEB7C01137801F05BEA01E03803C003EA0FFE391FFFC3F048 13FB267C01FF13403AF0003FFFE000601307C71400EC0FE05DA3141F5DA3143F92C7FCA4 143E141C24487DB72A>52 D57 D65 D67 D<0103B612FEEFFFC018F0903B0007F8 000FF84BEB03FCEF00FE020F157FF03F804B141F19C0021F150F19E05D1807143F19F05D A2147FA292C8FCA25C180F5CA2130119E04A151FA2130319C04A153FA201071780187F4A 1600A2010F16FEA24A4A5A60011F15034D5A4A5D4D5A013F4B5A173F4A4AC7FC17FC017F EC03F84C5A91C7EA1FC04949B45A007F90B548C8FCB712F016803C397CB83F>I<0107B8 FCA3903A000FF000034BEB007F183E141F181E5DA2143FA25D181C147FA29238000380A2 4A130718004A91C7FC5E13015E4A133E167E49B512FEA25EECF8000107147C163C4A1338 A2010F147818E04A13701701011F16C016004A14031880013F150718004A5CA2017F151E 173E91C8123C177C4915FC4C5A4914070001ED7FF0B8FCA25F38397BB838>I<0103B512 F8A390390007F8005DA2140FA25DA2141FA25DA2143FA25DA2147FA292C7FCA25CA25CA2 1301A25CA21303A25CA21307A25CA2130FA25CA2131FA25CA2133FA25CA2137FA291C8FC 497EB6FCA25C25397CB820>73 D<0107B512FCA25E9026000FF8C7FC5D5D141FA25DA214 3FA25DA2147FA292C8FCA25CA25CA21301A25CA21303A25CA21307A25CA2130F170C4A14 1CA2011F153C17384A1478A2013F157017F04A14E01601017F140317C091C71207160F49 EC1F80163F4914FF000102071300B8FCA25E2E397BB834>76 D<902607FFF8923807FFF0 614F13E0D9000FEFF0004F5AA2021F167FF1EFC0141DDA1CFCEC01CF023C16DF9538039F 800238ED071FA20278ED0E3F97C7FC0270151CA202F04B5AF0707E14E0037E14E0010117 FE4D485A02C0EC0380A20103ED0701610280140EA20107ED1C0305385B14006F13704916 0705E05B010EEC01C0A2011E913803800F61011CEC0700A2013C020E131F4C5C1338ED1F B80178163F04F091C8FC01705CA201F04A5B187E00015DD807F816FEB500C09039007FFF FC151E150E4C397AB84A>I79 D<0107B612F817FF1880903B000FF0003FE04BEB0FF0EF03F814 1FEF01FC5DA2023F15FEA25DA2147FEF03FC92C7FCA24A15F817074A15F0EF0FE01301EF 1FC04AEC3F80EFFE0001034A5AEE0FF091B612C04CC7FCD907F8C9FCA25CA2130FA25CA2 131FA25CA2133FA25CA2137FA291CAFCA25BA25B1201B512FCA337397BB838>I<92383F C00E913901FFF01C020713FC91391FC07E3C91393F001F7C027CEB0FF84A130749481303 495A4948EB01F0A2495AA2011F15E091C7FCA34915C0A36E90C7FCA2806D7E14FCECFF80 6D13F015FE6D6D7E6D14E0010080023F7F14079138007FFC150F15031501A21500A2167C 120EA3001E15FC5EA3003E4A5AA24B5AA2007F4A5A4B5A6D49C7FC6D133ED8F9F013FC39 F8FC03F839F07FFFE0D8E01F138026C003FCC8FC2F3D7ABA2F>83 D<0007B812E0A25AD9F800EB001F01C049EB07C0485AD900011403121E001C5C003C1780 1403123800785C00701607140700F01700485CA2140FC792C7FC5DA2141FA25DA2143FA2 5DA2147FA292C9FCA25CA25CA21301A25CA21303A25CA21307A25CA2130FA25CEB3FF000 7FB512F8B6FCA2333971B83B>I<14F8EB07FE90381F871C90383E03FE137CEBF8011201 48486C5A485A120FEBC001001F5CA2EA3F801403007F5C1300A21407485C5AA2140F5D48 ECC1C0A2141F15831680143F1587007C017F1300ECFF076C485B9038038F8E391F0F079E 3907FE03FC3901F000F0222677A42A>97 D<133FEA1FFFA3C67E137EA313FE5BA312015B A312035BA31207EBE0F8EBE7FE9038EF0F80390FFC07C013F89038F003E013E0D81FC013 F0A21380A2123F1300A214075A127EA2140F12FE4814E0A2141F15C05AEC3F80A215005C 147E5C387801F8007C5B383C03E0383E07C0381E1F80D80FFEC7FCEA01F01C3B77B926> I<147F903803FFC090380FC1E090381F0070017E13784913383901F801F83803F0031207 13E0120FD81FC013F091C7FC485AA2127F90C8FCA35A5AA45AA3153015381578007C14F0 007EEB01E0003EEB03C0EC0F806CEB3E00380F81F83803FFE0C690C7FC1D2677A426>I< ED01F815FFA3150316F0A21507A216E0A2150FA216C0A2151FA21680A2153FA202F81300 EB07FE90381F877F90383E03FF017C5BEBF80112013803F00048485B120FEBC001121F5D EA3F801403127F01005BA214075A485CA2140FA248ECC1C0A2141F15C3ED8380143F1587 007C017F1300ECFF076C485B9038038F8E391F0F079E3907FE03FC3901F000F0253B77B9 2A>I<147F903803FFC090380FC1E090383F00F0017E13785B485A485A485A120F4913F8 001F14F0383F8001EC07E0EC1F80397F81FF00EBFFF891C7FC90C8FC5A5AA55AA2153000 7C14381578007E14F0003EEB01E0EC03C06CEB0F806CEB3E00380781F83803FFE0C690C7 FC1D2677A426>IIIII107 DI< D801E001FEEB07F03C07F803FF801FFC3C0E3C0F07C0783E3C1E3E3C03E1E01F261C1F78 D9F3C013803C383FF001F7800F02E01400007801C013FE007018C002805B4A4848EB1F80 EAF07FD8E07E5CA200000207143F01FE1700495CA2030F5C0001177E495C18FE031F5C12 0349DA8001131C18F8033F153C00070403133849020013F0A24B1570000F17E049017E15 F019E003FEECE1C0001FEE01E34949903800FF000007C70038143C3E2679A444>II<147F903803FFC090380FC1F090381F00F801 7E137C5B4848137E4848133E0007143F5B120F485AA2485A157F127F90C7FCA215FF5A48 14FEA2140115FC5AEC03F8A2EC07F015E0140F007C14C0007EEB1F80003EEB3F00147E6C 13F8380F83F03803FFC0C648C7FC202677A42A>I<9039078007C090391FE03FF090393C F0787C903938F8E03E9038787FC00170497EECFF00D9F0FE148013E05CEA01E113C15CA2 D80003143FA25CA20107147FA24A1400A2010F5C5E5C4B5A131F5EEC80035E013F495A6E 485A5E6E48C7FC017F133EEC70FC90387E3FF0EC0F8001FEC9FCA25BA21201A25BA21203 A25B1207B512C0A3293580A42A>II<3903 C003F0390FF01FFC391E783C0F381C7C703A3C3EE03F8038383FC0EB7F80007815000070 1300151CD8F07E90C7FCEAE0FE5BA2120012015BA312035BA312075BA3120F5BA3121F5B A3123F90C9FC120E212679A423>I<14FE903807FF8090380F83C090383E00E04913F001 78137001F813F00001130313F0A215E00003EB01C06DC7FC7FEBFFC06C13F814FE6C7F6D 13807F010F13C01300143F141F140F123E127E00FE1480A348EB1F0012E06C133E00705B 6C5B381E03E06CB45AD801FEC7FC1C267AA422>II<13F8D803FEEB01C0D8078FEB03E0390E0F8007121E121C0038 140F131F007815C01270013F131F00F0130000E015805BD8007E133FA201FE14005B5D12 0149137EA215FE120349EBFC0EA20201131E161C15F813E0163CD9F003133814070001EC F07091381EF8F03A00F83C78E090393FF03FC090390FC00F00272679A42D>I<01F0130E D803FC133FD8071EEB7F80EA0E1F121C123C0038143F49131F0070140FA25BD8F07E1400 00E08013FEC6485B150E12015B151E0003141C5BA2153C000714385B5DA35DA24A5A1403 00035C6D48C7FC0001130E3800F83CEB7FF8EB0FC0212679A426>I<01F01507D803FC90 3903801F80D8071E903907C03FC0D80E1F130F121C123C0038021F131F49EC800F007016 07A249133FD8F07E168000E0ED000313FEC64849130718000001147E5B03FE5B0003160E 495BA2171E00070101141C01E05B173C1738A217781770020314F05F0003010713016D48 6C485A000190391E7C07802800FC3C3E0FC7FC90393FF81FFE90390FE003F0322679A437 >I<13F0D803FCEB01C0D8071EEB03E0D80E1F1307121C123C0038140F4914C01270A249 131FD8F07E148012E013FEC648133F160012015B5D0003147E5BA215FE00075C5BA21401 5DA314035D14070003130FEBF01F3901F87FE038007FF7EB1FC7EB000F5DA2141F003F5C 48133F92C7FC147E147C007E13FC387001F8EB03E06C485A383C1F80D80FFEC8FCEA03F0 233679A428>121 D<903903C0038090380FF007D91FF81300496C5A017F130E9038FFFE 1E9038F83FFC3901F007F849C65A495B1401C7485A4A5A4AC7FC141E5C5C5C495A495A49 5A49C8FC131E5B49131C5B4848133C48481338491378000714F8390FF801F0391FFF07E0 383E1FFFD83C0F5B00785CD8700790C7FC38F003FC38E000F021267BA422>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fn cmr6 6 3 /Fn 3 53 df50 D<13FF000313C0380F03E038 1C00F014F8003E13FC147CA2001E13FC120CC712F8A2EB01F0EB03E0EB0FC03801FF00A2 380003E0EB00F01478147C143E143F1230127812FCA2143E48137E0060137C003813F838 1E03F0380FFFC00001130018227DA01E>I<14E01301A213031307A2130D131D13391331 136113E113C1EA01811203EA07011206120C121C12181230127012E0B6FCA2380001E0A6 EB03F0EB3FFFA218227DA11E>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fo cmmi9 9 2 /Fo 2 111 df 109 DI E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fp cmti9 9 32 /Fp 32 122 df45 D<161C163CA2167C16FCA215018215 03A2ED077E150F150E151CA21538A2157015F015E0EC01C0A2913803807F82EC0700A214 0E141E141C5CA25CA25C49B6FCA25B913880003F49C7EA1F80A2130E131E131C133C1338 5B13F05B12011203D80FF0EC3FC0D8FFFE903807FFFEA32F367BB539>65 D<0107B612C04915F017FC903A003F8000FE177FEF3F8092C7121FA24A15C0A2147EA214 FE18804A143FA20101ED7F00177E4A5C16010103EC03F04C5A4AEB1FC091B6C7FC495C91 39F0007F804AEB0FC0707E010F6E7E834A1301A2011F81A25CA2133F5F91C71203A2494A 5AA2017E4A5A4C5A01FE4A5A4CC7FC49EB01FE0001EC07FC007FB612F0B712C04BC8FC32 337BB236>II<0107B612C04915F017 FC903A003F8001FEEE007FEF1F8092C7EA0FC0EF07E05CEF03F0147E170102FE15F8A25C A21301A25CA2130317035CA2130718F04A1407A2130F18E04A140F18C0011F151F18805C EF3F00133F177E91C85AA2494A5A4C5A017E4A5A4C5A01FE4A5A047EC7FC49495A0001EC 0FF8007FB612E0B7C8FC15F835337BB23A>I<92391FE001809238FFF8030207EBFE0791 3A1FF01F0F0091393F80079F9139FE0003DFD901F86DB4FCD907F05C49481300495A4948 147E49C8127C137E13FE485A48481578A2485AA248481570A2485A94C7FC123F5BA3127F 90CBFCA400FE91383FFFFCA25F9238003F8094C7FCA2007E5DA2167EA2007F15FE7E5E6C 6C1301A26C6C495A6D13076C6CEB0F786C6C133E3A00FF01FC3090387FFFF0011F01C0C8 FCD903FEC9FC313775B43B>71 D<010FB51280A216009038003FC05DA292C7FCA25CA214 7EA214FEA25CA21301A25CA21303A25CA21307A25CA2130FA25CA2131FA25CA2133FA291 C8FCA25BA2137EA213FEA25B1201B512F8A25C21337BB21E>73 D<91381FFFFE5C16FC91 38003F80A31600A25D157EA315FE5DA314015DA314035DA314075DA3140F5DA3141F5DA3 143F92C7FCA2121C007E5B00FE137EA214FE485BEAF80100E05B495A387007E038780FC0 6C48C8FCEA1FFCEA07F0273579B228>I<0107B512C05BA29026003FC0C7FC5DA292C8FC A25CA2147EA214FEA25CA21301A25CA21303A25CA21307A25CA2130FA25C17E0011F1401 17C05C1603013F1580160791C7FCEE0F005B5E017E143EA201FE5CED01FC4913030001EC 1FF8007FB6FCB7FC5E2B337CB230>76 D<902607FFC0ED7FFC4917FF81D9003F4B130061 1803023BED077CA2027BED0EFC610273151C1838DAF1F01439F071F014E118E10101ED01 C36102C1EC0383EF070301031607050E5BEC80F8171C0107ED380F6102001470A249EDE0 1FDC01C090C7FC130EEE0380011E017C5C933807003E011C140EA2013C4A137E187C0138 5C5E017816FC6F485B1370ED3FC001F0EC80016000011500D807F81503277FFF803E90B5 12C0B5EB3C01151C46337BB245>I<0107B612C04915F883903A003F8001FEEE003FEF1F 8092C713C0170F5C18E0147EA214FEEF1FC05CA201011680173F4A1500177E010315FE5F 4AEB03F8EE07E00107EC3FC091B6C7FC16F802E0C9FC130FA25CA2131FA25CA2133FA291 CAFCA25BA2137EA213FEA25B1201387FFFF0B5FCA233337CB234>80 D<913901FC018091380FFF03023F13C791387E07EF903A01F801FF0049487E4A7F495A49 48133E131F91C7FC5B013E143CA3137E1638A293C7FC137FA26D7E14E014FE90381FFFC0 6D13F86D7F01017F6D6C7E020F7F1400153F6F7E150FA4120EA2001E5D121CA2151F003C 92C7FCA2003E143E5D127E007F5C6D485A9038C007E039F3F80FC000F0B5C8FC38E03FFC 38C00FF029377AB42B>83 D<0003B812C05A1880903AF800FC003F260FC001141F018015 0F01005B001EEE07001403121C003C4A5BA200380107140E127800705CA2020F141E00F0 161CC74990C7FCA2141FA25DA2143FA292C9FCA25CA2147EA214FEA25CA21301A25CA213 03A25CA21307A25C497E001FB512F05AA2323374B237>I97 D<137EEA0FFE121F5B1200A35BA21201A25BA21203A25BA21207A2EBC3E0EBCFF8380FDC 3EEBF81F497E01E01380EA1FC0138015C013005AA2123EA2007E131F1580127CA2143F00 FC14005AA2147EA25CA2387801F85C495A6C485A495A6C48C7FCEA0FFCEA03F01A3578B3 23>I<14FCEB07FF90381F078090383E03C0EBFC013801F8033803F0073807E00F13C012 0F391F80070091C7FC48C8FCA35A127EA312FE5AA4007C14C0EC01E0A2EC03C06CEB0F80 EC1F006C137C380F81F03803FFC0C648C7FC1B2278A023>III<151FED7FC0EDF0E0020113F0EC03E3A2EC07C316E0ED C1C091380FC0005DA4141F92C7FCA45C143E90381FFFFEA3D9007EC7FC147CA414FC5CA5 13015CA413035CA413075CA3130FA25CA3131F91C8FCA35B133E1238EA7E3CA2EAFE7812 FC485AEA78E0EA3FC0000FC9FC244582B418>I<143FECFF80903803E1E6903807C0FF90 380F807FEB1F00133E017E133F49133EA24848137EA24848137CA215FC12074913F8A214 01A2D80FC013F0A21403120715E01407140F141F3903E03FC00001137FEBF0FF38007FCF 90381F0F801300141FA21500A25C143E1238007E137E5C00FE5B48485A387803E0387C0F 80D81FFFC7FCEA07F820317CA023>III<133F EA07FF5A13FEEA007EA3137CA213FCA213F8A21201A213F0A21203A213E0A21207A213C0 A2120FA21380A2121FA21300A25AA2123EA2127EA2127C1318EAFC1C133CEAF838A21378 137012F013F0EAF8E01279EA3FC0EA0F00103579B314>108 D<2703C003F8137F3C0FF0 0FFE01FFC03C1E783C1F07C1E03C1C7CF00F8F01F03B3C3DE0079E0026383FC001FC7FD9 7F805B007001005B5E137ED8F0FC90380FC00100E05FD860F8148012000001021F130360 491400A200034A13076049013E130FF081800007027EEC83C0051F138049017C1403A200 0F02FC1407053E130049495CEF1E0E001F01015D183C010049EB0FF0000E6D48EB03E03A 227AA03F>I<3903C007F0390FF01FFC391E787C1E391C7CF01F393C3DE00F26383FC013 80EB7F8000781300EA707EA2D8F0FC131F00E01500EA60F8120000015C153E5BA2000314 7E157C4913FCEDF8180007153C0201133801C013F0A2000F1578EDE070018014F016E000 1FECE1C015E390C7EAFF00000E143E26227AA02B>I<14FCEB07FF90381F07C090383E03 E09038FC01F0EA01F83903F000F8485A5B120F484813FCA248C7FCA214014814F8127EA2 140300FE14F05AA2EC07E0A2007CEB0FC01580141FEC3F006C137E5C381F01F0380F83E0 3803FF80D800FCC7FC1E2278A027>I<011E137C90387F81FF9039F3C387C09039E3EF03 E03901E1FE01D9C1FC13F0EBC3F8000313F0018314F814E0EA07871307000313C0120001 0F130316F01480A2011F130716E01400A249EB0FC0A2013EEB1F80A2017EEB3F00017F13 3E5D5D9038FF81F09038FDC3E09038F8FF80027EC7FC000190C8FCA25BA21203A25BA212 07A25BB5FCA325307FA027>I<3903C00FC0390FF03FF0391E78F078391C7DE03C393C3F C0FC00381380EB7F00007814F8D8707E13701500EAF0FC12E0EA60F812001201A25BA212 03A25BA21207A25BA2120FA25BA2121FA290C8FC120E1E227AA020>114 DI<1303EB0F80A3131FA214 00A25BA2133EA2137EA2137C387FFFF8A2B5FC3800F800A21201A25BA21203A25BA21207 A25BA2120FA25B1460001F13F014E01300130114C01303001E1380EB07005BEA0F1EEA07 F8EA01E015307AAE19>II<13F0D803FC1307D80F1E130F000E14 1F121C123C0038143FD8783E133E1270A2017E137ED8F07C137CEA60FCC65A15FC000114 F85BA21401000314F013E0A2140315E0EA07C0A20003130715C0EBE00F141F0001133F90 38F07F8038007FEFEB1F8FEB001F1500A25C003E133E007E137E147C5C007C5BEA700149 5A38380780D83C1FC7FCEA0FFCEA07F020317AA025>121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fq cmr9 9 67 /Fq 67 123 df<91393FE00FE0903A01FFF83FF8903A07E01EF83C903A1F800FF07E903A 3F001FE0FE017E133F4914C0485A1738484890381F8000ACB812C0A33B03F0001F8000B3 A7486C497EB50083B5FCA32F357FB42D>11 D14 D<127812FCA27E7EEA7F80121FEA0FC0EA07E01203EA00F01378 133C13080E0E78B326>18 D<14C01301EB0380EB0F00130E5B133C5B5BA2485A485AA212 075B120F90C7FC5AA2121E123EA3123C127CA55AB0127CA5123C123EA3121E121FA27E7F 12077F1203A26C7E6C7EA213787F131C7F130FEB0380EB01C01300124A79B71E>40 D<12C07E1270123C121C7E120F6C7E6C7EA26C7E6C7EA27F1378137C133C133EA2131E13 1FA37F1480A5EB07C0B0EB0F80A514005BA3131E133EA2133C137C137813F85BA2485A48 5AA2485A48C7FC120E5A123C12705A5A124A7CB71E>I<156015F0B3A4007FB812C0B912 E0A26C17C0C800F0C8FCB3A4156033327CAB3C>43 D<123C127EB4FCA21380A2127F123D 1201A412031300A25A1206120E120C121C5A5A126009177A8715>II<123C127E12FFA4127E123C08087A8715>I48 D<13075B5B137FEA07FFB5FC13BFEAF83F1200B3B3A2497E007F B51280A319327AB126>IIII<000C14C0380FC00F90B5128015005C5C14F014 C0D80C18C7FC90C8FCA9EB0FC0EB7FF8EBF07C380FC03F9038001F80EC0FC0120E000CEB 07E0A2C713F01403A215F8A41218127E12FEA315F0140712F8006014E01270EC0FC06C13 1F003C14806CEB7F00380F80FE3807FFF8000113E038003F801D347CB126>I<14FE9038 07FF80011F13E090383F00F0017C13703901F801F8EBF003EA03E01207EA0FC0EC01F048 48C7FCA248C8FCA35A127EEB07F0EB1FFC38FE381F9038700F809038E007C039FFC003E0 018013F0EC01F8130015FC1400A24814FEA5127EA4127F6C14FCA26C1301018013F8000F 14F0EBC0030007EB07E03903E00FC03901F81F806CB51200EB3FFCEB0FE01F347DB126> I<1230123C003FB6FCA34814FEA215FC0070C7123800601430157015E04814C01401EC03 80C7EA07001406140E5C141814385CA25CA2495A1303A3495AA2130FA3131F91C7FCA25B A55BA9131C20347CB126>III<123C127E12FFA4127E123C1200B0123C127E12FE12FFA312 7F123F1203A412071206A3120E120C121C1238123012701260082F7A9F15>59 D<15E0A34A7EA24A7EA34A7EA3EC0DFE140CA2EC187FA34A6C7EA202707FEC601FA202E0 7FECC00FA2D901807F1507A249486C7EA301066D7EA2010E80010FB5FCA249800118C77E A24981163FA2496E7EA3496E7EA20001821607487ED81FF04A7ED8FFFE49B512E0A33336 7DB53A>65 DIIIIIIII<017FB5FCA3 9038003FE0EC1FC0B3B1127EB4FCA4EC3F805A0060140000705B6C13FE6C485A380F03F0 3803FFC0C690C7FC20357DB227>I76 DI79 DI82 D<90381FE00390387FFC0748B5FC3907F01FCF390F8003FF48C7 FC003E80814880A200788000F880A46C80A27E92C7FC127F13C0EA3FF013FF6C13F06C13 FF6C14C06C14F0C680013F7F01037F9038003FFF140302001380157F153FED1FC0150F12 C0A21507A37EA26CEC0F80A26C15006C5C6C143E6C147E01C05B39F1FC03F800E0B512E0 011F138026C003FEC7FC22377CB42B>I<007FB712FEA390398007F001D87C00EC003E00 78161E0070160EA20060160600E01607A3481603A6C71500B3AB4A7E011FB512FCA33033 7DB237>I86 DI91 D93 D97 DII<153FEC0FFFA3 EC007F81AEEB07F0EB3FFCEBFC0F3901F003BF3907E001FF48487E48487F8148C7FCA25A 127E12FEAA127E127FA27E6C6C5BA26C6C5B6C6C4813803A03F007BFFC3900F81E3FEB3F FCD90FE0130026357DB32B>III<151F90391FC07F809039 FFF8E3C03901F07FC73907E03F033A0FC01F83809039800F8000001F80EB00074880A66C 5CEB800F000F5CEBC01F6C6C48C7FCEBF07C380EFFF8380C1FC0001CC9FCA3121EA2121F 380FFFFEECFFC06C14F06C14FC4880381F0001003EEB007F4880ED1F8048140FA56C141F 007C15006C143E6C5C390FC001F83903F007E0C6B51280D91FFCC7FC22337EA126>IIIIII<2703F01FE0 13FF00FF90267FF80313C0903BF1E07C0F03E0903BF3803E1C01F02807F7003F387FD803 FE1470496D486C7EA2495CA2495CB3486C496C487EB53BC7FFFE3FFFF0A33C217EA041> I<3903F01FC000FFEB7FF09038F1E0FC9038F3807C3907F7007EEA03FE497FA25BA25BB3 486CEB7F80B538C7FFFCA326217EA02B>II<3903F03F8000FFEBFFE09038F3C0F89038F7007ED807FE7F6C48EB1F80 4914C049130F16E0ED07F0A3ED03F8A9150716F0A216E0150F16C06D131F6DEB3F801600 01FF13FC9038F381F89038F1FFE0D9F07FC7FC91C8FCAA487EB512C0A325307EA02B>I< 903807F00390383FFC07EBFC0F3901F8038F3807E001000F14DF48486CB4FC497F123F90 C77E5AA25A5AA9127FA36C6C5B121F6D5B000F5B3907E003BF3903F0073F3800F81EEB3F F8EB0FE090C7FCAAED7F8091380FFFFCA326307DA029>I<3803E07C38FFE1FF9038E38F 809038E71FC0EA07EEEA03ECA29038FC0F8049C7FCA35BB2487EB512E0A31A217FA01E> II<1330A51370A313F0A21201 A212031207381FFFFEB5FCA23803F000AF1403A814073801F806A23800FC0EEB7E1CEB1F F8EB07E0182F7FAD1E>IIIII<3A7FFF807FF8A33A07F8001FC00003 EC0F800001EC070015066C6C5BA26D131C017E1318A26D5BA2EC8070011F1360ECC0E001 0F5BA2903807E180A214F3010390C7FC14FBEB01FEA26D5AA31478A21430A25CA214E05C A2495A1278D8FC03C8FCA21306130EEA701CEA7838EA1FF0EA0FC025307F9F29>I<003F B512F0A2EB000F003C14E00038EB1FC00030EB3F800070137F1500006013FE495A13035C C6485A495AA2495A495A49C7FC153013FE485A12035B48481370485A001F14604913E048 5A387F000348130F90B5FCA21C207E9F22>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fr cmbx10 10 42 /Fr 42 123 df<913803FFC0027F13F00103B512FC010FEB00FED93FF8133FD97FE0EBFF 8049485A5A1480484A13C04A6C1380A36F1300167E93C7FCA592383FFFC0B8FCA4000390 C7FCB3ABB5D8FC3F13FFA4303A7EB935>12 D<141C143C14F8EB01F0EB03E01307EB0FC0 EB1F8014005B137E13FE5B12015B1203A2485AA2120F5B121FA25B123FA4485AA512FFB1 127FA56C7EA4121F7FA2120F7F1207A26C7EA212017F12007F137E7F7F1480EB0FC0EB07 E01303EB01F0EB00F8143C141C165377BD25>40 D<12E07E127C7E7E7F6C7E6C7E12037F 6C7E7F12007F137E137FA2EB3F80A214C0131F14E0A2130F14F0A4EB07F8A514FCB114F8 A5EB0FF0A414E0131FA214C0133F1480A2EB7F00A2137E13FE5B12015B485A5B1207485A 485A90C7FC123E5A12F05A16537BBD25>I43 D45 D<141E143E14FE1307133FB5FCA313CFEA000FB3B3A6007FB61280A4213779B630>49 DIII<001C15C0D81F80 130701F8137F90B61280A216005D5D15F05D15804AC7FC14F090C9FCA8EB07FE90383FFF E090B512F89038FC07FC9038E003FFD98001138090C713C0120EC813E0157F16F0A216F8 A21206EA3F80EA7FE012FF7FA44914F0A26C4813FF90C713E0007C15C06C5B6C491380D9 C0071300390FF01FFE6CB512F8000114E06C6C1380D90FF8C7FC25387BB630>II65 D67 D70 D73 D77 D79 DI82 D97 D<13FFB5FCA412077EAF4AB47E02 0F13F0023F13FC9138FE03FFDAF00013804AEB7FC00280EB3FE091C713F0EE1FF8A217FC 160FA217FEAA17FCA3EE1FF8A217F06E133F6EEB7FE06E14C0903AFDF001FF80903AF8FC 07FE009039F03FFFF8D9E00F13E0D9C00390C7FC2F3A7EB935>I<903801FFC0010F13FC 017F13FFD9FF8013802603FE0013C048485AEA0FF8121F13F0123F6E13804848EB7F0015 1C92C7FC12FFA9127FA27F123FED01E06C7E15036C6CEB07C06C6C14806C6C131FC69038 C07E006DB45A010F13F00101138023257DA42A>II<903803FF80011F13F0017F13FC3901FF83FE3A03 FE007F804848133F484814C0001FEC1FE05B003FEC0FF0A2485A16F8150712FFA290B6FC A301E0C8FCA4127FA36C7E1678121F6C6C14F86D14F000071403D801FFEB0FE06C9038C0 7FC06DB51200010F13FC010113E025257DA42C>II<161FD907FEEBFFC090387FFFE348B6EAEFE026 07FE07138F260FF801131F48486C138F003F15CF4990387FC7C0EEC000007F81A6003F5D A26D13FF001F5D6C6C4890C7FC3907FE07FE48B512F86D13E0261E07FEC8FC90CAFCA212 3E123F7F6C7E90B512F8EDFF8016E06C15F86C816C815A001F81393FC0000F48C8138048 157F5A163FA36C157F6C16006D5C6C6C495AD81FF0EB07FCD807FEEB3FF00001B612C06C 6C91C7FC010713F02B377DA530>I<13FFB5FCA412077EAFED7FC0913803FFF8020F13FE 91381F03FFDA3C01138014784A7E4A14C05CA25CA291C7FCB3A3B5D8FC3F13FFA4303A7D B935>II<13FFB5FCA412077EAF92380FFFE0A4923803FC0016F0ED0F E0ED1F804BC7FC157E5DEC03F8EC07E04A5A141FEC7FE04A7E8181A2ECCFFEEC0FFF496C 7F806E7F6E7F82157F6F7E6F7E82150F82B5D8F83F13F8A42D3A7EB932>107 D<13FFB5FCA412077EB3B3ACB512FCA4163A7DB91B>I<01FED97FE0EB0FFC00FF902601 FFFC90383FFF80020701FF90B512E0DA1F81903983F03FF0DA3C00903887801F000749DA CF007F00034914DE6D48D97FFC6D7E4A5CA24A5CA291C75BB3A3B5D8FC1FB50083B512F0 A44C257DA451>I<01FEEB7FC000FF903803FFF8020F13FE91381F03FFDA3C0113800007 13780003497E6D4814C05CA25CA291C7FCB3A3B5D8FC3F13FFA430257DA435>I<903801 FFC0010F13F8017F13FFD9FF807F3A03FE003FE048486D7E48486D7E48486D7EA2003F81 491303007F81A300FF1680A9007F1600A3003F5D6D1307001F5DA26C6C495A6C6C495A6C 6C495A6C6C6CB45A6C6CB5C7FC011F13FC010113C029257DA430>I<9039FF01FF80B500 0F13F0023F13FC9138FE07FFDAF00113800007496C13C06C0180EB7FE091C713F0EE3FF8 A2EE1FFCA3EE0FFEAA17FC161FA217F8163F17F06E137F6E14E06EEBFFC0DAF003138091 39FC07FE0091383FFFF8020F13E0020390C7FC91C9FCACB512FCA42F357EA435>I<9038 FE03F000FFEB0FFEEC3FFF91387C7F809138F8FFC000075B6C6C5A5CA29138807F80ED3F 00150C92C7FC91C8FCB3A2B512FEA422257EA427>114 D<90383FF0383903FFFEF8000F 13FF381FC00F383F0003007E1301007C130012FC15787E7E6D130013FCEBFFE06C13FCEC FF806C14C06C14F06C14F81203C614FC131F9038007FFE140700F0130114007E157E7E15 7C6C14FC6C14F8EB80019038F007F090B512C000F8140038E01FF81F257DA426>I<130F A55BA45BA25B5BA25A1207001FEBFFE0B6FCA3000390C7FCB21578A815F86CEB80F01481 6CEBC3E090383FFFC06D1380903803FE001D357EB425>I<01FFEC3FC0B5EB3FFFA40007 14016C80B3A35DA25DA26C5C6E4813E06CD9C03E13FF90387FFFFC011F13F00103138030 257DA435>III121 D<003FB612C0A3D9F00313 80EB800749481300003E5C003C495A007C133F5D0078495A14FF5D495B5BC6485B92C7FC 495A131F5C495A017FEB03C0EBFFF014E04813C05AEC80074813005A49EB0F80485A003F 141F4848133F9038F001FFB7FCA322257DA42A>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fs cmsy8 8 3 /Fs 3 123 df120 D<1338137CA81338A7007C137CB512FEA338 7C387C00001300A5137CB3A41338AD173D7CAE20>I<1338137CA71338A40020130838FF 39FE13FFA2133938003800A5137CA7133890C7FC1338137CA71338A538FF39FE13FFA213 393820380800001300A4137CA71338173D7CAE20>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Ft cmr12 12 18 /Ft 18 122 df<121EEA7F80A2EAFFC0A4EA7F80A2EA1E000A0A78891B>46 D66 D72 D<010FB512FEA3D90003 13806E130080B3B3AB123F487E487EA44A5A13801300006C495A00705C6C13076C5C6C49 5A6CEB1F802603E07FC7FC3800FFFCEB1FE027467BC332>74 D82 D<49B41303010FEBE007013F13F89039FE00FE0FD801F8131FD807E0EB079F49EB03DF48 486DB4FC48C8FC4881003E81127E82127C00FC81A282A37E82A27EA26C6C91C7FC7F7FEA 3FF813FE381FFFE06C13FE6CEBFFE06C14FC6C14FF6C15C0013F14F0010F80010180D900 1F7F14019138001FFF03031380816F13C0167F163F161F17E000C0150FA31607A37EA36C 16C0160F7E17806C151F6C16006C5D6D147ED8FBC05CD8F9F0495AD8F07C495A90393FC0 0FE0D8E00FB51280010149C7FC39C0003FF02B487BC536>I97 D<167FED3FFFA315018182B3EC7F80 903803FFF090380FC07C90383F000E017E1307496D5AD803F87F48487F5B000F81485AA2 485AA2127FA290C8FC5AAB7E7FA2123FA26C7EA2000F5D7F6C6C5B00035C6C6C9038077F 806C6C010E13C0013F011C13FE90380FC0F8903803FFE09026007F0013002F467DC436> 100 DI104 D I109 D<3901FC01FE00FF903807FFC091381E07F091383801F8000701707F0003EBE0002601FD C07F5C01FF147F91C7FCA25BA35BB3A8486CECFF80B5D8F83F13FEA32F2C7DAB36>I<39 01FC03FC00FF90380FFF8091383C07E091387001F83A07FDE000FE00030180137FD801FF EC3F8091C7EA1FC04915E049140F17F0160717F8160317FCA3EE01FEABEE03FCA3EE07F8 A217F0160F6D15E0EE1FC06D143F17806EEB7E00D9FDC05B9039FCF003F891383C0FE091 381FFF80DA03FCC7FC91C9FCAE487EB512F8A32F3F7DAB36>112 D<3903F803F000FFEB1FFCEC3C3EEC707F0007EBE0FF3803F9C000015B13FBEC007E153C 01FF13005BA45BB3A748B4FCB512FEA3202C7DAB26>114 D<1306A5130EA4131EA3133E 137EA213FE12011207001FB512F0B6FCA2C648C7FCB3A4150CAA017E131C017F1318A26D 133890381F8030ECC070903807E0E0903801FFC09038007F001E3E7EBC26>116 D119 D121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fu cmsy10 12 1 /Fu 1 4 df<147014F8A81470007815F0007C1401B4EC07F8D87F80EB0FF0D83FE0EB3F E0D80FF0EB7F80D803F8EBFE003900FE73F890383F77E090380FFF80D903FEC7FCEB00F8 EB03FE90380FFF8090383F77E09038FE73F83903F870FED80FF0EB7F80D83FE0EB3FE0D8 7F80EB0FF0D8FF00EB07F8007CEC01F000781400C7140014F8A81470252B7AAD32>3 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fv cmr17 17.28 22 /Fv 22 122 df<170FA34D7EA24D7EA34D7EA34D7EA34C7F17DFA29338039FFC178FA293 38070FFE1707040F7FEE0E03A2041E80EE1C01A2043C80EE3800A24C80187FA24C80183F A24B4880181F0303814C130FA203078193C71207A24B81030E80A24B8284A24B8284A24B 82197F03F0824B153FA20201834B151FA202038392B8FCA24A83A292C91207020E8385A2 4A8485023C84023882A20278840270177FA202F0844A173FA24948841A1FA24948841A0F A249CB7F1A074985865B496C85497E48486C4D7F000F01F8051F13F0B60407B612F0A45C 657DE463>65 D67 D71 DI87 D97 D<181EEF3FFEEE07FFA4EE000F1703A21701B3AAEDFF80020F13F802 3F13FE9139FF803F81903A03FC0007C14948EB01E1D91FE0EB00F94948147D4948143D49 C8121F4848150F491507120348481503491501120F121F5BA2123F5B127FA45B12FFAD12 7F7FA3123FA27F121FA26C6C1503A26C6C150712036D150F6C6C151F0000163D137F6D6C ECF9FF6D6CEB01F1D90FF0D903C113C06D6CD90F81EBFF80D901FFEB7F019039007FFFFC 021F13E00201010091C7FC41657CE349>100 DI 103 DI<133C13FF 487F487FA66C5B6C90C7FC133C90C8FCB3A2EB03C0EA07FF127FA41201EA007FA2133FB3 B3AC497E497EB612E0A41B5F7DDE23>I 107 DIIII< D903C0EB7FC0D807FF903807FFFCB5011F13FFDB7F0013C003F8EB1FF0DAC3E0EB07F800 01D9C7806D7E26007FCFC76C7E02DE6E7ED93FFC6F7E4A6F7E4A82181F4A82727E5C727E A2727EA3727EA41A8084AC4E1300A54E5AA2611807A24E5A6E5E181F6E4B5A6E5E187F6E 4B5A02DE4A90C7FC02CF4A5ADAC780495ADAC3C0EB0FF0DAC1F0EB3FE0913AC07E01FF80 6FB448C8FC030F13F80300138093CAFCB3A3497E497EB612F0A4415B7DBE49>I<903907 8003F8D807FFEB0FFFB5013F13C092387C0FE0913881F01F9238E03FF00001EB83803900 7F8700148FEB3F8E029CEB1FE0EE0FC00298EB030002B890C7FCA214B014F0A25CA55CB3 B0497EEBFFF8B612FCA42C3F7CBE33>114 D<9139FFE00180010FEBFC03017FEBFF073A 01FF001FCFD803F8EB03EFD807E0EB01FF48487F4848147F48C8123F003E151F007E150F 127CA200FC1507A316037EA27E7F6C7E6D91C7FC13F8EA3FFE381FFFF06CEBFF806C14F8 6C14FF6C15C06C6C14F0011F80010714FED9007F7F02031480DA003F13C01503030013E0 167F00E0ED1FF0160F17F86C15071603A36C1501A37EA26C16F016037E17E06D14076DEC 0FC06D1580D8FDF0141FD8F8F8EC7F00013E14FC3AF01FC00FF80107B512E0D8E0011480 27C0003FF8C7FC2D417DBF34>I<1438A71478A414F8A31301A31303A21307130F131FA2 137F13FF1203000F90B6FCB8FCA3260007F8C8FCB3AE17E0AE6D6CEB01C0A316036D6C14 8016076D6C14006E6C5A91383FC01E91381FF07C6EB45A020313E09138007F802B597FD7 33>I118 D121 D E %EndDVIPSBitmapFont end %%EndProlog %%BeginSetup %%Feature: *Resolution 600dpi TeXDict begin %%BeginPaperSize: Letter letter %%EndPaperSize %%EndSetup %%Page: 42 1 42 0 bop 790 789 a Fv(W)-11 b(eakly)43 b(Chordal)h(Graph)f(Algorithms)h (via)g(Handles)3526 737 y Fu(\003)861 1029 y Ft(Ry)m(an)33 b(B.)g(Ha)m(yw)m(ard)1624 993 y Fs(y)1940 1029 y Ft(Jerem)m(y)h (Spinrad)2609 993 y Fs(z)2924 1029 y Ft(R.)e(Sritharan)3457 993 y Fs(x)116 1355 y Fr(Abstract)116 1479 y Fq(W)-6 b(e)50 b(use)g(the)f(notion)h(of)h Fp(hand)t(le)p Fq(,)57 b(in)n(tro)r(duced)49 b(b)n(y)g(Ha)n(yw)n(ard,)116 1579 y(to)f(impro)n(v)n(e)f(algorithms)i(for)g(w)n(eakly)f(c)n(hordal)h (graphs.)102 b(F)-6 b(or)116 1679 y(recognition)28 b(w)n(e)f(reduce)f (the)g(time)g(complexit)n(y)f(from)h(O\()p Fo(n)1890 1647 y Fn(2)1925 1679 y Fo(m)p Fq(\))g(to)116 1778 y(O\()p Fo(m)274 1747 y Fn(2)308 1778 y Fq(\))i(and)g(the)h(space)g(complexit)n (y)e(from)h(O\()p Fo(n)1575 1747 y Fn(3)1610 1778 y Fq(\))g(to)h(O\()p Fo(n)19 b Fq(+)f Fo(m)p Fq(\),)116 1878 y(and)36 b(also)i(pro)r(duce)e (a)g(hole)h(or)f(an)n(tihole)h(if)g(the)f(input)f(graph)h(is)116 1978 y(not)31 b(w)n(eakly)g(c)n(hordal.)51 b(F)-6 b(or)31 b(the)f(optimization)h(problems)g(clique,)116 2077 y(indep)r(enden)n(t) 19 b(set,)j(coloring,)h(and)c(clique)h(co)n(v)n(ering,)i(w)n(e)f (reduce)e(the)116 2177 y(time)25 b(complexit)n(y)g(from)g(O\()p Fo(n)999 2145 y Fn(4)1034 2177 y Fq(\))g(to)h(O\()p Fo(nm)p Fq(\).)116 476 y Fm(Pr)l(o)l(c)l(e)l(e)l(dings)31 b(of)f(the)g (Eleventh)h(A)n(nnual)e(A)n(CM-SIAM)g(Symp)l(osium)h(on)g(Discr)l(ete)g (A)n(lgorithms)g(\(2000\))i(pp)e(42-49)116 2575 y Fr(1)95 b(In)m(tro)s(duction)33 b(and)f(Motiv)-5 b(ation)116 2700 y Fl(P)169 2712 y Fk(k)249 2700 y Fj(and)39 b Fl(C)481 2712 y Fk(k)561 2700 y Fj(denote)g(resp)r(ectiv)n(ely)f(the)h(induced)g (path)g(and)116 2800 y(cycle)32 b(with)g Fl(k)j Fj(v)n(ertices.)p 942 2733 66 4 v 48 w Fl(C)1008 2812 y Fk(k)1080 2800 y Fj(is)d(the)g(complemen)n(t)g(of)g Fl(C)1941 2812 y Fk(k)1982 2800 y Fj(.)50 b(A)116 2899 y Fm(hole)32 b Fj(is)f(an)f(induced)h(cycle)g(with)g(\014v)n(e)f(or)g(more)g(v)n (ertices)f(and)116 2999 y(an)f Fm(antihole)j Fj(is)d(the)h(complemen)n (t)f(of)h(a)f(hole.)40 b(W)-7 b(e)28 b(use)h Fl(n)f Fj(and)116 3098 y Fl(m)j Fj(resp)r(ectiv)n(ely)f(for)h(the)g(n)n(um)n(b)r(er)g(of) f(v)n(ertices)g(and)h(edges)f(of)116 3198 y(a)37 b(graph.)65 b Fm(Se)l(es)37 b Fj(and)g Fm(misses)g Fj(mean)g(\\is)g(adjacen)n(t)g (to")f(and)116 3298 y(\\is)f(not)h(adjacen)n(t)g(to")f(resp)r(ectiv)n (ely)-7 b(.)60 b(A)37 b(v)n(ertex)d Fm(misses)k(an)116 3397 y(e)l(dge)29 b Fj(if)g(it)f(misses)g(b)r(oth)g(v)n(ertices)f(of)h (the)g(edge.)38 b(F)-7 b(or)28 b(a)f(subset)116 3497 y Fl(S)46 b Fj(of)41 b(the)h(v)n(ertex)e(set)h Fl(V)19 b Fj(\()p Fl(G)p Fj(\))42 b(of)f(a)g(graph)f Fl(G)p Fj(,)k Fl(G)p Fj([)p Fl(S)5 b Fj(])42 b(is)f(the)116 3597 y(subgraph)30 b(induced)i(b)n(y)e Fl(S)36 b Fj(and)31 b Fl(N)9 b Fj(\()p Fl(S)c Fj(\))31 b(is)g(the)g(neigh)n(b)r(orho)r(o)r(d)116 3696 y(of)h Fl(S)5 b Fj(,)32 b(namely)f(the)g(v)n(ertices)g(of)g Fl(V)19 b Fj(\()p Fl(G)p Fj(\))j Fi(\000)e Fl(S)36 b Fj(whic)n(h)c(see)f(some)116 3796 y(v)n(ertex)c(of)g Fl(S)5 b Fj(.)266 3895 y(A)25 b(graph)g(is)g Fm(we)l(akly)k(chor)l(dal) e Fj(\(also)e(called)g(w)n(eakly)f(trian-)116 3995 y(gulated\))d(if)f (it)h(con)n(tains)f(no)g(holes)g(and)g(no)g(an)n(tiholes.)34 b(W)-7 b(eakly)116 4095 y(c)n(hordal)32 b(graphs,)h(in)n(tro)r(duced)g (b)n(y)g(Ha)n(yw)n(ard)f([2)o(],)j(are)e(a)f(w)n(ell)116 4194 y(studied)i(class)e(of)h(p)r(erfect)g(graphs.)52 b(Ha)n(yw)n(ard,)33 b(Ho\022)-42 b(ang,)33 b(and)116 4294 y(Ma\013ra)n(y)43 b(c)n(haracterized)f(w)n(eakly)h(c)n(hordal)g (graphs)f(via)i(the)116 4394 y(presence)39 b(of)g(a)g Fm(two-p)l(air)p Fj(,)k(namely)c(a)g(pair)g(of)g(nonadjacen)n(t)116 4493 y(v)n(ertices)21 b(suc)n(h)h(that)h(ev)n(ery)e(induced)i(path)f(b) r(et)n(w)n(een)h(them)g(has)116 4593 y(exactly)k(t)n(w)n(o)g(edges.)36 b(Their)27 b(theorem)g(is:)116 4774 y Fh(Theorem)32 b(1.1.)40 b Fj([5])23 b Fm(A)f(gr)l(aph)i(is)f(we)l(akly)g(chor)l(dal)i(if)e(and) g(only)116 4873 y(if)29 b(e)l(ach)g(induc)l(e)l(d)g(sub)l(gr)l(aph)g (either)g(is)f(a)h(clique)g(or)f(c)l(ontains)h(a)116 4973 y(two-p)l(air)i(of)g(the)e(sub)l(gr)l(aph.)p 116 5206 250 4 v 207 5232 a Fg(\003)243 5256 y Ff(Supp)r(orted)c(b)n(y)f (NSER)n(C,)f(NSF,)h(UR)n(C/Indiana)g(State)i(Univ)n(ersit)n(y)211 5315 y Fg(y)243 5338 y Ff(Departmen)n(t)39 b(of)f(Computing)g(Science,) k(Univ)n(ersit)n(y)c(of)g(Alb)r(erta,)116 5422 y(Edmon)n(ton)24 b(Canada)h(T6G)f(2H1,)g(ha)n(yw)n([email protected])r(erta.ca)211 5481 y Fg(z)243 5504 y Ff(Departmen)n(t)48 b(of)e(Computer)h(Science,) 53 b(V)-6 b(anderbilt)47 b(Univ)n(ersit)n(y)-6 b(,)116 5587 y(Nash)n(ville)23 b(TN)h(37235,)g([email protected])l(anderbilt.edu)211 5647 y Fg(x)243 5670 y Ff(Computer)37 b(Science)h(Departmen)n(t,)i (Univ)n(ersit)n(y)d(of)f(Da)n(yton,)41 b(300)116 5753 y(College)24 b(P)n(ark,)f(Da)n(yton)i(OH)f(42469-2160,)h([email protected])n (yton.edu)2350 1355 y Fj(A)32 b(n)n(um)n(b)r(er)f(of)h(algorithms)f(on) g(w)n(eakly)g(c)n(hordal)f(graphs)2200 1455 y(w)n(ork)25 b(b)n(y)i(rep)r(eatedly)f(\014nding)h(a)f(t)n(w)n(o-pair)f Fi(f)p Fl(x;)14 b(y)s Fi(g)26 b Fj(and)g(mo)r(di-)2200 1554 y(fying)d(the)g(neigh)n(b)r(orho)r(o)r(ds)e(of)h Fl(x)i Fj(and/or)d Fl(y)s Fj(.)35 b(This)22 b(is)h(the)g(basis)2200 1654 y(of)g(the)h(previously)e(b)r(est)h(algorithms)f(for)h (recognizing)e(w)n(eakly)2200 1753 y(c)n(hordal)j(graphs)f([8])i(and)g (for)f(solving)g(a)h(v)-5 b(ariet)n(y)24 b(of)h(optimiza-)2200 1853 y(tion)31 b(problems)e(on)h(w)n(eakly)g(c)n(hordal)f(graphs)g([8)o (,)i(5)o(])g(\(namely)2200 1953 y(w)n(eigh)n(ted)h(and)g(un)n(w)n(eigh) n(ted)f(v)n(ersions)g(of)h(maxim)n(um)g(clique,)2200 2052 y(minim)n(um)44 b(v)n(ertex)e(coloring,)j(maxim)n(um)e(indep)r (enden)n(t)h(set)2200 2152 y(and)22 b(minim)n(um)h(clique)f(co)n(v)n (ering\))f(The)h(fastest)g(algorithm)g(for)2200 2252 y(\014nding)j(a)g(t)n(w)n(o-pair)f([1)o(])i(runs)e(in)i(O\()p Fl(nm)p Fj(\))f(time)h(and)f(w)n(orks)e(on)2200 2351 y(general)f(graphs.)34 b(In)24 b(this)g(pap)r(er)f(w)n(e)g(giv)n(e)g(a) g(structural)f(result)2200 2451 y(sp)r(ecifying)29 b(where)f(a)h(t)n(w) n(o-pair)e(can)i(b)r(e)g(lo)r(cated)f(in)i(a)e(w)n(eakly)2200 2550 y(c)n(hordal)d(graph.)36 b(While)27 b(this)g(do)r(es)g(not)f(lead) h(to)f(an)h(impro)n(v)n(e-)2200 2650 y(men)n(t)22 b(in)f(the)g(time)h (to)f(\014nd)h(a)f(single)f(t)n(w)n(o-pair,)h(it)g(do)r(es)g(lead)g(to) 2200 2750 y(an)30 b(impro)n(v)n(emen)n(t)f(in)h(the)h(time)g(to)f (\014nd)g(a)g(sequence)g(of)g(t)n(w)n(o-)2200 2849 y(pairs)25 b(in)h(a)g(graph)e(as)i(the)g(graph)f(is)g(mo)r(di\014ed)i(during)e(w)n (eakly)2200 2949 y(c)n(hordal)h(recognition)g(and)i(optimization)f (algorithms.)2350 3049 y(The)67 b(previously)f(b)r(est)i(recognition)d (algorithm)i(for)2200 3148 y(w)n(eakly)25 b(c)n(hordal)g(graphs)g([8])i (tak)n(es)e(O\()p Fl(n)3505 3118 y Fe(4)3542 3148 y Fj(\))i(time)g(and) f(O\()p Fl(nm)p Fj(\))2200 3248 y(space.)68 b(W)-7 b(e)39 b(impro)n(v)n(e)d(on)i(this)h(algorithm)e(b)n(y)h(taking)f(only)2200 3347 y(O\()p Fl(m)2370 3317 y Fe(2)2407 3347 y Fj(\))e(time)f(and)g (O\()p Fl(n)23 b Fj(+)f Fl(m)p Fj(\))34 b(space,)h(and)f(pro)r(ducing)g (as)f(a)2200 3447 y(certi\014cate)d(a)f(hole)h(or)f(an)n(tihole)g (whenev)n(er)g(the)h(input)h(graph)2200 3547 y(is)e(not)g(w)n(eakly)f (c)n(hordal)f(\(the)j(previous)e(algorithm)f(do)r(es)i(not)2200 3646 y(do)c(this\).)37 b(This)25 b(is)h(analogous)d(to)i(the)h(w)n(ell) f(kno)n(wn)g(O\()p Fl(m)14 b Fj(+)g Fl(n)p Fj(\))2200 3746 y(time)25 b(c)n(hordal)d(graph)h(recognition)f(algorithm)h([6],)i (whic)n(h)e(can)2200 3846 y(also)e(pro)r(duce)h(in)h(this)f(time)h(an)f (induced)h(cycle)f(of)g(length)g(four)2200 3945 y(or)27 b(more)g(whenev)n(er)f(the)i(input)h(graph)d(is)h(not)h(c)n(hordal.) 2350 4045 y(The)49 b(previously)g(b)r(est)h(optimization)f(algorithms)g (for)2200 4144 y(w)n(eakly)34 b(c)n(hordal)f(graphs)g([8],)k(based)d (on)g(the)i(algorithms)d(of)2200 4244 y([5])42 b(and)g(an)g Fl(O)r Fj(\()p Fl(nm)p Fj(\))h(time)g(algorithm)d(for)i(\014nding)g(a)g (t)n(w)n(o-)2200 4344 y(pair)36 b([1],)j(rep)r(eat)d(the)i(follo)n (wing)d(pro)r(cess:)54 b(\014nd)38 b(a)e(t)n(w)n(o-pair)2200 4443 y(and)g(mo)r(dify)h(the)f(graph,)i(either)e(b)n(y)g(adding)g(an)g (edge)f(to)h(a)2200 4543 y(t)n(w)n(o-pair)i(or)g(b)n(y)h(collapsing)f (a)h(t)n(w)n(o-pair)e(to)j(form)f(a)g(single)2200 4643 y(v)n(ertex.)108 b(These)51 b(algorithms)f(tak)n(e)h(O\()p Fl(n)3606 4612 y Fe(2)3643 4643 y Fl(m)p Fj(\))g(and)h(O\()p Fl(n)4132 4612 y Fe(4)4169 4643 y Fj(\))2200 4742 y(time)25 b(in)g(the)g(un)n(w)n(eigh)n(ted)f(and)g(w)n(eigh)n(ted)g(cases)g(resp) r(ectiv)n(ely)-7 b(.)2200 4842 y(Our)32 b(algorithms)e(can)i(solv)n(e)f (the)i(un)n(w)n(eigh)n(ted)e(optimization)2200 4941 y(problems,)44 b(whic)n(h)d(only)f(in)n(v)n(olv)n(e)g(collapsing)f(t)n(w)n(o-pairs,)k (in)2200 5041 y(O\()p Fl(nm)p Fj(\))28 b(time.)2350 5141 y(Our)42 b(algorithms)g(rely)g(on)h(the)h(follo)n(wing)e(notion)h(due) 2200 5240 y(to)34 b(Ha)n(yw)n(ard)f([3,)h(4]:)50 b(a)34 b Fm(hand)t(le)j Fj(in)d(a)g(graph)g Fl(G)h Fj(is)f(a)g(prop)r(er)2200 5340 y(v)n(ertex)28 b(subset)h Fl(H)36 b Fj(with)30 b(size)e(at)h (least)g(t)n(w)n(o,)g(suc)n(h)f(that)i Fl(G)p Fj([)p Fl(H)7 b Fj(])2200 5440 y(is)39 b(connected,)k(some)38 b(comp)r(onen)n(t)i Fl(J)50 b Fi(6)p Fj(=)43 b Fl(H)j Fj(of)39 b Fl(G)27 b Fi(\000)f Fl(N)9 b Fj(\()p Fl(H)e Fj(\))2200 5539 y(satis\014es)31 b Fl(N)9 b Fj(\()p Fl(J)f Fj(\))31 b(=)f Fl(N)9 b Fj(\()p Fl(H)e Fj(\),)33 b(and)f(eac)n(h)f(v)n (ertex)g(of)h Fl(N)9 b Fj(\()p Fl(H)e Fj(\))32 b(sees)2200 5639 y(at)c(least)f(one)g(v)n(ertex)g(of)g(eac)n(h)g(edge)g(of)h Fl(G)p Fj([)p Fl(H)7 b Fj(].)2350 5738 y Fl(J)35 b Fj(is)28 b(called)f(a)g Fm(c)l(ohand)t(le)j Fj(of)e Fl(H)7 b Fj(.)36 b(Notice)28 b(that)g Fl(N)9 b Fj(\()p Fl(H)e Fj(\))28 b(is)f(a)p eop %%Page: 43 2 43 1 bop -116 299 a Fd(Pro)r(ceedings)26 b(of)h(11th)g(A)n(CM-SIAM)h (SOD)n(A)g(\(2000\))e(42-49)2075 b Fj(43)-116 523 y(minimal)28 b(separator)d(of)i Fl(H)35 b Fj(and)27 b Fl(J)8 b Fj(.)-116 685 y Fh(Theorem)32 b(1.2.)40 b Fj([3,)27 b(4])j Fm(A)g(gr)l(aph)h(has) g(a)f(hand)t(le)i(if)e(and)h(only)-116 785 y(if)38 b(the)g(gr)l(aph)g (has)g(a)p 587 718 65 4 v 38 w Fl(P)652 797 y Fe(3)689 785 y Fm(,)i(and)e(a)f(hand)t(le)i(and)f(its)g(c)l(ohand)t(le)-116 884 y(c)l(an)30 b(b)l(e)f(found)i(in)e(O\()p Fl(nm)p Fm(\))g(time.)33 1046 y Fj(A)53 b Fm(c)l(o-two-p)l(air)g Fj(of)f(a)g(graph,)57 b(or)51 b(simply)i(a)e Fm(c)l(o-p)l(air)p Fj(,)-116 1146 y(is)43 b(a)g(t)n(w)n(o-pair)e(of)i(the)g(complemen)n(t) g(of)h(the)f(graph.)82 b(Our)-116 1245 y(algorithms)34 b(are)h(based)g(on)g(searc)n(hing)f(for)h(co-pairs.)60 b(A)36 b(set)-116 1345 y Fl(X)44 b Fj(of)38 b(v)n(ertices)f(is)i(main)n (tained)e(with)i(the)g(prop)r(ert)n(y)e(that)h(a)-116 1445 y(co-pair)30 b(of)i Fl(G)h Fj(can)f(b)r(e)g(found)h(in)f Fl(X)39 b Fj(whenev)n(er)31 b Fl(G)i Fj(is)f(w)n(eakly)-116 1544 y(c)n(hordal.)53 b Fl(X)40 b Fj(is)33 b(re\014ned)h(un)n(til)g (eac)n(h)e(edge)h(in)h Fl(G)p Fj([)p Fl(X)7 b Fj(])34 b(induces)-116 1644 y(a)28 b(co-pair)g(of)h Fl(G)p Fj(.)41 b(The)29 b(graph)f(is)h(then)h(mo)r(di\014ed)f(as)g(required)-116 1743 y(b)n(y)19 b(the)h(top-lev)n(el)f(\(recognition)f(or)h (optimization\))h(algorithm,)-116 1843 y(and)33 b(the)g(co-pair)e (searc)n(h)h(resumes)g(in)h(the)g(mo)r(di\014ed)h(graph.)-116 1943 y(The)46 b(adv)-5 b(an)n(tage)44 b(of)i(our)f(metho)r(d)h(is)g (that)g(when)g(the)h(co-)-116 2042 y(pair)28 b(searc)n(h)g(resumes)h (in)g(the)h(mo)r(di\014ed)g(graph,)e(v)n(ertices)h(are)-116 2142 y(considered)17 b(in)i(essen)n(tially)e(the)i(same)f(order)f(as)h (in)g(the)h(original)-116 2242 y(searc)n(h.)32 b(Th)n(us)19 b(unnecessary)e(recomputation)h(can)g(b)r(e)h(a)n(v)n(oided)-116 2341 y(b)n(y)33 b(main)n(taining)g(a)h(stac)n(k)e(of)i(v)n(ertices)f (eliminated)h(from)f Fl(X)7 b Fj(.)-116 2441 y(Up)r(on)44 b(searc)n(h)f(resumption,)k(it)e(su\016ces)e(to)h(restore)f Fl(X)50 b Fj(b)n(y)-116 2540 y(p)r(opping)39 b(the)g(stac)n(k)e(bac)n (k)h(to)h(the)g(\014rst)g(lev)n(el)f(at)h(whic)n(h)f Fl(X)-116 2640 y Fj(con)n(tains)26 b(an)i(edge.)33 2740 y(W)-7 b(e)21 b(condense)f(the)i(relev)-5 b(an)n(t)19 b(algorithms)h(from)g([3,)h(4)o(])g(in)n(to)-116 2839 y(the)i(follo)n(wing)f(algorithm)g(whose)g(details)h(are)f(needed)h (for)f(the)-116 2939 y(analysis)30 b(of)i(our)f(algorithms.)48 b(W)-7 b(e)32 b(use)g Fm(with)g Fj(as)f(a)h(synon)n(ym)-116 3039 y(for)27 b(\\con)n(taining".)-116 3200 y Fr(Algorithm)e Fm(\014nd-hand)t(le)-116 3300 y Fr(Input)p Fj(:)37 b(A)28 b(graph)f Fl(G)-116 3400 y Fr(Output)p Fj(:)37 b(Either)27 b(a)g(message)f(`no)i(handle')f(or)234 3499 y(a)g(handle)h Fl(H)34 b Fj(of)28 b Fl(G)g Fj(and)f(a)h(cohandle)e Fl(J)36 b Fj(of)28 b Fl(H)-116 3699 y Fr(b)s(egin)147 3798 y Fj(/*)e Fm(initialization)k Fj(*/)-29 3898 y(searc)n(h)c(for)i(v)n (ertex)e Fl(v)31 b Fj(and)c(edge)h Fl(e)f Fj(so)g(that)h Fl(v)j Fj(misses)c Fl(e)-29 3998 y Fr(if)h Fj(no)f Fl(v)s(;)14 b(e)28 b Fr(then)f Fj(return)g(`no)h(handle')f(and)h(exit)f Fr(endif)-29 4097 y Fl(Y)42 b Fi( )28 b Fj(comp)r(onen)n(t)f(of)h Fl(G)18 b Fi(\000)g Fl(N)9 b Fj(\()p Fl(e)p Fj(\))28 b(with)g Fl(v)-29 4197 y(X)i Fi( )d Fj(comp)r(onen)n(t)h(of)f Fl(G)19 b Fi(\000)f Fl(N)9 b Fj(\()p Fl(Y)19 b Fj(\))28 b(with)g Fl(e)-29 4296 y Fj(/*)p Fl(N)9 b Fj(\()p Fl(X)e Fj(\))22 b(=)h Fl(N)9 b Fj(\()p Fl(Y)18 b Fj(\))28 b(minimally)g (separates)e Fl(X)34 b Fj(and)27 b Fl(Y)19 b Fj(*/)147 4496 y(/*)26 b Fm(hand)t(le)32 b(\014nding)27 b Fj(*/)-29 4595 y Fr(while)g Fj(some)g Fl(v)k Fj(in)d Fl(N)9 b Fj(\()p Fl(X)e Fj(\))27 b(misses)g(some)g Fl(e)g Fj(in)h Fl(X)34 b Fr(do)59 4695 y Fl(Y)126 4665 y Fc(0)172 4695 y Fi( )28 b Fj(comp)r(onen)n(t)f(of)h Fl(G)18 b Fi(\000)g Fl(N)9 b Fj(\()p Fl(e)p Fj(\))28 b(with)g Fl(v)59 4795 y(X)135 4764 y Fc(0)181 4795 y Fi( )f Fj(comp)r(onen)n(t)h(of)f Fl(G)19 b Fi(\000)f Fl(N)9 b Fj(\()p Fl(Y)1152 4764 y Fc(0)1175 4795 y Fj(\))28 b(with)g Fl(e)f Fj(/*)p Fr(\(+\))p Fj(*/)59 4894 y(push)h(v)n(ertices)e(of)i Fl(X)d Fi(\000)18 b Fl(X)906 4864 y Fc(0)956 4894 y Fj(on)n(to)27 b(the)h(stac)n(k)59 4994 y Fl(X)h Fi( )23 b Fl(X)339 4964 y Fc(0)445 4994 y Fl(Y)42 b Fi( )23 b Fl(Y)708 4964 y Fc(0)786 4994 y Fr(endwhile)-29 5093 y Fl(H)7 b Fj(,)28 b Fl(J)36 b Fi( )27 b Fl(X)7 b Fj(,)27 b Fl(Y)-116 5193 y Fr(end)g Fm(\014nd-hand)t(le)33 5355 y Fj(W)-7 b(e)31 b(also)e(use)h(an)g(op)r(eration)f(called)h Fm(r)l(estarting)p Fj(,)h(namely)-116 5455 y(reen)n(tering)25 b Fm(\014nd-hand)t(le)k Fj(in)e(the)g(handle)g(\014nding)g(phase)g (after)-116 5554 y(the)22 b(mo)r(di\014cation)g(of)g(either)g(the)g (graph)f(or)g(the)i(set)f Fl(X)7 b Fj(.)34 b(When)-116 5654 y(restarting)d(w)n(e)h(assume)g(that)h(w)n(e)f(ha)n(v)n(e)f (access)g(to)i(the)g(stac)n(k)-116 5753 y(whic)n(h)27 b(w)n(as)g(used)g(when)h Fm(\014nd-hand)t(le)h Fj(last)e(exited.)2117 523 y(A)j(k)n(ey)f(fact)g([3,)g(4])g(used)h(in)f(pro)n(ving)f(the)i (correctness)e(of)1968 623 y Fm(\014nd-hand)t(le)g Fj(is)g(that)f Fl(X)2737 593 y Fc(0)2787 623 y Fj(is)h(a)f(prop)r(er)f(subset)i(of)f Fl(X)34 b Fj(after)27 b(the)1968 722 y(step)h(mark)n(ed)f(\(+\).)39 b(Th)n(us)28 b Fm(\014nd-hand)t(le)i Fj(deletes)e(at)g(least)g(one)1968 822 y(v)n(ertex)h(from)g Fl(X)37 b Fj(at)30 b(a)f(cost)h(of)g(O\()p Fl(m)p Fj(\))g(during)g(eac)n(h)f(iteration)1968 922 y(of)h(the)h(while)g(lo)r(op.)46 b(The)31 b(initialization)f(phase)h (tak)n(es)e(O\()p Fl(m)p Fj(\))1968 1021 y(time.)36 b(An)25 b(initial)g Fl(v)j Fj(and)d Fl(e)f Fj(can)h(b)r(e)g(found)g(if)g(and)g (only)f(if)i Fl(G)f Fj(is)1968 1121 y(not)31 b(a)f(complete)h(m)n (ultipartite)g(graph.)46 b(A)31 b(simple)h(complete)1968 1220 y(m)n(ultipartite)26 b(recognition)e(algorithm)h(is)h(to)g(pic)n (k)f(an)n(y)h(v)n(ertex)1968 1320 y Fl(x)p Fj(,)g(let)f Fl(C)32 b Fj(b)r(e)25 b Fl(V)32 b Fi(\000)13 b(f)p Fl(x)p Fi(g)g(\000)g Fl(N)c Fj(\()p Fl(x)p Fj(\),)27 b(and)e(c)n(hec)n(k)f (whether)h Fl(N)9 b Fj(\()p Fl(y)s Fj(\))25 b(=)1968 1420 y Fl(N)9 b Fj(\()p Fl(x)p Fj(\))30 b(for)f(ev)n(ery)f Fl(y)33 b Fj(in)c Fl(C)6 b Fj(.)43 b(If)30 b(so,)g(remo)n(v)n(e)e Fl(C)36 b Fj(and)29 b(rep)r(eat)g(the)1968 1519 y(pro)r(cess.)35 b(If)28 b(not,)g(some)f Fl(z)k Fj(has)c(b)r(een)h(found)g(in)g Fl(N)9 b Fj(\()p Fl(y)s Fj(\))19 b Fi(\000)f Fl(N)9 b Fj(\()p Fl(x)p Fj(\))1968 1619 y(or)28 b Fl(N)9 b Fj(\()p Fl(x)p Fj(\))21 b Fi(\000)e Fl(N)9 b Fj(\()p Fl(y)s Fj(\),)31 b(so)e Fi(f)p Fl(x;)14 b(y)s(;)g(z)t Fi(g)28 b Fj(induces)p 3322 1552 V 29 w Fl(P)3387 1631 y Fe(3)3454 1619 y Fj(and)i(yields)f (the)1968 1719 y(desired)e Fl(v)k Fj(and)c Fl(e)p Fj(.)1968 1918 y Fr(2)95 b(Finding)31 b(co-pairs)1968 2042 y Fj(Giv)n(en)h(a)g (graph,)h(our)e(approac)n(h)g(in)i(\014nding)f(a)g(co-pair)f(is)i(to) 1968 2142 y(\014nd)k(a)g(handle)f(of)h(the)h(graph,)g(and)e(then)i(a)e (handle)h(of)g(the)1968 2242 y(handle,)45 b(and)c(so)g(on,)k(un)n(til)d (w)n(e)f(cannot)g(\014nd)h(a)f(handle)g(in)1968 2341 y(the)32 b(last)f(handle.)50 b(It)32 b(turns)g(out)f(that)i(if)f(a)f (graph)g(is)h(w)n(eakly)1968 2441 y(c)n(hordal)23 b(then)j(ev)n(ery)e (edge)h(of)g(the)h(last)f(handle)g(induces)g(a)g(co-)1968 2540 y(pair)30 b(of)i(the)g(graph.)47 b(A)32 b(handle)f(of)g(a)h (handle)f(ma)n(y)g(not)g(b)r(e)h(a)1968 2640 y(handle)i(of)g(the)h (graph,)g(but)g(that)g(prop)r(ert)n(y)e(is)h(not)g(needed.)1968 2740 y(After)41 b(p)r(erforming)f(op)r(erations)g(on)g(a)h(co-pair)e (as)h(required)1968 2839 y(b)n(y)34 b(the)g(relev)-5 b(an)n(t)34 b(recognition)e(or)i(optimization)g(algorithm,)1968 2939 y(w)n(e)23 b(searc)n(h)g(for)h(the)g(next)g(co-pair)f(b)n(y)h (restarting)e Fm(\014nd-hand)t(le)p Fj(,)1968 3039 y(th)n(us)36 b(doing)f(less)g(w)n(ork)g(than)h(in)g(the)g(original)f(call)g(to)h Fm(\014nd-)1968 3138 y(hand)t(le)p Fj(.)1968 3319 y Fr(Algorithm)25 b Fm(\014nd-p)l(air)1968 3418 y Fr(Input)p Fj(:)37 b(A)28 b(w)n(eakly)e(c)n(hordal)h(graph)f Fl(G)i Fj(with)g(at)g(least)f(one)g (edge)1968 3518 y Fr(Output)p Fj(:)37 b(A)28 b(co-pair)e(of)h Fl(G)1968 3717 y Fr(b)s(egin)2055 3817 y Fl(j)h Fi( )23 b Fj(0)83 b Fl(H)2417 3829 y Fe(0)2477 3817 y Fi( )23 b Fl(V)c Fj(\()p Fl(G)p Fj(\))2055 3917 y Fr(while)27 b Fl(G)p Fj([)p Fl(H)2459 3929 y Fk(j)2494 3917 y Fj(])h(has)f(a)g (handle)h Fl(H)34 b Fr(do)2143 4016 y Fl(j)28 b Fi( )23 b Fl(j)g Fj(+)18 b(1)83 b Fl(H)2645 4028 y Fk(j)2703 4016 y Fi( )28 b Fl(H)1995 4116 y Fr(endwhile)2055 4215 y Fj(output)g(an)n(y)f(edge)g(of)h Fl(G)p Fj([)p Fl(H)2925 4227 y Fk(j)2960 4215 y Fj(])1968 4315 y Fr(end)f Fm(\014nd-p)l(air) 2117 4496 y Fj(T)-7 b(o)43 b(pro)n(v)n(e)f(the)i(correctness)d(of)j Fm(\014nd-p)l(air)g Fj(w)n(e)f(use)g(the)1968 4595 y(follo)n(wing)26 b(lemma.)1968 4776 y Fh(Lemma)31 b(2.1.)40 b Fm(L)l(et)45 b Fl(H)52 b Fm(b)l(e)46 b(a)f(hand)t(le)i(of)f(a)g(we)l(akly)h(chor)l (dal)1968 4875 y(gr)l(aph)24 b Fl(G)g Fm(and)g(let)f Fi(f)p Fl(x;)14 b(y)s Fi(g)23 b Fm(b)l(e)g(a)h(c)l(o-p)l(air)g(of)h Fl(G)p Fj([)p Fl(H)7 b Fj(])p Fm(.)36 b(Then)24 b Fi(f)p Fl(x;)14 b(y)s Fi(g)1968 4975 y Fm(is)30 b(a)g(c)l(o-p)l(air)h(of)f Fl(G)p Fm(.)1968 5156 y(Pr)l(o)l(of.)43 b Fj(Let)27 b Fl(J)35 b Fj(b)r(e)27 b(a)g(cohandle)f(of)h Fl(H)34 b Fj(in)27 b Fl(G)p Fj(,)h(let)f Fl(I)j Fj(=)23 b Fl(N)9 b Fj(\()p Fl(H)e Fj(\))23 b(=)1968 5255 y Fl(N)9 b Fj(\()p Fl(J)f Fj(\),)28 b(and)g(let)g Fl(R)d Fj(=)e Fl(V)c Fj(\()p Fl(G)p Fj(\))g Fi(\000)f Fl(H)26 b Fi(\000)18 b Fl(I)7 b Fj(.)38 b(Supp)r(ose)28 b(that)g Fi(f)p Fl(x;)14 b(y)s Fi(g)1968 5355 y Fj(is)27 b(a)g(co-pair)f(in)i Fl(G)p Fj([)p Fl(H)7 b Fj(])28 b(but)g(not)g(in)g Fl(G)p Fj(.)2117 5455 y(Then)j(in)p 2437 5388 66 4 v 31 w Fl(G)g Fj(there)f(is)h(an)f (induced)h(path)g Fl(P)40 b Fj(=)27 b(\()p Fl(x)35 b(:)14 b(:)g(:)34 b(y)s Fj(\))1968 5554 y(with)42 b(at)g(least)g(four)g(v)n (ertices.)80 b Fl(P)54 b Fj(do)r(es)42 b(not)g(in)n(tersect)g Fl(R)q Fj(,)1968 5654 y(since)34 b(in)p 2281 5587 V 34 w Fl(G)h Fj(eac)n(h)f(v)n(ertex)f(in)i Fl(R)g Fj(sees)f(b)r(oth)h Fl(x)g Fj(and)f Fl(y)s Fj(.)57 b(Th)n(us)1968 5753 y Fl(P)48 b Fj(in)n(tersects)35 b Fl(I)7 b Fj(.)63 b Fl(P)48 b Fj(has)36 b(no)g(subpath)g(\()p Fl(uv)s(w)r Fj(\))i(suc)n(h)d(that)i Fl(u)p eop %%Page: 44 3 44 2 bop 116 299 a Fj(44)2953 b Fd(Ha)n(yw)n(ard,)26 b(Spinrad,)h(Sritharan)116 523 y Fj(and)f Fl(w)j Fj(are)c(in)h Fl(H)33 b Fj(but)26 b Fl(v)k Fj(is)c(in)g Fl(I)7 b Fj(,)26 b(for)g(otherwise)f(in)h Fl(G)g Fj(some)g Fl(v)116 623 y Fj(of)j Fl(I)36 b Fj(misses)28 b(edge)h(\()p Fl(u;)14 b(w)r Fj(\))30 b(of)e Fl(G)p Fj([)p Fl(H)7 b Fj(])30 b(and)e Fl(H)36 b Fj(is)29 b(not)g(a)f(handle,)116 722 y(con)n(tradiction.)36 b(Th)n(us)27 b(in)p 961 656 66 4 v 28 w Fl(G)h(P)39 b Fj(has)27 b(at)h(least)f(one)g(edge)g(of)h Fl(I)7 b Fj(.)266 822 y(In)p 372 755 V 30 w Fl(G)30 b Fj(consider)f(a)g(subpath)h Fl(P)1250 792 y Fc(0)1303 822 y Fj(=)g(\()p Fl(x)1477 834 y Fe(2)1515 822 y Fl(x)1562 834 y Fe(3)1600 822 y Fl(x)1647 834 y Fe(4)1698 822 y Fl(:)14 b(:)g(:)g(x)1856 834 y Fk(r)1893 822 y Fj(\))30 b(of)g Fl(P)116 922 y Fj(with)24 b Fl(r)i Fi(\025)d Fj(4)g(suc)n(h)g (that)g Fl(x)922 934 y Fe(2)983 922 y Fj(and)h Fl(x)1188 934 y Fk(r)1248 922 y Fj(are)f(in)g Fl(H)31 b Fj(but)24 b Fl(x)1770 934 y Fe(3)1831 922 y Fj(through)116 1021 y Fl(x)163 1033 y Fk(r)r Fc(\000)p Fe(1)313 1021 y Fj(are)j(in)i Fl(I)7 b Fj(.)37 b(Observ)n(e)27 b(that)h Fl(x)1200 1033 y Fe(3)1266 1021 y Fj(misses)f Fl(x)1568 1033 y Fe(4)1634 1021 y Fj(in)h Fl(G)p Fj(.)38 b(Since)28 b Fl(I)116 1121 y Fj(is)21 b(a)g(minimal)h(separator)d(for)i Fl(H)28 b Fj(and)21 b Fl(J)29 b Fj(in)22 b Fl(G)g Fj(and)f(since)g Fl(G)h Fj(has)116 1220 y(no)27 b(holes,)f(in)i Fl(G)f Fj(ev)n(ery)e(t)n(w)n(o)i(nonadjacen)n(t)f(v)n(ertices)f(of)i Fl(I)34 b Fj(ha)n(v)n(e)116 1320 y(a)f(common)g(neigh)n(b)r(or)f(in)h Fl(J)8 b Fj(.)54 b(In)34 b(particular)d Fl(x)1654 1332 y Fe(3)1725 1320 y Fj(and)j Fl(x)1940 1332 y Fe(4)2011 1320 y Fj(see)116 1420 y(some)27 b Fl(x)371 1432 y Fe(1)435 1420 y Fj(of)g Fl(J)35 b Fj(in)28 b Fl(G)p Fj(.)37 b(Th)n(us)26 b(in)p 1138 1353 V 28 w Fl(G)h(x)1277 1432 y Fe(1)1342 1420 y Fj(sees)f Fl(x)1555 1432 y Fe(2)1593 1420 y Fj(,)h Fl(x)1690 1432 y Fe(1)1755 1420 y Fj(misses)f Fl(x)2056 1432 y Fe(3)2094 1420 y Fj(,)116 1519 y Fl(x)163 1531 y Fe(1)229 1519 y Fj(misses)i Fl(x)532 1531 y Fe(4)570 1519 y Fj(,)h(and)f(so)g(\()p Fl(x)966 1531 y Fe(1)1004 1519 y Fl(x)1051 1531 y Fe(2)1089 1519 y Fl(x)1136 1531 y Fe(3)1174 1519 y Fl(x)1221 1531 y Fe(4)1258 1519 y Fj(\))h(is)f(a)h Fl(P)1527 1531 y Fe(4)1564 1519 y Fj(.)40 b(Let)28 b Fl(x)1823 1531 y Fk(s)1888 1519 y Fj(b)r(e)h(the)116 1619 y(\014rst)f(v)n(ertex)f(in)h Fl(P)702 1589 y Fc(0)753 1619 y Fj(after)f Fl(x)996 1631 y Fe(4)1062 1619 y Fj(suc)n(h)h(that)g (in)p 1527 1552 V 28 w Fl(G)g(x)1667 1631 y Fe(1)1733 1619 y Fj(sees)f Fl(x)1947 1631 y Fk(s)1983 1619 y Fj(;)h Fl(x)2081 1631 y Fk(s)116 1719 y Fj(exists)f(since)f(in)p 643 1652 V 27 w Fl(G)h(x)782 1731 y Fe(1)847 1719 y Fj(sees)f Fl(x)1060 1731 y Fk(r)1097 1719 y Fj(.)36 b(Then)27 b(in)p 1468 1652 V 27 w Fl(G)g Fi(f)p Fl(x)1649 1731 y Fe(1)1687 1719 y Fl(;)14 b(x)1771 1731 y Fe(2)1808 1719 y Fl(;)g(:)g(:)g(:)g(;)g (x)2040 1731 y Fk(s)2076 1719 y Fi(g)116 1818 y Fj(induces)30 b(a)g(hole)g(of)f(size)h(at)g(least)g(\014v)n(e)f(and)h Fl(G)g Fj(is)g(not)g(w)n(eakly)116 1918 y(c)n(hordal,)c(con)n (tradiction.)p 2059 1920 59 4 v 2059 1861 V 2057 1918 4 59 v 2115 1918 V 116 2098 a Fh(Theorem)32 b(2.1.)40 b Fm(A)n(lgorithm)31 b(\014nd-p)l(air)f(is)g(c)l(orr)l(e)l(ct.)116 2279 y(Pr)l(o)l(of.)43 b Fj(Assume)27 b(that)h Fm(\014nd-p)l(air)g Fj(terminates)e(after)h(p)r(erform-)116 2379 y(ing)35 b Fl(p)f Fj(lo)r(op)g(iterations.)57 b(Then)34 b Fl(G)p Fj([)p Fl(H)1330 2391 y Fk(p)1369 2379 y Fj(])h(has)f(no)p 1704 2312 65 4 v 34 w Fl(P)1769 2391 y Fe(3)1806 2379 y Fj(,)i(since)f(a)116 2478 y(graph)e(with)g(a)p 627 2412 V 33 w Fl(P)692 2490 y Fe(3)763 2478 y Fj(has)g(a)g(handle.)54 b(Th)n(us)33 b Fl(G)p Fj([)p Fl(H)1682 2490 y Fk(p)1721 2478 y Fj(])g(is)h(a)f(com-)116 2578 y(plete)23 b(m)n(ultipartite)f (graph,)g(so)f(ev)n(ery)g(edge)g(of)h Fl(G)p Fj([)p Fl(H)1765 2590 y Fk(p)1804 2578 y Fj(])g(induces)116 2677 y(a)32 b(co-pair)e(of)i Fl(G)p Fj([)p Fl(H)727 2689 y Fk(p)765 2677 y Fj(].)50 b(Th)n(us)31 b(b)n(y)h(Lemma)f(2.1)g(ev)n(ery)g(edge)g (of)116 2777 y Fl(G)p Fj([)p Fl(H)273 2789 y Fk(p)312 2777 y Fj(])e(induces)f(a)h(co-pair)e(of)h Fl(G)p Fj([)p Fl(H)1261 2789 y Fk(p)p Fc(\000)p Fe(1)1385 2777 y Fj(],)h(since)g Fl(H)1734 2789 y Fk(p)1801 2777 y Fj(is)f(a)h(han-)116 2877 y(dle)k(of)f Fl(G)p Fj([)p Fl(H)511 2889 y Fk(p)p Fc(\000)p Fe(1)634 2877 y Fj(].)51 b(Con)n(tin)n(uing)32 b(this)g(argumen)n(t,)h(ev)n(ery)e(edge)116 2976 y(of)d Fl(G)p Fj([)p Fl(H)368 2988 y Fk(p)407 2976 y Fj(])f(induces)h(a)f (co-pair)f(of)i Fl(G)p Fj(.)p 2059 2978 59 4 v 2059 2920 V 2057 2976 4 59 v 2115 2976 V 116 3157 a Fh(Theorem)k(2.2.)40 b Fm(A)n(lgorithm)65 b(\014nd-p)l(air)g(runs)f(in)g(O\()p Fl(nm)p Fm(\))116 3257 y(time.)116 3437 y(Pr)l(o)l(of.)43 b Fj(The)37 b(time)g(sp)r(en)n(t)g(b)n(y)g(an)f(execution)g(of)h Fm(\014nd-p)l(air)g Fj(is)116 3537 y(the)25 b(total)f(of)h(the)g(time)g (sp)r(en)n(t)f(b)n(y)h(the)f(resulting)g(calls)g(of)h Fm(\014nd-)116 3636 y(hand)t(le)p Fj(.)39 b(Since)27 b Fm(\014nd-hand)t(le)h Fj(is)f(called)f(at)h(most)g Fl(n)f Fj(times,)i(the)116 3736 y(total)40 b(time)h(sp)r(en)n(t)f(in)h (its)f(initialization)g(phase)g(o)n(v)n(er)e(these)116 3836 y(calls)44 b(is)h(O\()p Fl(nm)p Fj(\).)88 b(The)45 b(total)f(time)h(sp)r(en)n(t)g(in)g(its)g(handle)116 3935 y(\014nding)35 b(phase)f(is)h(also)f(O\()p Fl(nm)p Fj(\),)i(since)f(eac)n(h)e(lo)r(op)i(iteration)116 4035 y(tak)n(es)g Fl(O)r Fj(\()p Fl(m)p Fj(\))i(time)f(and)g(with)g(eac)n(h) f(iteration)g(at)h(least)g(one)116 4134 y(v)n(ertex)27 b(is)g(deleted.)p 2059 4136 59 4 v 2059 4078 V 2057 4134 4 59 v 2115 4134 V 116 4334 a Fr(3)95 b(Recognizing)31 b(w)m(eakly)h(c)m(hordal)h(graphs)116 4458 y Fj(Since)19 b(our)f(algorithm)g(uses)g(the)h(basic)g(structure)f(of)h(the)g(O\()p Fl(n)2048 4428 y Fe(4)2085 4458 y Fj(\))116 4558 y(algorithm)26 b([8)o(])h(for)f(recognizing)f(w)n(eakly)g(c)n(hordal)g(graphs,)h(w)n (e)116 4658 y(review)h(that)h(\014rst.)37 b(Giv)n(en)27 b(an)g(arbitrary)f(graph)g Fl(G)i Fj(as)f(input,)116 4757 y(the)21 b(algorithm)f(in)h([8)o(])g(rep)r(eatedly)f(\014nds)h(a)f (t)n(w)n(o-pair)f(and)i(adds)116 4857 y(an)k(edge)f(b)r(et)n(w)n(een)h (the)g(v)n(ertices)f(of)h(the)g(t)n(w)n(o-pair.)34 b(When)26 b(the)116 4956 y(algorithm)20 b(ev)n(en)n(tually)g(fails)h(to)g(\014nd) h(a)f(t)n(w)n(o-pair,)f(the)i(original)116 5056 y(graph)27 b(is)g(w)n(eakly)g(c)n(hordal)f(if)i(and)f(only)g(if)h(the)g(\014nal)g (graph)e(is)116 5156 y(a)h(clique.)266 5255 y(A)41 b Fm(c)l(o-p)l(air)j(e)l(dge)e Fj(is)f(the)h(edge)f(induced)h(b)n(y)f(a)g (co-pair.)116 5355 y(Our)d(algorithm)f(can)h(b)r(e)h(though)n(t)f(of)h (as)e(the)i(execution)f(of)116 5455 y(the)47 b(ab)r(o)n(v)n(e)e (algorithm)g(in)h(the)h(complemen)n(t:)74 b(rep)r(eatedly)116 5554 y(\014nd)28 b(a)f(co-pair)f(and)h(delete)h(the)g(induced)g(edge)f (\(but)h(not)g(the)116 5654 y(v)n(ertices\).)35 b(Since)23 b(a)f(graph)g(is)h(w)n(eakly)e(c)n(hordal)h(if)h(and)g(only)f(its)116 5753 y(complemen)n(t)d(is)g(w)n(eakly)f(c)n(hordal,)h(the)h(input)g (graph)d(is)i(w)n(eakly)2200 523 y(c)n(hordal)38 b(if)h(and)g(only)g (if)h(our)e(algorithm)g(deletes)h(all)g(of)g(its)2200 623 y(edges.)d(W)-7 b(e)27 b(use)g Fm(\014nd-p)l(air)g Fj(as)f(the)h(fundamen)n(tal)g(subroutine.)2200 722 y(After)32 b(a)g(co-pair)e(is)i(found)g(and)g(its)g(edge)f(deleted,)j(the)e(next) 2200 822 y(co-pair)23 b(is)h(found)g(b)n(y)g(restarting)f Fm(\014nd-p)l(air)h Fj(if)h(the)g(curren)n(t)e(set)2200 922 y Fl(X)44 b Fj(still)38 b(con)n(tains)e(an)h(edge)g(and)g(b)n(y)g (p)r(opping)h(bac)n(k)e(to)i(the)2200 1021 y(previous)28 b(set)g Fl(X)36 b Fj(otherwise.)j(In)29 b(this)g(section)f(w)n(e)h(sho) n(w)f(that)2200 1121 y(our)37 b(recognition)f(algorithm)h(is)h(correct) e(and)i(tak)n(es)f(O\()p Fl(m)4132 1091 y Fe(2)4169 1121 y Fj(\))2200 1220 y(time.)2200 1429 y Fr(Algorithm)26 b Fm(wc-r)l(e)l(c)l(o)l(gnize)2200 1529 y Fr(Input)p Fj(:)38 b(A)27 b(graph)g Fl(G)2200 1629 y Fr(Output)p Fj(:)37 b(`y)n(es')27 b(if)h Fl(G)g Fj(is)g(w)n(eakly)e(c)n(hordal,)g (otherwise)h(`no')2200 1828 y Fr(b)s(egin)2288 1927 y Fl(H)j Fi( )23 b Fl(V)18 b Fj(\()p Fl(G)p Fj(\))2288 2027 y Fr(while)26 b Fj(\()p Fl(G)p Fj([)p Fl(H)7 b Fj(])28 b(has)f(a)h(co-pair\))e Fr(do)2375 2127 y Fi(f)p Fl(x;)14 b(y)s Fi(g)22 b( )28 b Fm(\014nd-p)l(air)p Fj(\()p Fl(G)p Fj([)p Fl(H)7 b Fj(]\))2375 2226 y Fr(if)28 b Fi(f)p Fl(x;)14 b(y)s Fi(g)26 b Fj(not)i(co-pair)e(of)i Fl(G)g Fr(then)f Fj(return)g(`no')2375 2326 y Fr(else)2463 2426 y Fj(delete)h(\()p Fl(x;)14 b(y)s Fj(\))28 b(from)f Fl(G)2463 2525 y Fr(if)g Fl(G)p Fj([)p Fl(H)7 b Fj(])28 b(has)f(no)h(edge)f Fr(then)2551 2625 y(if)g Fj(stac)n(k)g(empt)n(y)g Fr(then)h Fj(return)f(`y)n(es')2551 2725 y Fr(else)f Fl(H)k Fi( )23 b Fl(H)7 b Fi([)28 b Fj(set)f(on)h(top)f(stac)n(k)g Fr(endif)g(endif) 2375 2824 y(endif)2375 2924 y Fj(restart)g(on)g(eac)n(h)g(connected)g (comp)r(onen)n(t)h(of)f Fl(H)2288 3023 y Fr(endwhile)2200 3123 y(end)2350 3332 y Fj(It)20 b(is)f(not)h(di\016cult)g(to)g(test)g (in)g(O\()p Fl(n)s Fj(+)s Fl(m)p Fj(\))e(time)j(whether)e(an)2200 3432 y(edge)24 b(induces)g(a)f(co-pair,)h(as)f(w)n(e)h(no)n(w)f (explain.)36 b(Nonadjacen)n(t)2200 3531 y(v)n(ertices)g(form)g(a)g(t)n (w)n(o-pair)e(if)k(and)e(only)g(if)h(remo)n(ving)e(their)2200 3631 y(common)29 b(neigh)n(b)r(ors)f(lea)n(v)n(es)g(the)i(v)n(ertices)e (in)i(di\013eren)n(t)g(com-)2200 3730 y(p)r(onen)n(ts,)e(so)e(adjacen)n (t)h(v)n(ertices)g(form)g(a)g(co-pair)f(if)i(and)f(only)2200 3830 y(if)i(remo)n(ving)e(their)i(common)f(nonneigh)n(b)r(ors)e(lea)n (v)n(es)h(the)i(v)n(er-)2200 3930 y(tices)c(in)g(di\013eren)n(t)g(comp) r(onen)n(ts)g(of)g(the)g(complemen)n(t.)36 b(Giv)n(en)2200 4029 y(t)n(w)n(o)h(v)n(ertices,)i(it)f(is)g(easy)f(to)h(remo)n(v)n(e)e (their)h(common)g(non-)2200 4129 y(neigh)n(b)r(ours)23 b(in)i(O\()p Fl(n)p Fj(\))g(time,)h(and)e(to)g(determine)h(in)g(O\()p Fl(n)12 b Fj(+)g Fl(m)p Fj(\))2200 4229 y(time)35 b(whether)e(in)i(the) f(reduced)g(graph)f(the)h(v)n(ertices)f(are)g(in)2200 4328 y(the)23 b(same)f(comp)r(onen)n(t)h(of)f(the)h(complemen)n(t,)h (for)e(example)g(b)n(y)2200 4428 y(starting)h(from)h(one)g(of)g(the)h (t)n(w)n(o)e(v)n(ertices)g(and)h(constructing)f(a)2200 4527 y(breadth)i(\014rst)g(searc)n(h)f(tree)h(of)h(the)f(reduced)g (graph's)g(comple-)2200 4627 y(men)n(t.)47 b(Since)31 b(testing)g(whether)f(an)h(edge)f(induces)h(a)g(co-pair)2200 4727 y(tak)n(es)c(O\()p Fl(n)p Fj(+)p Fl(m)p Fj(\))g(time,)i(and)e (since)h(eac)n(h)f(edge)g(is)h(deleted)g(im-)2200 4826 y(mediately)e(after)g(it)h(is)f(tested,)h(the)g(total)f(time)h(sp)r(en) n(t)g(on)f(this)2200 4926 y(task)h(o)n(v)n(er)f(the)i(whole)f (algorithm)g(is)g(O\()p Fl(m)3566 4896 y Fe(2)3603 4926 y Fj(\).)2350 5026 y(Let)k Fl(e)h Fj(b)r(e)g(a)f(co-pair)g(edge)g(of)g Fl(G)i Fj(returned)e(b)n(y)g Fm(\014nd-p)l(air)2200 5125 y Fj(and)g(let)g Fl(G)2553 5095 y Fc(0)2607 5125 y Fj(b)r(e)g Fl(G)21 b Fi(\000)f Fl(e)p Fj(.)46 b(Recall)30 b(that)h Fm(\014nd-p)l(air)g Fj(main)n(tains)f(a)2200 5225 y(set)24 b Fl(X)30 b Fj(suc)n(h)23 b(that)h Fl(e)f Fj(is)g(an)h(edge)f(of)g Fl(G)p Fj([)p Fl(X)7 b Fj(].)36 b(W)-7 b(e)24 b(consider)e(three)2200 5324 y(p)r(ossibilities:)39 b Fl(G)2746 5294 y Fc(0)2770 5324 y Fj([)p Fl(X)7 b Fj(])28 b(is)g(connected,)h Fl(G)3481 5294 y Fc(0)3505 5324 y Fj([)p Fl(X)7 b Fj(])28 b(is)g(disconnected) 2200 5424 y(but)g(has)f(at)h(least)f(one)g(edge,)g(and)h Fl(G)3387 5394 y Fc(0)3410 5424 y Fj([)p Fl(X)7 b Fj(])27 b(has)h(no)f(edges.)2200 5633 y Fh(Lemma)k(3.1.)41 b Fm(L)l(et)g Fl(G)2916 5603 y Fc(0)2940 5633 y Fj([)p Fl(X)7 b Fj(])41 b Fm(b)l(e)h(c)l(onne)l(cte)l(d.)74 b(If)42 b Fl(G)h Fm(is)f(we)l(akly)2200 5733 y(chor)l(dal)32 b(then)d(every)i(c)l(o-p)l(air)g(of)f Fl(G)p Fj([)p Fl(X)7 b Fj(])30 b Fm(is)g(a)g(c)l(o-p)l(air)h(of)f Fl(G)4085 5703 y Fc(0)4109 5733 y Fm(.)p eop %%Page: 45 4 45 3 bop -116 299 a Fd(Pro)r(ceedings)26 b(of)h(11th)g(A)n(CM-SIAM)h (SOD)n(A)g(\(2000\))e(42-49)2075 b Fj(45)-116 523 y Fm(Pr)l(o)l(of.)43 b Fj(Recall)35 b(that)h Fl(X)42 b Fj(is)36 b(a)f(handle)h(of)g Fl(G)p Fj(.)62 b(Supp)r(ose)35 b(that)-116 623 y(w)n(e)c(start)g (algorithm)g Fm(\014nd-hand)t(le)i Fj(on)e Fl(G)1215 593 y Fc(0)1270 623 y Fj(with)i(an)n(y)e(edge)g(of)-116 722 y Fl(G)p Fj([)p Fl(X)7 b Fj(])18 b(as)g(our)g(initial)g(edge)g Fl(e)h Fj(and)f(an)g(initial)h(v)n(ertex)e Fl(v)22 b Fj(from)c(the)-116 822 y(cohandle)i Fl(Y)39 b Fj(of)21 b Fl(X)7 b Fj(.)34 b(It)21 b(is)g(not)g(di\016cult)g(to)g(see)g(that)g (at)f(the)h(end)-116 922 y(of)j(the)g(initialization)g(stage,)g(the)g (set)g Fl(X)31 b Fj(found)24 b(b)n(y)g(algorithm)-116 1021 y Fm(\014nd-hand)t(le)38 b Fj(is)e(the)h(same)f(as)g(our)g(set)h Fl(X)7 b Fj(.)63 b(The)37 b(algorithm)-116 1121 y(will)26 b(\014nd)g Fl(Y)44 b Fj(as)25 b(the)h(cohandle,)f(with)h Fl(N)9 b Fj(\()p Fl(Y)19 b Fj(\))26 b(consisting)e(of)i(all)-116 1220 y(separators)e(of)j(handles)f(whic)n(h)h(con)n(tained)f Fl(Y)46 b Fj(and)27 b Fl(X)33 b Fj(as)26 b(w)n(ell)-116 1320 y(as)f(the)i(separator)d(b)r(et)n(w)n(een)i Fl(Y)45 b Fj(and)26 b Fl(X)7 b Fj(,)26 b(with)h Fl(X)32 b Fj(as)26 b(a)g(handle)-116 1420 y(in)i(this)g(graph.)37 b(Since)28 b Fl(X)34 b Fj(remains)27 b(a)g(handle)h(in)g Fl(G)1541 1390 y Fc(0)1565 1420 y Fj(,)g(Lemma)-116 1519 y(2.1)c(sa)n(ys)f(that)j (w)n(e)e(ma)n(y)g(con)n(tin)n(ue)h(our)f(searc)n(h)f(for)i(co-pairs)e (of)-116 1619 y Fl(G)-51 1589 y Fc(0)-6 1619 y Fj(b)n(y)f(lo)r(oking)e (within)j(the)f(subgraph)f(induced)h(b)n(y)g Fl(X)7 b Fj(.)34 b(Th)n(us,)-116 1719 y(w)n(e)27 b(restart)f(our)g(algorithm)g (with)i Fl(X)34 b Fj(as)26 b(our)h(curren)n(t)f(set.)p 1826 1721 59 4 v 1826 1662 V 1825 1719 4 59 v 1883 1719 V 33 1901 a(The)32 b(situation)f(is)g(quite)h(similar)f(if)h Fl(G)1281 1871 y Fc(0)1336 1901 y Fj(is)f(disconnected)-116 2001 y(but)c(con)n(tains)f(at)h(least)f(one)h(edge.)36 b(Eac)n(h)26 b(connected)g(comp)r(o-)-116 2100 y(nen)n(t)e(of)f Fl(G)p Fj([)p Fl(X)7 b Fj(])23 b(could)h(b)r(e)g(pro)r(duced)f(as)g Fl(X)30 b Fj(in)24 b Fl(G)1407 2070 y Fc(0)1454 2100 y Fj(b)n(y)f(the)h(same)-116 2200 y(argumen)n(t)31 b(giv)n(en)h(ab)r(o) n(v)n(e.)51 b(Th)n(us)32 b(w)n(e)g(restart)g(our)g(algorithm)-116 2300 y(lo)r(oking)39 b(for)g(co-pairs)f(separately)g(within)j(eac)n(h)e (connected)-116 2399 y(comp)r(onen)n(t)27 b(of)h Fl(G)p Fj([)p Fl(X)7 b Fj(].)-116 2582 y Fh(Lemma)31 b(3.2.)40 b Fm(L)l(et)22 b Fl(e)f Fm(b)l(e)h(the)g(last)g(e)l(dge)g(in)g Fl(G)p Fj([)p Fl(X)7 b Fj(])22 b Fm(and)g(let)g Fl(X)1754 2594 y Fe(2)1812 2582 y Fm(b)l(e)-116 2682 y(the)28 b(union)g(of)h Fl(X)35 b Fm(with)29 b(the)f(top)h(of)g(the)g(stack.)38 b(If)29 b Fl(G)g Fm(is)f(we)l(akly)-116 2781 y(chor)l(dal)h(then)f (every)h(c)l(o-p)l(air)g(of)f(e)l(ach)h(c)l(onne)l(cte)l(d)f(c)l(omp)l (onent)-116 2881 y(of)i Fl(G)p Fj([)p Fl(X)138 2893 y Fe(2)176 2881 y Fj(])f Fm(is)i(a)f(c)l(o-p)l(air)h(of)f Fl(G)829 2851 y Fc(0)853 2881 y Fm(.)-116 3064 y(Pr)l(o)l(of.)43 b Fj(Restart)29 b(the)h(algorithm)f(with)i(an)n(y)e(connected)g(com-) -116 3163 y(p)r(onen)n(t)f Fl(C)34 b Fj(of)28 b Fl(X)418 3175 y Fe(2)483 3163 y Fj(as)g(our)f(curren)n(t)g Fl(X)34 b Fj(set.)39 b(W)-7 b(e)28 b(sho)n(w)f(that)h Fl(C)-116 3263 y Fj(could)19 b(ha)n(v)n(e)g(b)r(een)h(obtained)g(as)f(the)h(set)g Fl(X)26 b Fj(b)n(y)20 b(an)f(appropriate)-116 3362 y(set)27 b(of)h(c)n(hoices)e(in)i(algorithm)f Fm(\014nd-p)l(air)h Fj(on)f Fl(G)1377 3332 y Fc(0)1401 3362 y Fj(.)33 3462 y(Consider)i(an)n(y)g(handle)h Fl(H)36 b Fj(already)29 b(found)h(b)n(y)f(the)h(algo-)-116 3562 y(rithm)22 b(suc)n(h)g(that)h Fl(X)28 b Fj(is)23 b(a)e(subset)i(of)f Fl(H)7 b Fj(.)35 b Fl(H)29 b Fj(-)22 b Fl(X)29 b Fj(is)22 b(connected;)-116 3661 y Fm(\014nd-hand)t(le)j Fj(remo)n(v)n(es)c(v)n(ertices)i(from)g (the)h Fl(X)30 b Fj(set)23 b(only)g(if)h(they)-116 3761 y(are)19 b(adjacen)n(t)i(to)f(v)n(ertices)g(already)f(remo)n(v)n(ed)g (from)h(the)i Fl(X)27 b Fj(set.)-116 3861 y(Th)n(us,)f Fl(H)32 b Fj(remains)25 b(a)h(handle)f(in)h Fl(G)1018 3830 y Fc(0)1042 3861 y Fj(,)g(with)g(the)h(only)e(p)r(ossible)-116 3960 y(c)n(hange)c(b)r(eing)h(the)g(remo)n(v)-5 b(al)21 b(of)h(v)n(ertices)f(of)h Fl(X)29 b Fj(whic)n(h)22 b(b)r(ecome)-116 4060 y(isolated)j(with)h(resp)r(ect)f(to)g Fl(H)32 b Fj(and)26 b(do)f(not)g(a\013ect)h(our)f(task)g(of)-116 4159 y(\014nding)j(co-pairs)d(of)j Fl(G)p Fj(.)33 4259 y(Th)n(us,)50 b(w)n(e)c(only)f(need)h(to)g(consider)f(a)g(single)g (call)h(to)-116 4359 y(pro)r(cedure)32 b Fm(\014nd-hand)t(le)p Fj(.)54 b(No)32 b(edge)h(of)g Fl(X)39 b Fj(could)33 b(ha)n(v)n(e)e(b)r (een)-116 4458 y(c)n(hosen)42 b(as)g Fl(e)g Fj(except)h(in)g(the)g (last)f(step;)51 b(this)43 b(w)n(ould)f(lead)-116 4558 y(to)36 b(\014nding)h(the)f(handle)h Fl(X)42 b Fj(immediately)-7 b(.)64 b(Run)37 b(algorithm)-116 4658 y Fm(\014nd-hand)t(le)44 b Fj(using)e(the)h(same)f(c)n(hoices)g(of)g Fl(v)k Fj(and)d Fl(e)f Fj(made)-116 4757 y(originally)-7 b(.)47 b(When)33 b(computing)e(the)h(connected)g(comp)r(onen)n(t)-116 4857 y(whic)n(h)26 b(con)n(tains)f Fl(v)s Fj(,)h(the)g(only)g(v)n (ertices)f(whic)n(h)h(the)g(algorithm)-116 4956 y(can)i(use)h(but)g (could)f(not)h(use)g(previously)e(are)h(v)n(ertices)g(of)g Fl(X)7 b Fj(.)-116 5056 y(Ho)n(w)n(ev)n(er,)39 b(an)n(y)e(v)n(ertex)h (of)g Fl(X)45 b Fj(can)38 b(only)g(b)r(e)g(reac)n(hed)f(via)h(a)-116 5156 y(path)28 b(through)e Fl(N)9 b Fj(\()p Fl(X)e Fj(\).)37 b(No)28 b(v)n(ertex)e(of)i Fl(N)9 b Fj(\()p Fl(X)e Fj(\))27 b(is)h(added)f(to)h Fl(Y)-116 5255 y Fj(in)e(the)g(original)e (algorithm,)h(so)g(no)h(v)n(ertex)e(of)i Fl(X)32 b Fj(can)26 b(ev)n(er)e(b)r(e)-116 5355 y(added)g(to)g Fl(Y)42 b Fj(in)24 b(this)h(w)n(a)n(y)-7 b(.)34 b(Th)n(us,)25 b(the)f(only)g(c)n (hange)f(from)g(the)-116 5455 y(previous)32 b(run)h(of)h(the)g (algorithm)e(whic)n(h)h(can)g(o)r(ccur)g(is)g(that)-116 5554 y(some)23 b(set)h Fl(X)283 5566 y Fk(i)335 5554 y Fj(found)g(previously)e(can)i(b)r(ecome)g(disconnected.)33 5654 y(First,)35 b(w)n(e)e(will)g(ignore)f(v)n(ertices)g(whic)n(h)i (are)e(isolated)g(in)-116 5753 y Fl(X)-47 5765 y Fe(2)-10 5753 y Fj(,)39 b(and)e(argue)e(that)i(nonisolated)f(v)n(ertices)g(will) h(nev)n(er)f(go)1968 523 y(in)n(to)j(separate)f(connected)i(comp)r (onen)n(ts.)72 b(There)39 b(m)n(ust)h(b)r(e)1968 623 y(some)29 b(path)g(b)r(et)n(w)n(een)h(the)f(comp)r(onen)n(ts)g(in)h Fl(X)7 b Fj(,)29 b(since)h Fl(X)36 b Fj(w)n(as)1968 722 y(connected.)92 b(Consider)45 b(a)g(shortest)g(path)i(\()p Fl(x)3520 692 y Fc(0)3520 743 y Fe(1)3558 722 y Fl(x)3605 734 y Fe(1)3656 722 y Fl(:)14 b(:)g(:)g(x)3814 734 y Fe(2)3851 722 y Fl(x)3898 692 y Fc(0)3898 743 y Fe(2)3936 722 y Fj(\))1968 822 y(b)r(et)n(w)n(een)42 b(comp)r(onen)n(ts)g(of)h Fl(X)2954 834 y Fe(2)2991 822 y Fj(,)j(where)c Fl(x)3362 834 y Fe(1)3442 822 y Fj(and)g Fl(x)3665 834 y Fe(2)3746 822 y Fj(are)f(in)1968 922 y Fl(X)7 b Fj(,)32 b Fl(x)2146 891 y Fc(0)2146 942 y Fe(1)2215 922 y Fj(and)f Fl(x)2427 891 y Fc(0)2427 942 y Fe(2)2497 922 y Fj(are)f(in)i Fl(X)2809 934 y Fe(2)2878 922 y Fj(-)f Fl(X)7 b Fj(,)32 b(and)g(the)g(subpath)f Fl(P)44 b Fj(from)1968 1021 y Fl(x)2015 1033 y Fe(1)2090 1021 y Fj(to)38 b Fl(x)2249 1033 y Fe(2)2324 1021 y Fj(only)g(uses)f(v) n(ertices)g(of)h Fl(X)7 b Fj(.)66 b Fl(P)50 b Fj(m)n(ust)38 b(b)r(e)g(empt)n(y)-7 b(,)1968 1121 y(since)40 b(if)h(there)f(is)g(an)g (edge)g(b)r(et)n(w)n(een)g Fl(x)3304 1133 y Fe(1)3383 1121 y Fj(and)g Fl(x)3604 1133 y Fe(2)3682 1121 y Fj(then)h Fl(x)3931 1091 y Fc(0)3931 1141 y Fe(1)1968 1220 y Fj(w)n(ould)g(ha)n (v)n(e)g(to)h(b)r(e)g(adjacen)n(t)g(to)g(at)g(least)f(one)h(endp)r(oin) n(t,)1968 1320 y(either)36 b(connecting)g(t)n(w)n(o)g(comp)r(onen)n(ts) g(of)h Fl(X)3441 1332 y Fe(2)3514 1320 y Fj(or)f(making)g(a)1968 1420 y(shorter)41 b(path)j(b)r(et)n(w)n(een)f(comp)r(onen)n(ts.)83 b(Since)43 b Fl(x)3626 1390 y Fc(0)3626 1440 y Fe(1)3707 1420 y Fj(and)g Fl(x)3931 1390 y Fc(0)3931 1440 y Fe(2)1968 1519 y Fj(w)n(ere)c(among)g(the)i(last)f(set)h(of)f(v)n(ertices)f(remo) n(v)n(ed)g(from)h Fl(X)1968 1619 y Fj(in)32 b(the)h(earlier)d(iterated) i(pro)r(cedure,)h(this)f(w)n(as)f(caused)h(b)n(y)g(a)1968 1719 y(re\014nemen)n(t)37 b(using)g(some)g Fl(v)k Fj(and)d Fl(e)p Fj(,)i(where)d Fl(e)g Fj(w)n(as)g(an)g(edge)1968 1818 y(from)29 b Fl(X)7 b Fj(.)42 b(Both)29 b Fl(x)2562 1788 y Fc(0)2562 1839 y Fe(1)2629 1818 y Fj(and)h Fl(x)2840 1788 y Fc(0)2840 1839 y Fe(2)2907 1818 y Fj(are)e(in)i Fl(N)9 b Fj(\()p Fl(e)p Fj(\))30 b(for)f(an)n(y)f(edge)h Fl(e)h Fj(of)1968 1918 y Fl(X)7 b Fj(,)26 b(so)h(these)g(are)g(remo)n (v)n(ed)e(from)i Fl(X)34 b Fj(only)27 b(if)h(they)f(are)g(in)g(the)1968 2017 y(set)i Fl(N)9 b Fj(\()p Fl(Y)19 b Fj(\).)43 b(The)29 b(shortest)g(path)g(from)g Fl(x)3301 1987 y Fc(0)3301 2038 y Fe(1)3369 2017 y Fj(to)g Fl(x)3519 1987 y Fc(0)3519 2038 y Fe(2)3586 2017 y Fj(through)g Fl(Y)1968 2117 y Fj(giv)n(es)h(us)i(a)g(hole)g(of)g(length)g(at)g(least)f(\014v)n(e)h (together)f(with)i Fl(x)3931 2129 y Fe(1)1968 2217 y Fj(and)27 b Fl(x)2176 2229 y Fe(2)2214 2217 y Fj(.)2117 2316 y(Th)n(us,)58 b(the)52 b(only)g(di\013erence)f(that)i(can)e(o)r (ccur)g(while)1968 2416 y(re\014ning)32 b Fl(G)2338 2386 y Fc(0)2395 2416 y Fj(is)h(that)h(isolated)e(v)n(ertices)g(of)i Fl(X)3456 2428 y Fe(2)3526 2416 y Fj(ma)n(y)e(go)h(in)n(to)1968 2516 y(a)e(di\013eren)n(t)g(connected)h(comp)r(onen)n(t.)48 b(This)32 b(will)f(only)g(a\013ect)1968 2615 y(the)38 b(algorithm)g(if)h(for)f(some)f(isolated)h(v)n(ertex)g Fl(i)g Fj(whic)n(h)g(has)1968 2715 y(already)25 b(b)r(een)j(separated)e (from)h(the)h(comp)r(onen)n(t)f(con)n(taining)1968 2814 y(nonisolated)50 b(v)n(ertices)h(of)g Fl(X)2942 2826 y Fe(2)2979 2814 y Fj(,)58 b(a)51 b(re\014nemen)n(t)g(step)h(of)f Fl(G)1968 2914 y Fj(c)n(ho)r(oses)18 b Fl(v)23 b Fj(and)d(an)g(edge)f (\()p Fl(i;)14 b(j)5 b Fj(\))20 b(as)g(its)g(initial)g(v)n(ertex)f(and) h(edge,)1968 3014 y(where)26 b Fl(j)31 b Fj(is)c(in)g Fl(N)9 b Fj(\()p Fl(X)e Fj(\).)36 b(V)-7 b(ertex)27 b Fl(j)k Fj(cannot)26 b(ha)n(v)n(e)g(edges)g(to)g(an)n(y)1968 3113 y(v)n(ertices)33 b(of)h Fl(X)41 b Fj(other)33 b(than)i Fl(i)p Fj(,)g(or)f Fl(i)g Fj(w)n(ould)f(not)i(b)r(e)f(isolated)1968 3213 y(at)40 b(this)i(stage.)75 b(Th)n(us,)44 b Fl(X)j Fj(m)n(ust)41 b(induce)h(a)e(star)g(cen)n(tered)1968 3313 y(at)e Fl(i)p Fj(,)i(since)e Fl(j)44 b Fj(m)n(ust)38 b(see)g(ev)n(ery)f(edge)h(in)g Fl(X)7 b Fj(.)68 b(Let)39 b Fl(x)3736 3282 y Fc(0)3760 3313 y Fj(,)p Fl(j)3822 3282 y Fc(0)3883 3313 y Fj(b)r(e)1968 3412 y(an)n(y)33 b(edge)h(of)h Fl(X)2498 3424 y Fe(2)2569 3412 y Fj(with)g Fl(x)g Fj(in)g Fl(X)41 b Fj(and)34 b Fl(j)3268 3382 y Fc(0)3326 3412 y Fj(in)h Fl(V)53 b Fj(-)34 b Fl(X)7 b Fj(.)57 b(If)35 b Fl(j)40 b Fj(is)1968 3512 y(adjacen)n(t)34 b(to)h Fl(j)2455 3482 y Fc(0)2478 3512 y Fj(,)i Fl(i)e Fj(will)g(b)r(e)h(in)f(the)g(same)g(comp)r(onen)n(t)f(as)h Fl(x)3945 3482 y Fc(0)1968 3611 y Fj(at)c(this)g(stage,)g(while)g(if)h Fl(j)k Fj(and)31 b Fl(j)3052 3581 y Fc(0)3107 3611 y Fj(are)f(nonadjacen)n(t)g(w)n(e)h(can)1968 3711 y(complete)h(the)g Fl(P)2523 3723 y Fe(4)2593 3711 y Fj(\()p Fl(j;)14 b(i;)g(x)2809 3681 y Fc(0)2832 3711 y Fl(;)g(j)2908 3681 y Fc(0)2932 3711 y Fj(\))32 b(to)g(b)r(e)g(a)g(hole)g(b)n(y)f(using)h(only)1968 3811 y(v)n(ertices)37 b(of)i(the)g(cohandle.)69 b(Therefore,)40 b(eac)n(h)e(step)h(of)f(the)1968 3910 y(re\014nemen)n(t)26 b(pro)r(cedure)g(of)g Fl(G)2918 3880 y Fc(0)2969 3910 y Fj(will)h(matc)n(h)f(the)h(same)f(step)h(in)1968 4010 y(the)h(re\014nemen)n(t)f(of)h Fl(G)p Fj(.)p 3910 4012 59 4 v 3910 3954 V 3909 4010 4 59 v 3967 4010 V 1968 4172 a Fh(Theorem)k(3.1.)40 b Fm(A)n(lgorithm)32 b(wc-r)l(e)l(c)l(o)l (gnize)f(c)l(orr)l(e)l(ctly)g(deter-)1968 4271 y(mines)e(whether)i Fl(G)f Fm(is)g(we)l(akly)h(chor)l(dal)h(in)e Fl(O)r Fj(\()p Fl(m)3525 4241 y Fe(2)3563 4271 y Fj(\))g Fm(time.)1968 4433 y(Pr)l(o)l(of.)43 b Fj(The)49 b(correctness)f(of)i(the)g (algorithm)e(is)h(a)h(conse-)1968 4533 y(quence)37 b(of)h(the)g (preceding)f(lemmas.)68 b(Eac)n(h)36 b(time)j(a)e(set)h Fl(X)1968 4633 y Fj(is)30 b(re\014ned)g(to)g(a)g(set)h Fl(X)2714 4602 y Fc(0)2736 4633 y Fj(,)h(the)e(edges)g(of)h Fl(G)p Fj([)p Fl(X)3423 4602 y Fc(0)3445 4633 y Fj(])g(will)g(nev)n(er) e(b)r(e)1968 4732 y(in)24 b(a)f(subgraph)g(together)g(with)i(edges)e (outside)h(of)f Fl(G)p Fj([)p Fl(X)3748 4702 y Fc(0)3771 4732 y Fj(].)36 b(W)-7 b(e)1968 4832 y(ma)n(y)35 b(think)h(of)g(eac)n (h)g(step)g(as)f(sub)r(dividing)i(a)e(set)h(of)g(edges:)1968 4932 y(eac)n(h)25 b(re\014nemen)n(t)h(step)g(increases)f(the)i(n)n(um)n (b)r(er)e(of)i(subsets)f(of)1968 5031 y(edges,)i(so)g(there)g(at)h (most)f Fl(m)g Fj(re\014nemen)n(t)h(steps.)40 b(Since)28 b(eac)n(h)1968 5131 y(re\014nemen)n(t)k(step)g(tak)n(es)f(O\()p Fl(m)p Fj(\))h(time,)i(the)f(total)f(time)g(sp)r(en)n(t)1968 5230 y(b)n(y)27 b(the)h(algorithm)e(is)i(O\()p Fl(m)2858 5200 y Fe(2)2895 5230 y Fj(\).)p 3910 5232 59 4 v 3910 5174 V 3909 5230 4 59 v 3967 5230 V 1968 5430 a Fr(4)95 b(On)26 b(\014nding)f(a)i(pro)s(of)e(that)i(a)g(graph)f(is)g(not)g(w)m (eakly)2111 5529 y(c)m(hordal)1968 5654 y Fj(The)31 b(recognition)g (algorithm)f(of)i(the)g(previous)f(section,)h(lik)n(e)1968 5753 y(the)40 b(algorithm)g(of)g([8])g(it)h(is)f(based)g(on,)j(do)r(es) d(not)h(pro)n(vide)p eop %%Page: 46 5 46 4 bop 116 299 a Fj(46)2953 b Fd(Ha)n(yw)n(ard,)26 b(Spinrad,)h(Sritharan)116 523 y Fj(the)36 b(most)e(natural)h(evidence) g(that)g(a)f(graph)g(is)h(not)g(w)n(eakly)116 623 y(c)n(hordal,)60 b(namely)55 b(a)f(hole)h(in)g(either)f(the)h(graph)f(or)g(its)116 722 y(complemen)n(t.)h(In)34 b(this)g(section,)g(w)n(e)g(pro)n(vide)e (an)h(algorithm)116 822 y(to)24 b(\014nd)g(a)g(hole)f(or)g(an)n(tihole) g(in)h(a)f(graph)g(whic)n(h)h(is)g(not)f(w)n(eakly)116 922 y(c)n(hordal,)40 b(suc)n(h)e(that)g(the)h(running)f(time)g(of)h (the)f(algorithm)116 1021 y(is)k(dominated)f(b)n(y)g(the)h(running)f (time)h(of)g(the)g(recognition)116 1121 y(algorithm.)81 b(The)43 b(\014rst)g(v)n(ertex)f(pair)g(found)h(whic)n(h)f(is)h(not)116 1220 y(a)35 b(co-pair)f(of)h(the)h(graph)e(giv)n(es)g(us)h(a)g (starting)g(p)r(osition)g(for)116 1320 y(\014nding)f(the)g(hole)f(or)g (an)n(tihole)g(easily)-7 b(.)54 b(By)34 b(con)n(trast,)g(if)g(the)116 1420 y(O\()p Fl(n)263 1390 y Fe(4)300 1420 y Fj(\))k(recognition)f (algorithm)g(of)g([8])h(is)g(used,)i(w)n(e)e(get)f(no)116 1519 y(information)26 b(ab)r(out)h(where)f(the)h(hole)f(migh)n(t)h(b)r (e)g(if)g(the)g(input)116 1619 y(graph)g(con)n(tains)f(no)i(t)n(w)n (o-pairs.)266 1719 y(Let)49 b(us)g(consider)f(the)i(b)r(eha)n(vior)e (of)h(the)h(recognition)116 1818 y(algorithm)33 b(when)h(a)g(graph)f Fl(G)h Fj(that)g(is)g(not)g(w)n(eakly)f(c)n(hordal)116 1918 y(is)c(giv)n(en)f(as)h(input.)42 b(The)29 b(algorithm)f(tak)n(es)g (O\()p Fl(n)1694 1888 y Fe(4)1731 1918 y Fj(\))i(time)f(and)116 2017 y(turns)36 b Fl(G)h Fj(in)n(to)f(a)f(graph)g(that)i(is)f(not)g(a)g (clique)g(and)g(has)f(no)116 2117 y(t)n(w)n(o-pairs.)40 b(Let)30 b(us)f(refer)g(to)g(this)h(resulting)f(graph)f(that)i(has)116 2217 y(no)41 b(t)n(w)n(o-pairs)e(as)i Fl(G)800 2187 y Fc(0)823 2217 y Fj(.)78 b(It)42 b(is)f(an)g(ob)n(vious)f(consequence)g (of)116 2316 y(Theorem)33 b(1.1)h(that)g Fl(G)865 2286 y Fc(0)922 2316 y Fj(has)g(either)g(a)f(hole)h(or)f(an)h(an)n(tihole.) 116 2416 y(More)24 b(imp)r(ortan)n(tly)-7 b(,)26 b(it)f(follo)n(ws)f (from)h(the)h(correctness)d(of)i(the)116 2516 y(recognition)37 b(algorithm)g(that)i(ev)n(ery)e(hole)h(and)g(an)n(tihole)f(of)116 2615 y(the)i(input)h(graph)d(is)i(also)f(presen)n(t)g(in)h Fl(G)1495 2585 y Fc(0)1557 2615 y Fj(and)f(vice)h(v)n(ersa.)116 2715 y(Therefore,)d(if)f(w)n(e)g(w)n(ere)f(to)h(lo)r(ok)f(for)g(holes)h (or)f(an)n(tiholes)g(in)116 2814 y(the)i(input)g(graph)e Fl(G)p Fj(,)k(it)e(su\016ces)f(to)g(lo)r(ok)f(for)h(them)h(in)g(the)116 2914 y(graph)31 b Fl(G)421 2884 y Fc(0)476 2914 y Fj(constructed)g(as)g (ab)r(o)n(v)n(e.)47 b(This)31 b(is)h(precisely)e(what)116 3014 y(our)36 b(algorithm)g(do)r(es.)64 b(In)37 b(the)g(follo)n(wing,)i (w)n(e)d(refer)g(to)h(the)116 3113 y(recognition)26 b(algorithm)h(from) g([8])g(as)g Fm(wt-r)l(e)l(c)l(o)l(gnition)p Fj(.)266 3213 y(Our)40 b(algorithm)f(tak)n(es)h(the)h(graph)f Fl(G)h Fj(giv)n(en)f(as)g(input)116 3313 y(and)53 b(runs)g Fm(wt-r)l(e)l(c)l(o)l(gnition)g Fj(on)p 1210 3246 66 4 v 53 w Fl(G)p Fj(.)114 b(If)p 1520 3246 V 53 w Fl(G)54 b Fj(turns)f(in)n(to)g(a)116 3412 y(clique)38 b(the)g(algorithm)f(rep)r (orts)g(that)h(the)h(input)f(is)g(w)n(eakly)116 3512 y(c)n(hordal.)47 b(Otherwise,)31 b(from)g(the)h(graph)e Fl(G)i Fj(with)g(no)f(co-pair)116 3611 y(the)23 b(algorithm)f(in)h(O\() p Fl(n)867 3581 y Fe(3)904 3611 y Fj(\))g(time)g(either)g(\014nds)g(a)f (prop)r(er)g(v)n(ertex)116 3711 y(subset)28 b Fl(H)35 b Fj(suc)n(h)27 b(that)i Fl(G)p Fj([)p Fl(H)7 b Fj(])28 b(has)f(no)h(co-pair)e(or)h(\014nds)h(a)f(hole)116 3811 y(or)j(an)h(an)n(tihole)f(in)h Fl(G)p Fj(.)48 b(In)31 b(the)g(former)f(case,)h(the)g(algorithm)116 3910 y(pro)r(ceeds)37 b(to)h(w)n(ork)e(on)h Fl(G)p Fj([)p Fl(H)7 b Fj(])38 b(to)g(\014nd)g(a)f(hole)h(or)f(an)n(tihole;)116 4010 y(in)g(the)g(latter)g(case)f(the)h(algorithm)e(ob)n(viously)g (terminates.)116 4110 y(W)-7 b(e)30 b(giv)n(e)e(a)h(description)f(of)h (our)g(algorithm)f(b)r(elo)n(w)h(and)g(then)116 4209 y(pro)n(v)n(e)d(its)i(complexit)n(y)-7 b(.)116 4380 y Fr(Algorithm)26 b Fm(\014nd-hole-or-antihole)116 4480 y Fr(Input)p Fj(:)38 b(A)28 b(graph)e Fl(G)116 4579 y Fr(Output)p Fj(:)37 b(Either)27 b(the)h(message)f(`)p Fl(G)h Fj(w)n(eakly)e(c)n(hordal')g(or)467 4679 y(a)h(hole)g(or)g(an)n (tihole)g(of)g Fl(G)116 4878 y Fr(b)s(egin)204 4981 y Fm(wt-r)l(e)l(c)l(o)l(gnition)6 b Fj(\()p 744 4915 V Fl(G)q Fj(\))204 5085 y Fr(if)27 b Fj(\()p 319 5018 V Fl(G)h Fj(is)g(a)f(clique\))h Fr(then)g Fj(output)g(`)p Fl(G)g Fj(w)n(eakly)e(c)n(hordal')204 5184 y Fr(else)g Fm(\014nd-pr)l(o)l(of)19 b Fj(\()p Fl(G)p Fj(\))28 b Fr(endif)116 5284 y(end)g Fm(\014nd-hole-or-antihole)116 5455 y Fr(Algorithm)e Fm(\014nd-pr)l(o)l(of)116 5554 y Fr(Input)p Fj(:)38 b(A)28 b(graph)e Fl(G)i Fj(with)g(no)f(co-pair)116 5654 y Fr(Output)p Fj(:)37 b(A)28 b(hole)g(or)e(an)n(tihole)h(of)h Fl(G)2200 523 y Fr(b)s(egin)2288 626 y Fj(/*)e Fl(G)i Fj(has)f(a)p 2709 560 65 4 v 28 w Fl(P)2773 638 y Fe(3)2838 626 y Fj(since)h Fl(G)g Fj(has)f(no)g(co-pair)f(*/)2288 726 y(\014nd)i(handle)f Fl(H)35 b Fj(of)27 b Fl(G)h Fj(and)g(cohandle)f Fl(J)35 b Fj(of)28 b Fl(H)2288 929 y Fj(/*)e(b)n(y)i(handle)f (de\014nition,)p 3173 862 66 4 v 28 w Fl(G)q Fj([)p Fl(H)7 b Fj(])27 b(is)h(not)f(a)g(clique)h(*/)2288 1028 y Fr(if)f Fl(G)p Fj([)p Fl(H)7 b Fj(])28 b(has)f(a)g(co-pair)f Fi(f)p Fl(x;)14 b(y)s Fi(g)27 b Fj(of)g Fl(G)p Fj([)p Fl(H)7 b Fj(])28 b Fr(then)2375 1128 y Fj(apply)g(the)g(algorithm)e(in) i(the)g(pro)r(of)f(of)g(Theorem)g(4.1)2288 1228 y Fr(else)2375 1327 y Fj(/*)g Fl(H)j Fi(\032)23 b Fl(V)18 b Fj(\()p Fl(G)p Fj(\))29 b(and)e Fl(G)p Fj([)p Fl(H)7 b Fj(])28 b(has)f(no)h(co-pair)e(*/)2375 1427 y Fm(\014nd-pr)l(o)l(of)19 b Fj(\()p Fl(G)p Fj([)p Fl(H)7 b Fj(]\))28 b Fr(endif)2200 1526 y(end)g Fm(\014nd-pr)l(o)l(of)2350 1707 y Fj(The)21 b(ideas)f(used)i(in)f(the)h(pro)r(of)e(of)i(the)f(follo)n(wing)f (theorem)2200 1806 y(are)27 b(similar)g(to)g(those)g(used)h(in)g(the)g (pro)r(of)f(of)g(Lemma)h(2.1.)2200 1987 y Fh(Theorem)k(4.1.)40 b Fm(L)l(et)27 b Fl(G)g Fm(b)l(e)h(a)f(gr)l(aph)i(with)e(no)h(c)l(o-p)l (air,)h(let)e Fl(H)2200 2086 y Fm(b)l(e)35 b(a)g(hand)t(le)i(of)e Fl(G)p Fm(,)i(and)e(let)g Fi(f)p Fl(x;)14 b(y)s Fi(g)34 b Fm(b)l(e)h(a)g(c)l(o-p)l(air)h(of)f Fl(G)p Fj([)p Fl(H)7 b Fj(])p Fm(.)2200 2186 y(Then)30 b(a)g(hole)h(or)f(an)f(antihole)i(of) g Fl(G)e Fm(c)l(an)h(b)l(e)g(found)g(in)f(O\()p Fl(n)4130 2156 y Fe(2)4167 2186 y Fm(\))2200 2286 y(time.)2200 2466 y(Pr)l(o)l(of.)43 b Fj(Let)30 b Fl(J)o(;)14 b(I)7 b(;)14 b(R)30 b Fj(b)r(e)g(as)f(de\014ned)h(in)g(the)g(pro)r(of)f(of)g (Lemma)2200 2565 y(2.1,)j(namely)f Fl(J)39 b Fj(is)31 b(a)g(cohandle)g(of)g Fl(H)7 b Fj(,)32 b Fl(I)k Fj(=)29 b Fl(N)9 b Fj(\()p Fl(H)e Fj(\))30 b(=)e Fl(N)9 b Fj(\()p Fl(J)f Fj(\),)2200 2665 y(and)28 b Fl(R)23 b Fj(=)g Fl(V)c Fj(\()p Fl(G)p Fj(\))g Fi(\000)f Fl(H)25 b Fi(\000)18 b Fl(I)7 b Fj(.)2350 2765 y(Since)19 b Fi(f)p Fl(x;)14 b(y)s Fi(g)19 b Fj(is)g(not)h(a)f(co-pair,)h(in)p 3448 2698 V 20 w Fl(G)f Fj(there)h(is)f(an)h(induced)2200 2864 y(path)g(with)g(at)g(least)f(four)h(v)n(ertices)e(b)r(et)n(w)n (een)i Fl(x)g Fj(and)g Fl(y)s Fj(.)34 b(Cho)r(ose)2200 2964 y(suc)n(h)43 b(a)g(path)h Fl(P)55 b Fj(as)43 b(follo)n(ws:)67 b(in)p 3373 2897 V 44 w Fl(G)44 b Fj(delete)g(the)f(common)2200 3064 y(neigh)n(b)r(ors)29 b(of)h Fl(x)h Fj(and)f Fl(y)j Fj(and)d(\014nd)h(a)e(shortest)h(path)g(b)r(et)n(w)n(een)2200 3163 y Fl(x)e Fj(and)g Fl(y)i Fj(in)e(the)g(resulting)f(graph.)2350 3263 y(In)p 2458 3196 V 32 w Fl(G)p Fj(,)34 b(as)e(ev)n(ery)f(v)n (ertex)h(in)h Fl(R)g Fj(sees)f(b)r(oth)h Fl(x)g Fj(and)f Fl(y)s Fj(,)i(the)2200 3362 y(induced)f(path)f Fl(P)44 b Fj(cannot)32 b(in)n(v)n(olv)n(e)f(v)n(ertices)g(from)h Fl(R)q Fj(.)51 b(More)2200 3462 y(o)n(v)n(er,)46 b(since)e Fi(f)p Fl(x;)14 b(y)s Fi(g)43 b Fj(is)h(a)g(co-pair)e(of)i Fl(G)p Fj(,)49 b Fl(P)56 b Fm(must)43 b Fj(in)n(v)n(olv)n(e)2200 3562 y(v)n(ertices)27 b(from)g Fl(I)7 b Fj(.)2350 3661 y(No)n(w,)59 b Fl(P)65 b Fj(cannot)53 b(ha)n(v)n(e)f(a)h(segmen)n(t)g Fl(uv)s(w)j Fj(on)d(three)2200 3761 y(v)n(ertices)42 b(suc)n(h)g(that)i Fl(u)e Fj(and)h Fl(w)i Fj(are)d(in)i Fl(H)49 b Fj(but)44 b Fl(v)i Fj(is)d(in)g Fl(I)7 b Fj(.)2200 3861 y(Otherwise,)54 b(in)c Fl(G)p Fj(,)56 b(v)n(ertex)48 b Fl(v)53 b Fj(of)d Fl(I)56 b Fj(will)50 b(miss)g(b)r(oth)g(the)2200 3960 y(endp)r(oin)n(ts)40 b(of)h(the)f(edge)g([)p Fl(u)p Fj(,)j Fl(w)r Fj(])e(of)f Fl(H)7 b Fj(,)44 b(con)n(tradicting)39 b(the)2200 4060 y(assumption)h(that)h Fl(H)47 b Fj(is)41 b(a)f(handle.)75 b(Therefore,)43 b(in)p 4004 3993 V 41 w Fl(G)p Fj(,)h Fl(P)2200 4159 y Fj(m)n(ust)28 b(ha)n(v)n(e)e(at)i (least)f(an)g(edge)g(in)h Fl(I)7 b Fj(.)2350 4259 y(In)p 2449 4192 V 23 w Fl(G)p Fj(,)25 b(compute)e(a)g(segmen)n(t)g Fl(P)3341 4229 y Fc(0)3388 4259 y Fj(=)g Fl(x)3523 4271 y Fe(2)3560 4259 y Fl(x)3607 4271 y Fe(3)3645 4259 y Fl(x)3692 4271 y Fe(4)3744 4259 y Fl(:)14 b(:)g(:)f(x)3901 4271 y Fk(r)3939 4259 y Fj(,)24 b Fl(r)i Fi(\025)c Fj(4,)2200 4359 y(of)k Fl(P)37 b Fj(suc)n(h)25 b(that)h Fl(x)2793 4371 y Fe(2)2857 4359 y Fj(and)f Fl(x)3063 4371 y Fk(r)3126 4359 y Fj(are)g(in)h Fl(H)32 b Fj(but)26 b Fl(x)3656 4371 y Fe(3)3720 4359 y Fj(through)f Fl(x)4079 4371 y Fk(r)r Fc(\000)p Fe(1)2200 4458 y Fj(are)i(in)h Fl(I)7 b Fj(;)27 b(observ)n(e)f(that)i Fl(x)3052 4470 y Fe(3)3117 4458 y Fj(misses)f Fl(x)3419 4470 y Fe(4)3485 4458 y Fj(in)h Fl(G)p Fj(.)2350 4558 y(Supp)r(ose)37 b(in)g Fl(G)p Fj(,)j Fl(x)2966 4570 y Fe(3)3041 4558 y Fj(and)d Fl(x)3259 4570 y Fe(4)3334 4558 y Fj(do)g(not)h(ha)n(v)n(e)e(a)g (common)2200 4658 y(neigh)n(b)r(or)44 b(in)h Fl(J)8 b Fj(.)89 b(Compute)45 b Fl(P)3281 4627 y Fc(\003)3319 4658 y Fj(,)50 b(a)44 b(shortest)g(path)h(in)h Fl(G)2200 4757 y Fj(b)r(et)n(w)n(een)33 b Fl(x)2573 4769 y Fe(3)2644 4757 y Fj(and)f Fl(x)2857 4769 y Fe(4)2928 4757 y Fj(suc)n(h)h(that)g (all)f(v)n(ertices)g(of)h Fl(P)3897 4727 y Fc(\003)3968 4757 y Fj(except)2200 4857 y Fl(x)2247 4869 y Fe(3)2318 4857 y Fj(and)g Fl(x)2532 4869 y Fe(4)2603 4857 y Fj(b)r(elong)g(to)h Fl(J)8 b Fj(;)36 b(observ)n(e)c(that)h Fl(P)3647 4827 y Fc(\003)3719 4857 y Fj(m)n(ust)g(ha)n(v)n(e)f(at)2200 4956 y(least)25 b(3)g(edges.)35 b(Then,)26 b(compute)g Fl(P)3350 4926 y Fc(\003\003)3422 4956 y Fj(,)f(a)g(shortest)g(path)g (in)h Fl(G)2200 5056 y Fj(b)r(et)n(w)n(een)k Fl(x)2570 5068 y Fe(3)2637 5056 y Fj(and)f Fl(x)2847 5068 y Fe(4)2914 5056 y Fj(suc)n(h)h(that)f(all)h(v)n(ertices)e(of)h Fl(P)3866 5026 y Fc(\003\003)3968 5056 y Fj(except)2200 5156 y Fl(x)2247 5168 y Fe(3)2310 5156 y Fj(and)c Fl(x)2516 5168 y Fe(4)2580 5156 y Fj(b)r(elong)f(to)i Fl(H)7 b Fj(.)36 b(Glue)25 b Fl(P)3338 5126 y Fc(\003)3402 5156 y Fj(with)h Fl(P)3654 5126 y Fc(\003\003)3751 5156 y Fj(to)f(get)g(a)g(hole)2200 5255 y(in)j Fl(G)p Fj(.)2350 5355 y(On)34 b(the)h(other)f(hand,)j(supp)r(ose)d Fl(x)3475 5367 y Fe(3)3548 5355 y Fj(and)g Fl(x)3763 5367 y Fe(4)3836 5355 y Fj(see)g(v)n(ertex)2200 5455 y Fl(x)2247 5467 y Fe(1)2322 5455 y Fj(of)j Fl(J)45 b Fj(in)37 b Fl(G)p Fj(.)65 b(Then,)40 b(in)p 3134 5388 V 37 w Fl(G)p Fj(,)g Fl(x)3309 5467 y Fe(1)3384 5455 y Fj(sees)c Fl(x)3607 5467 y Fe(2)3645 5455 y Fj(,)j Fl(x)3754 5467 y Fe(1)3829 5455 y Fj(misses)d Fl(x)4140 5467 y Fe(3)4178 5455 y Fj(,)2200 5554 y(and)j Fl(x)2420 5566 y Fe(1)2497 5554 y Fj(misses)g Fl(x)2811 5566 y Fe(4)2849 5554 y Fj(,)j(making)c Fl(x)3265 5566 y Fe(1)3303 5554 y Fl(x)3350 5566 y Fe(2)3388 5554 y Fl(x)3435 5566 y Fe(3)3472 5554 y Fl(x)3519 5566 y Fe(4)3596 5554 y Fj(a)h Fl(P)3730 5566 y Fe(4)3768 5554 y Fj(.)72 b(In)p 3978 5487 V 39 w Fl(G)p Fj(,)43 b(let)2200 5654 y Fl(x)2247 5666 y Fk(s)2320 5654 y Fj(b)r(e)38 b(the)f(\014rst)g(v)n(ertex)g(that)g(comes)g(after)f Fl(x)3734 5666 y Fe(4)3809 5654 y Fj(in)i Fl(P)3981 5624 y Fc(0)4041 5654 y Fj(suc)n(h)2200 5753 y(that)44 b Fl(x)2443 5765 y Fe(1)2524 5753 y Fj(sees)f Fl(x)2754 5765 y Fk(s)2790 5753 y Fj(;)51 b(there)43 b(m)n(ust)h(b)r(e)g(suc)n(h)f(a)g(v)n(ertex)f (as)h Fl(x)4163 5765 y Fe(1)p eop %%Page: 47 6 47 5 bop -116 299 a Fd(Pro)r(ceedings)26 b(of)h(11th)g(A)n(CM-SIAM)h (SOD)n(A)g(\(2000\))e(42-49)2075 b Fj(47)-116 523 y(sees)28 b Fl(x)99 535 y Fk(r)165 523 y Fj(in)p 263 456 66 4 v 29 w Fl(G)p Fj(.)40 b(Then,)30 b(the)f(set)g(of)f(v)n(ertices)g Fi(f)p Fl(x)1394 535 y Fe(1)1431 523 y Fl(;)14 b(x)1515 535 y Fe(2)1553 523 y Fl(;)g(:)g(:)g(:)f(;)h(x)1784 535 y Fk(s)1820 523 y Fi(g)p Fj(,)-116 623 y(induce)34 b(a)g(hole)f(of)h (size)g(at)g(least)g(\014v)n(e)f(in)p 1246 556 V 35 w Fl(G)p Fj(.)56 b(Ev)n(ery)33 b(step)h(of)-116 722 y(the)f(ab)r(o)n(v)n (e)e(algorithm)g(tak)n(es)h(O\()p Fl(n)1020 692 y Fe(2)1057 722 y Fj(\))h(time)g(and)f(there)h(are)e(a)-116 822 y(constan)n(t)g(n)n (um)n(b)r(er)g(of)h(steps)g(in)g(the)g(algorithm)f(making)g(the)-116 922 y(time)d(complexit)n(y)f(O\()p Fl(n)642 891 y Fe(2)679 922 y Fj(\).)p 1826 924 59 4 v 1826 865 V 1825 922 4 59 v 1883 922 V 33 1063 a(The)40 b(correctness)e(of)i(algorithm)f Fm(\014nd-hole-or-antihole)-116 1162 y Fj(follo)n(ws)28 b(from)i(our)f(discussions)g(and)g(the)h(pro)r(of)f(of)h(the)g(theo-) -116 1262 y(rem)d(ab)r(o)n(v)n(e.)-116 1403 y Fh(Theorem)32 b(4.2.)40 b Fm(A)n(lgorithm)29 b(\014nd-hole-or-antihole)h(runs)d(in) -116 1503 y(O\()p Fl(n)32 1473 y Fe(4)68 1503 y Fm(\))j(time.)-116 1644 y(Pr)l(o)l(of.)43 b Fj(As)38 b Fm(wt-r)l(e)l(c)l(o)l(gnition)f Fj(runs)h(in)g(O\()p Fl(n)1266 1614 y Fe(4)1303 1644 y Fj(\))g(time,)j(w)n(e)c(only)-116 1743 y(need)20 b(to)h(pro)n(v)n(e)e (that)i Fm(\014nd-pr)l(o)l(of)p Fj(\()p Fl(G)p Fj(\))h(tak)n(es)e(O\()p Fl(n)1403 1713 y Fe(4)1440 1743 y Fj(\))h(time.)35 b(Note)-116 1843 y(that)45 b(in)g(eac)n(h)f(step)h(of)g Fm(\014nd-pr)l(o)l(of)p Fj(,)50 b(the)45 b(algorithm)f(either)-116 1943 y(decides)33 b(to)f(iterate)h(on)g(a)f(prop)r(er)g(induced)i(subgraph)d Fl(G)p Fj([)p Fl(H)7 b Fj(])-116 2042 y(of)47 b Fl(G)p Fj(,)52 b(or)46 b(terminates)h(after)g(sp)r(ending)g(O\()p Fl(n)1421 2012 y Fe(2)1458 2042 y Fj(\))g(time)h(\(see)-116 2142 y(Theorem)c(4.1\).)87 b(No)n(w,)49 b(the)c(decision)f(to)h(w)n (ork)e(on)h Fl(G)p Fj([)p Fl(H)7 b Fj(])-116 2242 y(in)n(v)n(olv)n(es) 31 b(computing)j(a)f(handle)g(follo)n(w)n(ed)g(b)n(y)g(lo)r(oking)f (for)h(a)-116 2341 y(t)n(w)n(o-pair)38 b(in)i(the)h(complemen)n(t)f(of) g(the)g(graph)f(induced)i(b)n(y)-116 2441 y(the)d(handle;)43 b(eac)n(h)37 b(of)h(these)g(can)f(b)r(e)h(done)g(in)g(O\()p Fl(n)1616 2411 y Fe(3)1653 2441 y Fj(\))g(time)-116 2540 y([1)o(,)26 b(3)o(].)37 b(Therefore,)24 b(algorithm)h Fm(\014nd-pr)l(o)l(of)h Fj(p)r(erforms)f(at)g(most)-116 2640 y Fl(n)j Fj(iterations)g(eac)n(h)f(of)i(whic)n(h)f(tak)n(es)g(O\() p Fl(n)1215 2610 y Fe(3)1252 2640 y Fj(\))h(time)g(making)f(its)-116 2740 y(time)g(complexit)n(y)f(O\()p Fl(n)642 2710 y Fe(4)679 2740 y Fj(\).)p 1826 2742 59 4 v 1826 2683 V 1825 2740 4 59 v 1883 2740 V -116 2939 a Fr(5)95 b(Optimization)30 b(Problems)-116 3064 y Fj(In)50 b(this)h(section,)k(w)n(e)50 b(sho)n(w)f(that)h(it)h(is)f(p)r(ossible)g(to)g(use)-116 3163 y(algorithm)33 b Fm(\014nd-p)l(air)j Fj(to)e(impro)n(v)n(e)f(the)i (time)h(complexit)n(y)e(of)-116 3263 y(un)n(w)n(eigh)n(ted)41 b(optimization)g(problems)g(on)g(w)n(eakly)f(c)n(hordal)-116 3362 y(graphs.)33 3462 y(The)31 b(algorithm)f(for)h(solving)f(un)n(w)n (eigh)n(ted)g(indep)r(enden)n(t)-116 3562 y(set,)59 b(coloring,)e (clique,)i(and)52 b(clique)g(co)n(v)n(er)f(problems)h(on)-116 3661 y(w)n(eakly)37 b(c)n(hordal)g(graphs)h(w)n(as)f(\014rst)i(disco)n (v)n(ered)e(in)h([5])h(and)-116 3761 y(is)k(based)h(on)f(the)h(follo)n (wing)f(op)r(eration:)68 b(rep)r(eatedly)43 b(\014nd)-116 3861 y(a)h(t)n(w)n(o-pair)f(x,y)-7 b(,)50 b(and)45 b(`iden)n(tify')g Fl(x)h Fj(and)f Fl(y)i Fj(b)n(y)e(collapsing)-116 3960 y(them)34 b(to)g(a)f(single)g(v)n(ertex)g Fl(z)k Fj(with)e Fl(N)9 b Fj(\()p Fl(z)t Fj(\))33 b(=)h Fl(N)9 b Fj(\()p Fl(x)p Fj(\))34 b Fi([)h Fl(N)9 b Fj(\()p Fl(y)s Fj(\).)-116 4060 y(This)41 b(w)n(orks)e(for)i(the)g(clique)g(and)g(coloring)e (problems;)47 b(for)-116 4159 y(indep)r(enden)n(t)32 b(set)g(and)g(clique)f(co)n(v)n(er,)g(the)i(algorithm)d(is)i(run)-116 4259 y(on)23 b(the)h(complemen)n(t)g(graph,)g(whic)n(h)f(is)h(also)f(w) n(eakly)f(c)n(hordal.)-116 4359 y(The)32 b(running)g(time)g(is)g (dominated)g(b)n(y)g(at)g(most)g Fl(n)g Fj(t)n(w)n(o-pair)-116 4458 y(\014nding)g(iterations;)h(using)e(the)i(algorithm)d(of)i([1])g (this)g(tak)n(es)-116 4558 y(O\()p Fl(n)31 4528 y Fe(2)68 4558 y Fl(m)p Fj(\))j(time.)59 b(W)-7 b(e)35 b(will)g(reduce)f(the)h (time)h(complexit)n(y)e(to)-116 4658 y(O\()p Fl(nm)p Fj(\).)33 4757 y(Since)d(w)n(e)g(\014nd)h(a)e(t)n(w)n(o-pair)g(of)h (the)g(complemen)n(t)g(in)g(our)-116 4857 y(algorithm,)e(the)i (e\013ect)f(of)g(an)g(iden)n(ti\014cation)f(op)r(eration)g(of)h(a)-116 4956 y(t)n(w)n(o-pair)20 b Fl(x)p Fj(,)25 b Fl(y)g Fj(in)p 459 4890 66 4 v 23 w Fl(G)e Fj(is)f(to)h(remo)n(v)n(e)d(the)j(v)n (ertices)f Fl(x)h Fj(and)f Fl(y)s Fj(,)i(and)-116 5056 y(add)j(a)g(new)h(v)n(ertex)f Fl(z)k Fj(suc)n(h)c(that)h Fl(N)9 b Fj(\()p Fl(z)t Fj(\))27 b(=)g Fl(N)9 b Fj(\()p Fl(x)p Fj(\))29 b Fi(\\)f Fl(N)9 b Fj(\()p Fl(y)s Fj(\).)33 5156 y(Algorithm)31 b Fm(wc-opt)g Fj(can)g(b)r(e)g(de\014ned)h(as)e (follo)n(ws.)46 b(If)31 b Fl(x)p Fj(,)p Fl(y)-116 5255 y Fj(is)37 b(not)h(the)g(last)f(edge)h(of)f(the)h(curren)n(t)f(handle,) j(w)n(e)e(simply)-116 5355 y(restart)25 b(our)h(handle)h(\014nding)g (pro)r(cedure)e(with)j Fl(z)i Fj(replacing)25 b Fl(x)-116 5455 y Fj(and)f Fl(y)j Fj(in)e(the)g(curren)n(t)f Fl(X)31 b Fj(set;)25 b(if)g Fl(x)p Fj(,)p Fl(y)j Fj(is)d(the)g(only)f(edge)g (of)g(the)-116 5554 y(handle,)k(let)h Fl(z)j Fj(replace)27 b Fl(x)i Fj(and)f Fl(y)s Fj(,)h(p)r(op)f(the)h(stac)n(k)f(to)g(add)g (the)-116 5654 y(last)c(set)h(of)f(v)n(ertices)g(deleted)h(from)f Fl(X)31 b Fj(to)25 b(our)f(curren)n(t)g Fl(X)31 b Fj(set,)-116 5753 y(and)c(restart)g(the)h(handle-\014nding)f(pro)r(cedure.)2117 523 y(W)-7 b(e)19 b(will)g(sho)n(w)f(that)h Fm(wc-opt)g Fj(can)g(b)r(e)g(implemen)n(ted)g(to)g(run)1968 623 y(in)j(O\()p Fl(nm)p Fj(\))h(time.)35 b(This)23 b(optimization)f(algorithm)f (implemen-)1968 722 y(tation)37 b(is)g(more)f(complex)h(than)g(our)g (previously)f(discussed)1968 822 y Fl(O)r Fj(\()p Fl(m)2138 792 y Fe(2)2176 822 y Fj(\))28 b(time)g(recognition)e(algorithm)g (implemen)n(tation.)2117 922 y(The)42 b(correctness)f(of)h Fm(wc-opt)h Fj(relies)f(on)g(the)h(follo)n(wing)1968 1021 y(in)n(v)-5 b(arian)n(t:)49 b(for)34 b(an)n(y)f(set)h Fl(X)41 b Fj(created)34 b(b)n(y)g(algorithm)f Fm(wc-opt)p Fj(,)1968 1121 y(there)44 b(is)g(a)h(set)f Fl(Y)63 b Fj(of)45 b Fl(V)63 b Fj(-)45 b Fl(X)51 b Fj(-)44 b Fl(N)9 b Fj(\()p Fl(X)e Fj(\))44 b(suc)n(h)h(that)f Fl(G)p Fj([)p Fl(Y)19 b Fj(])1968 1220 y(is)34 b(connected)g(and)g(ev)n(ery)e(v)n (ertex)i(of)g Fl(N)9 b Fj(\()p Fl(X)e Fj(\))33 b(in)i(the)f(curren)n(t) 1968 1320 y(handle)27 b(is)h(adjacen)n(t)f(to)g(a)g(mem)n(b)r(er)h(of)f Fl(Y)19 b Fj(.)2117 1420 y(Note)40 b(that)g(this)h(in)n(v)-5 b(arian)n(t)39 b(is)h(not)g(a\013ected)g(b)n(y)g(either)1968 1519 y(the)21 b(iden)n(ti\014cation)g(of)h(co-pairs)d(in)j Fl(X)7 b Fj(,)22 b(whic)n(h)f(can)g(p)r(oten)n(tially)1968 1619 y(remo)n(v)n(e)26 b(v)n(ertices)i(from)g(the)h(separator)d(set)i (and)g(in)n(to)h(the)g(set)1968 1719 y Fl(Y)18 b Fj(,)25 b(or)f(b)n(y)g(adding)f(v)n(ertices)h(bac)n(k)f(to)h(the)h(set)f Fl(X)7 b Fj(;)25 b(in)f(the)h(latter)1968 1818 y(case,)h(w)n(e)i (simply)f(rev)n(ert)g(to)g(an)g(earlier)g(set)g Fl(Y)46 b Fj(of)28 b(v)n(ertices.)2117 1918 y(The)60 b(pro)r(ofs)e(b)r(elo)n(w) h(are)g(essen)n(tially)f(equiv)-5 b(alen)n(t)60 b(to)1968 2017 y(Lemma)36 b(2.1.)64 b(F)-7 b(or)37 b(con)n(v)n(enience,)h(w)n(e)e (will)h(call)g(a)f(set)h(a)g Fm(r)l(e-)1968 2117 y(cursive)f(hand)t(le) f Fj(if)f(this)g(set)g(w)n(as)f(found)h(to)f(b)r(e)i(a)e(handle)h(at) 1968 2217 y(some)27 b(p)r(oin)n(t)g(during)h(the)g(running)f(of)g(the)h (algorithm.)2117 2316 y(Let)f Fl(G)2330 2286 y Fc(0)2381 2316 y Fj(b)r(e)h(obtained)f(from)g Fl(G)g Fj(via)g(the)h(iden)n (ti\014cation)f(of)1968 2416 y(a)g(co-pair)f Fi(f)p Fl(x;)14 b(y)s Fi(g)p Fj(.)1968 2578 y Fh(Lemma)31 b(5.1.)40 b Fm(L)l(et)34 b Fl(H)2680 2590 y Fe(0)2751 2578 y Fm(b)l(e)h(a)f(r)l(e)l (cursive)h(hand)t(le)h(of)f(a)f(we)l(akly)1968 2677 y(chor)l(dal)h(gr)l (aph)f Fl(G)p Fm(.)49 b(If)34 b Fi(f)p Fl(u;)14 b(v)s Fi(g)32 b Fm(is)h(a)h(c)l(o-p)l(air)g(of)g Fl(G)3578 2647 y Fc(0)3602 2677 y Fj([)p Fl(H)3694 2689 y Fe(0)3731 2677 y Fj(])p Fm(,)h(then)1968 2777 y Fi(f)p Fl(u;)14 b(v)s Fi(g)28 b Fm(is)i(a)g(c)l(o-p)l(air)h(of)g Fl(G)2809 2747 y Fc(0)2832 2777 y Fm(.)1968 2939 y(Pr)l(o)l(of.)43 b Fj(Assume)30 b(that)h Fl(G)p Fj([)p Fl(H)2878 2951 y Fk(i)2906 2939 y Fj(])g(is)g(a)f(handle)g(of)h Fl(G)p Fj([)p Fl(H)3644 2951 y Fk(i)p Fe(+1)3756 2939 y Fj(])g(for)f Fl(i)1968 3039 y Fj(=)j(0,...,)p Fl(k)s Fj(.)55 b(Consider)32 b(an)h(induced)h(path)g Fl(P)46 b Fj(from)33 b Fl(u)g Fj(to)h Fl(v)j Fj(of)1968 3138 y(length)21 b(greater)g(than)g(t)n(w)n (o)g(in)p 2922 3072 89 4 v 23 w Fl(G)2987 3114 y Fc(0)3010 3138 y Fj(.)35 b(This)22 b(path)g(m)n(ust)g(lea)n(v)n(e)e Fl(H)3908 3150 y Fe(0)3945 3138 y Fj(,)1968 3238 y(since)27 b Fi(f)p Fl(u;)14 b(v)s Fi(g)26 b Fj(is)i(a)f(co-pair)f(of)i Fl(G)2999 3208 y Fc(0)3022 3238 y Fj([)p Fl(H)3114 3250 y Fe(0)3151 3238 y Fj(].)2117 3337 y(Let)d Fl(i)g Fj(b)r(e)g(the)g (largest)e(index)i(suc)n(h)g(that)g Fl(P)37 b Fj(uses)24 b(a)h(v)n(ertex)1968 3437 y(whic)n(h)e(is)h(in)g Fl(H)2443 3449 y Fk(i)2471 3437 y Fj(,)h(but)f(not)g Fl(H)2880 3449 y Fk(i)p Fc(\000)p Fe(1)2993 3437 y Fj(.)35 b(Let)25 b Fl(h)3245 3449 y Fk(i)3268 3457 y Fb(1)3328 3437 y Fj(b)r(e)g(the)f(\014rst)g(v)n(ertex)1968 3537 y(from)18 b Fl(H)2224 3549 y Fk(i)2270 3537 y Fj(-)h Fl(H)2386 3549 y Fk(i)p Fc(\000)p Fe(1)2517 3537 y Fj(on)g Fl(P)12 b Fj(.)33 b(Note)19 b(that)g Fl(h)3156 3549 y Fk(i)3179 3557 y Fb(1)3235 3537 y Fj(m)n(ust)f(b)r(e)h(in)g Fl(N)9 b Fj(\()p Fl(H)3800 3549 y Fk(i)p Fc(\000)p Fe(1)3913 3537 y Fj(\),)1968 3636 y(since)24 b Fl(h)2216 3648 y Fk(i)2239 3656 y Fb(1)2301 3636 y Fj(is)h(adjacen)n(t)g(to)f(at)h (least)g(one)f(of)h Fl(u;)14 b(v)s Fj(.)36 b(Let)25 b Fl(g)j Fj(b)r(e)d(the)1968 3736 y(v)n(ertex)18 b(whic)n(h)i(precedes)f Fl(h)2814 3748 y Fk(i)2837 3756 y Fb(1)2894 3736 y Fj(on)g Fl(P)12 b Fj(,)22 b(and)d(let)h Fl(h)3424 3748 y Fk(i)3447 3756 y Fb(2)3504 3736 y Fj(b)r(e)g(the)h(v)n(ertex)1968 3836 y(whic)n(h)j(succeeds)f Fl(h)2579 3848 y Fk(i)2602 3856 y Fb(1)2663 3836 y Fj(on)h Fl(P)12 b Fj(.)36 b(Since)24 b Fl(h)3160 3848 y Fk(i)3183 3856 y Fb(1)3244 3836 y Fj(cannot)g(miss)g(an)g(edge)1968 3935 y(in)j Fl(H)2133 3947 y Fk(i)p Fc(\000)p Fe(1)2246 3935 y Fj(,)h Fl(h)2345 3947 y Fk(i)2368 3955 y Fb(2)2432 3935 y Fj(m)n(ust)g(b)r(e)g(in)g Fl(H)2917 3947 y Fk(i)2972 3935 y Fj(-)g Fl(H)3097 3947 y Fk(i)p Fc(\000)p Fe(1)3209 3935 y Fj(.)2117 4035 y(V)-7 b(ertices)26 b Fl(h)2478 4047 y Fk(i)2501 4055 y Fb(1)2565 4035 y Fj(and)g Fl(h)2773 4047 y Fk(i)2796 4055 y Fb(2)2860 4035 y Fj(m)n(ust)h(ha)n(v)n(e)e(a)h(common)h(neigh)n(b)r(or)1968 4134 y Fl(s)g Fj(in)g Fl(V)46 b Fj(-)27 b Fl(N)9 b Fj(\()p Fl(H)2456 4146 y Fk(i)p Fc(\000)p Fk(i)2559 4134 y Fj(\);)27 b(this)h(follo)n(ws)e(from)h(the)g(in)n(v)-5 b(arian)n(t)26 b(ab)r(o)n(v)n(e)1968 4234 y(and)i(the)g(fact)h(that)f Fl(G)h Fj(has)f(no)g(holes.)38 b(Th)n(us,)29 b(there)f(is)g(a)g(hole) 1968 4334 y(in)p 2071 4267 V 34 w Fl(G)2136 4310 y Fc(0)2159 4334 y Fj(,)36 b(of)d(the)h(form)g Fl(s;)14 b(g)s(;)g(h)2874 4346 y Fk(i)2897 4354 y Fb(1)2933 4334 y Fl(;)g(h)3018 4346 y Fk(i)3041 4354 y Fb(2)3078 4334 y Fj(,..,)p Fl(j)5 b Fj(,)35 b(where)e Fl(j)39 b Fj(is)34 b(the)g(\014rst)1968 4433 y(v)n(ertex)26 b(after)h Fl(h)2463 4445 y Fk(i)2486 4453 y Fb(2)2551 4433 y Fj(on)g Fl(P)40 b Fj(whic)n(h)27 b(is)h(nonadjacen)n(t)f(to)g Fl(s)p Fj(.)2117 4533 y(Th)n(us,)d Fl(G)2412 4503 y Fc(0)2460 4533 y Fj(is)g(not)g(w)n(eakly)e(c)n (hordal,)h(con)n(tradiction,)h(since)1968 4633 y Fl(G)2033 4602 y Fc(0)2084 4633 y Fj(w)n(as)i(obtained)i(from)f Fl(G)h Fj(b)n(y)f(iden)n(tifying)h(a)f(co-pair.)p 3910 4635 59 4 v 3910 4576 V 3909 4633 4 59 v 3967 4633 V 1968 4795 a Fh(Theorem)32 b(5.1.)40 b Fm(A)n(lgorithm)30 b(wc-opt)h(is)f(c)l(orr)l(e)l(ct.)1968 4956 y(Pr)l(o)l(of.)43 b Fj(Let)38 b Fl(G)g Fj(b)r(e)g(a)g(w)n(eakly)f(c)n(hordal)f(graph,)k (and)d(let)i Fl(u)p Fj(,)p Fl(v)1968 5056 y Fj(b)r(e)33 b(the)g(\014rst)f(pair)g(of)h(v)n(ertices)e(found)i(b)n(y)f(algorithm)g Fm(wc-opt)1968 5156 y Fj(whic)n(h)27 b(are)g(not)g(a)h(co-pair)e(of)h (the)h(curren)n(t)f(graph)f Fl(G)3664 5126 y Fc(0)3688 5156 y Fj(.)2117 5255 y(By)32 b(the)g(preceding)g(lemma,)h(w)n(e)f (only)f(need)i(to)e(concern)1968 5355 y(ourself)c(with)h(re\014nemen)n (t)g(pro)r(cedures)f(in)h(a)g(single)f(recursiv)n(e)1968 5455 y(handle.)47 b(Ho)n(w)n(ev)n(er,)29 b(within)j(a)f(single)f (recursiv)n(e)f(handle,)j(the)1968 5554 y(pro)r(of)22 b(of)i(lemma)f(1)g(can)f(b)r(e)i(rep)r(eated)f(essen)n(tially)f(unc)n (hanged)1968 5654 y(using)39 b(the)h(in)n(v)-5 b(arian)n(t)39 b(giv)n(en)g(ab)r(o)n(v)n(e,)j(so)d(ev)n(ery)f(v)n(ertex)h(pair)1968 5753 y(found)28 b(m)n(ust)f(b)r(e)h(a)f(co-pair)f(of)i Fl(G)3025 5723 y Fc(0)3049 5753 y Fj(.)p 3910 5755 59 4 v 3910 5697 V 3909 5753 4 59 v 3967 5753 V eop %%Page: 48 7 48 6 bop 116 299 a Fj(48)2953 b Fd(Ha)n(yw)n(ard,)26 b(Spinrad,)h(Sritharan)266 523 y Fj(W)-7 b(e)45 b(no)n(w)f(sho)n(w)g (that)h(the)g(algorithm)f(can)g(b)r(e)h(imple-)116 623 y(men)n(ted)30 b(to)g(run)g(in)g(O\()p Fl(nm)p Fj(\))g(time.)44 b(In)30 b(previous)e(argumen)n(ts,)116 722 y(our)f(time)i(b)r(ound)f(w) n(as)f(deriv)n(ed)g(from)g(the)h(fact)g(that)g(a)g(single)116 822 y(re\014nemen)n(t)c(of)f(the)h(set)g Fl(X)30 b Fj(to)r(ok)23 b(O\()p Fl(m)p Fj(\))g(time.)36 b(There)23 b(are)g(sev-)116 922 y(eral)c(steps)g(whic)n(h)h(tak)n(e)f(O\()p Fl(m)p Fj(\))h(time;)j(\014nding)c(v)n(ertices)g Fl(v)k Fj(and)c Fl(e)116 1021 y Fj(to)j(start)f(the)h(re\014nemen)n(t)g(pro)r(cedure,)g (\014nding)g(the)g(connected)116 1121 y(comp)r(onen)n(t)h Fl(C)29 b Fj(of)23 b Fl(v)j Fj(in)e Fl(V)k Fi(\000)9 b Fl(N)g Fj(\()p Fl(e)p Fj(\),)23 b(marking)f(neigh)n(b)r(ors)g(of)h Fl(C)6 b Fj(,)116 1220 y(and)28 b(\014nding)f(the)h(connected)g(comp)r (onen)n(t)f(of)g Fl(e)h Fj(in)f(the)h(graph)116 1320 y(induced)j(b)n(y)e Fl(X)e Fi(\000)19 b Fl(N)9 b Fj(\()p Fl(C)d Fj(\).)45 b(W)-7 b(e)30 b(will)g(sho)n(w)f(that)h(if)h(w)n(e)e (ignore)116 1420 y(a)j(total)f(cost)g(of)h(O\()p Fl(nm)p Fj(\),)h(a)e(single)h(re\014nemen)n(t)f(step)h(can)g(b)r(e)116 1519 y(made)38 b(to)g(run)g(in)g(O\()p Fl(m)900 1531 y Fk(X)963 1519 y Fj(\))g(time,)j(where)d Fl(m)1582 1531 y Fk(X)1683 1519 y Fj(is)g(the)g(n)n(um-)116 1619 y(b)r(er)f(of)f (edges)g(in)h(the)g(subgraph)e(induced)i(b)n(y)f Fl(X)7 b Fj(.)63 b(W)-7 b(e)37 b(will)116 1719 y(then)g(use)g(the)g(new)g(b)r (ound)g(on)f(an)g(individual)h(step)g(to)f(get)116 1818 y(an)28 b(O\()p Fl(nm)p Fj(\))h(upp)r(er)f(b)r(ound)h(on)f(the)g(en)n (tire)g(w)n(ork)f(done)h(in)h(the)116 1918 y(optimization)f(algorithm.) 266 2017 y(W)-7 b(e)32 b(will)g(main)n(tain)f(some)g(extra)g (information)f(to)i(sp)r(eed)116 2117 y(up)20 b(these)f(steps.)34 b(Keep)18 b(the)i(curren)n(t)e(set)h Fl(N)9 b Fj(\()p Fl(X)e Fj(\))19 b(as)g(an)f(ordered)116 2217 y(list,)36 b(with)f(v)n(ertices)e(added)h(to)g Fl(N)9 b Fj(\()p Fl(X)e Fj(\))34 b(b)r(eing)h(placed)f(at)g(the)116 2316 y(end)i(of)f(this)h(list,)h(and)f(main)n(tain)f(with)g(eac)n(h)g(mem)n (b)r(er)g Fl(u)g Fj(of)116 2416 y Fl(N)9 b Fj(\()p Fl(X)e Fj(\))41 b(the)g(n)n(um)n(b)r(er)g(of)g(neigh)n(b)r(ors)e(of)i Fl(u)g Fj(in)g Fl(X)7 b Fj(.)76 b(W)-7 b(e)41 b(also)116 2516 y(main)n(tain)20 b(for)g(eac)n(h)f(v)n(ertex)g Fl(x)i Fj(in)f Fl(X)27 b Fj(the)20 b(n)n(um)n(b)r(er)g(of)g(neigh)n(b)r(ors) 116 2615 y(of)28 b Fl(x)g Fj(in)g Fl(N)9 b Fj(\()p Fl(X)e Fj(\).)116 2790 y Fh(Theorem)32 b(5.2.)40 b Fm(A)n(lgorithm)j(wc-opt)f (c)l(an)g(b)l(e)g(implemente)l(d)116 2889 y(to)30 b(run)f(in)h(O\(nm\)) f(time.)116 3064 y(Pr)l(o)l(of.)43 b Fj(Our)54 b(\014rst)g(step)h(whic) n(h)g(tak)n(es)e(O\()p Fl(m)p Fj(\))i(time)g(in)g(a)116 3163 y(straigh)n(tforw)n(ard)41 b(implemen)n(tation)k(is)f(\014nding)g (a)g(v)n(ertex)f Fl(v)116 3263 y Fj(from)i Fl(N)9 b Fj(\()p Fl(X)e Fj(\))44 b(and)h(edge)f Fl(e)h Fj(in)g Fl(X)51 b Fj(suc)n(h)45 b(that)g Fl(v)j Fj(misses)c Fl(e)p Fj(.)116 3362 y(Note)d(that)h(once)e Fl(v)45 b Fj(has)40 b(b)r(een)i(found)f(to) g(\(not\))h(miss)f Fl(e)p Fj(,)j Fl(v)116 3462 y Fj(will)29 b(alw)n(a)n(ys)e(\(not\))j(miss)f Fl(e)p Fj(.)40 b(F)-7 b(or)29 b(eac)n(h)f(edge)g Fl(e)h Fj(of)g Fl(X)7 b Fj(,)28 b(w)n(e)h(will)116 3562 y(ha)n(v)n(e)f(already)f(ha)n(v)n(e)h(c)n(hec)n (k)n(ed)g(to)g(see)h(whether)f Fl(e)h Fj(has)f(missed)116 3661 y(neigh)n(b)r(ors)f(of)h Fl(X)34 b Fj(up)29 b(through)e(some)g(v)n (ertex)g Fl(j)5 b Fj(;)29 b(w)n(e)e(start)h(our)116 3761 y(searc)n(h)f(from)h Fl(j)33 b Fj(and)28 b(con)n(tin)n(ue.)39 b(Since)28 b(eac)n(h)f(edge)h(is)g(c)n(hec)n(k)n(ed)116 3861 y(against)38 b(eac)n(h)g(v)n(ertex)f(once,)k(the)e(total)g(w)n (ork)e(in)i(\014nding)g Fl(v)116 3960 y Fj(and)d Fl(e)f Fj(through)g(the)h(whole)f(algorithm)g(is)g(O\()p Fl(nm)p Fj(\).)61 b(In)36 b(the)116 4060 y(full)29 b(v)n(ersion)e(of)h(the)h (pap)r(er,)f(w)n(e)f(address)g(certain)h(lo)n(w)n(er)f(lev)n(el)116 4159 y(details)k(not)f(treated)g(here;)i(these)f(in)n(v)n(olv)n(e)e (deleting)h(v)n(ertices)116 4259 y(from)22 b Fl(N)9 b Fj(\()p Fl(X)e Fj(\))21 b(and)h(assignmen)n(t)f(of)g(costs)g(when)h(v)n (ertices)f Fl(x)h Fj(and)116 4359 y Fl(y)31 b Fj(are)26 b(iden)n(ti\014ed)i(in)g(the)g(algorithm.)266 4458 y(The)g(next)g(task) g(whic)n(h)g(used)g(O\()p Fl(m)p Fj(\))g(time)g(is)g(computing)116 4558 y Fl(Y)183 4528 y Fc(0)206 4558 y Fj(,)k(whic)n(h)f(is)g(the)h (comp)r(onen)n(t)f(of)g Fl(G)21 b Fi(\000)f Fl(N)9 b Fj(\()p Fl(e)p Fj(\))32 b(con)n(taining)e Fl(v)s Fj(.)116 4658 y(First,)f(note)g(that)g(ev)n(ery)f(mem)n(b)r(er)h(of)g Fl(N)9 b Fj(\()p Fl(X)e Fj(\))19 b Fi(\000)g Fl(N)9 b Fj(\()p Fl(e)p Fj(\))29 b(will)g(b)r(e)116 4757 y(added)21 b(to)g Fl(Y)515 4727 y Fc(0)539 4757 y Fj(;)i(these)e(can)f(easily)g(b) r(e)h(found)g(in)g(O\()p Fl(n)p Fj(\))g(time.)35 b(If)22 b(a)116 4857 y(v)n(ertex)j Fl(x)g Fj(of)h Fl(X)31 b Fj(is)26 b(not)f(in)g Fl(N)9 b Fj(\()p Fl(e)p Fj(\))26 b(and)f(is)g(adjacen)n(t) g(to)g(a)g(v)n(ertex)116 4956 y(mo)n(v)n(ed)33 b(from)g Fl(N)9 b Fj(\()p Fl(X)e Fj(\))33 b(to)g Fl(Y)1008 4926 y Fc(0)1031 4956 y Fj(,)i(it)f(is)f(added)h(to)f Fl(Y)1692 4926 y Fc(0)1715 4956 y Fj(;)k(note)c(that)116 5056 y(w)n(e)c(will)g (also)f(add)h(its)g(connected)g(comp)r(onen)n(t)g(in)g Fl(X)d Fi(\000)19 b Fl(N)9 b Fj(\()p Fl(e)p Fj(\))116 5156 y(to)32 b Fl(Y)289 5126 y Fc(0)312 5156 y Fj(,)h(but)g(the)f(w)n (ork)f(\014nding)h(this)g(comp)r(onen)n(t)g(can)f(all)h(b)r(e)116 5255 y(c)n(harged)26 b(to)i Fl(m)598 5267 y Fk(X)661 5255 y Fj(.)266 5355 y(W)-7 b(e)29 b(no)n(w)e(m)n(ust)i(\014nd)g(neigh) n(b)r(ors)e(of)h Fl(Y)1494 5325 y Fc(0)1517 5355 y Fj(.)40 b(When)29 b(a)f(v)n(ertex)116 5455 y Fl(y)h Fj(is)d(mo)n(v)n(ed)f(in)n (to)g Fl(Y)760 5424 y Fc(0)783 5455 y Fj(,)h(w)n(e)g(scan)f(its)h (adjacency)f(list,)i(up)r(dating)116 5554 y(appropriate)19 b(main)n(tained)i(v)-5 b(alues)20 b(\(if)i Fl(y)i Fj(is)c(mo)n(v)n(ed)g (from)h Fl(X)7 b Fj(,)21 b(all)116 5654 y(neigh)n(b)r(ors)34 b(in)h Fl(N)9 b Fj(\()p Fl(X)e Fj(\))34 b(ha)n(v)n(e)g(their)g(n)n(um)n (b)r(er)h(of)f Fl(X)7 b Fj(-neigh)n(b)r(ors)116 5753 y(decreased)29 b(b)n(y)g(1\),)h(and)g(mo)n(ving)e(neigh)n(b)r(ors)h(of) g Fl(y)k Fj(from)c Fl(X)36 b Fj(to)2200 523 y Fl(N)9 b Fj(\()p Fl(X)e Fj(\).)58 b(When)36 b(neigh)n(b)r(ors)d(of)i Fl(y)j Fj(are)33 b(mo)n(v)n(ed)h(to)h Fl(N)9 b Fj(\()p Fl(X)e Fj(\),)36 b(w)n(e)2200 623 y(also)h(up)r(date)i(the)f (appropriate)f(v)-5 b(alues.)68 b(A)39 b(v)n(ertex)e(can)h(b)r(e)2200 722 y(mo)n(v)n(ed)h(in)n(to)h Fl(Y)59 b Fj(at)40 b(most)g Fl(n)p Fj(-1)f(times,)k(since)d(a)g(v)n(ertex)f(will)2200 822 y(nev)n(er)24 b(return)h(to)f Fl(X)32 b Fj(or)24 b Fl(N)9 b Fj(\()p Fl(X)e Fj(\))24 b(un)n(til)i(a)e(collapse)g(op)r (eration)g(is)2200 922 y(p)r(erformed.)36 b(Similarly)25 b(a)h(v)n(ertex)f(can)g(b)r(e)i(mo)n(v)n(ed)e(in)n(to)g Fl(N)9 b Fj(\()p Fl(X)e Fj(\))2200 1021 y(at)31 b(most)f Fl(n)p Fj(-1)g(times,)h(since)g(it)f(will)h(not)g(return)f(to)g Fl(X)37 b Fj(b)r(efore)2200 1121 y(a)27 b(collapse)g(op)r(eration)g(is) g(p)r(erformed.)37 b(Th)n(us,)28 b(the)g(total)f(time)2200 1220 y(sp)r(en)n(t)h(scanning)f(adjacency)g(lists)h(while)g(mo)n(ving)e (v)n(ertices)h(to)2200 1320 y Fl(Y)46 b Fj(and)28 b Fl(N)9 b Fj(\()p Fl(X)e Fj(\))27 b(is)h(O\()p Fl(nm)p Fj(\).)2350 1420 y(The)e(\014nal)g(step)g(for)g(whic)n(h)g(w)n(e)g(allo)n(w)n(ed)f (O\()p Fl(m)p Fj(\))h(time)h(w)n(as)2200 1519 y(\014nding)20 b(connected)f(comp)r(onen)n(ts)f(in)i(the)g(new)f(set)g Fl(X)7 b Fj(,)21 b(but)f(this)2200 1619 y(step)29 b(clearly)e(tak)n(es) h(O\()p Fl(m)3027 1631 y Fk(X)3089 1619 y Fj(\))h(time.)40 b(Th)n(us)28 b(the)h(running)f(time)2200 1719 y(of)h(the)h(algorithm)e (is)h(O\()p Fl(nm)p Fj(\))g(plus)g(the)g(sum)h(of)f(the)g(n)n(um)n(b)r (er)2200 1818 y(of)f(edges)e(in)i(all)g Fl(X)34 b Fj(sets)27 b(created)g(during)g(the)h(algorithm.)2350 1918 y(Eac)n(h)c(edge)h(is)g (part)h(of)f(at)h(most)f Fl(n)g Fj(edge)h(sets,)f(since)h(eac)n(h)2200 2017 y(time)i(it)g(is)f(placed)g(in)g(an)g Fl(X)34 b Fj(set)27 b(the)h(size)f(of)g Fl(X)34 b Fj(decreases)25 b(b)n(y)2200 2117 y(at)c(least)f(1.)35 b(Th)n(us)20 b(the)i(total)e (size)h(of)g(all)g(sets)f(of)h(edges)g(induced)2200 2217 y(b)n(y)29 b Fl(X)35 b Fj(sets)28 b(is)h(O\()p Fl(nm)p Fj(\),)g(and)g(our)f(algorithm)g(runs)g(in)h(O\()p Fl(nm)p Fj(\))2200 2316 y(time.)p 4143 2318 59 4 v 4143 2260 V 4141 2316 4 59 v 4199 2316 V 2350 2499 a(Note)j(that)h(in)f(this)h (case,)g(the)g(optimization)f(algorithm)2200 2599 y(runs)h(faster)g (than)g(the)h(recognition)d(algorithm.)53 b(Th)n(us,)34 b(one)2200 2698 y(can)50 b(imagine)g(a)f(p)r(oten)n(tial)h(for)g(the)h (algorithm)e(to)h(mak)n(e)2200 2798 y(mistak)n(es)28 b(if)i(the)g(input)g(is)f(not)g(w)n(eakly)f(c)n(hordal;)h(there)g(is)g (no)2200 2897 y(time)20 b(to)e(run)h(a)g(recognition)e(algorithm)h(to)h (c)n(hec)n(k)f(whether)h(the)2200 2997 y(input)26 b(is)g(in)g(the)g (class.)35 b(F)-7 b(ortunately)g(,)25 b(the)h(correctness)e(of)i(the) 2200 3097 y(optimization)36 b(algorithm)f(dep)r(ends)i(only)f(on)g(the) g(fact)h(that)2200 3196 y(eac)n(h)26 b(edge)h(induces)g(a)f(co-pair)f (of)i Fl(G)p Fj(,)h(whic)n(h)e(can)h(b)r(e)g(c)n(hec)n(k)n(ed)2200 3296 y(within)44 b(the)g(time)g(b)r(ounds)f(giv)n(en.)83 b(Th)n(us,)47 b(the)d(algorithm)2200 3396 y(w)n(orks)31 b(correctly)g(on)h(all)g(w)n(eakly)g(c)n(hordal)f(graphs,)h(and)h(will) 2200 3495 y(also)20 b(correctly)g(solv)n(e)g(the)i(problems)e(in)h (some)g(cases)f(when)i(the)2200 3595 y(input)28 b(is)g(not)g(w)n(eakly) e(c)n(hordal.)2200 3794 y Fr(6)95 b(Conclusions)30 b(and)j(Op)s(en)e (Problems)2200 3919 y Fj(W)-7 b(e)24 b(ha)n(v)n(e)e(demonstrated)h(the) h(use)f(of)h(the)f(notion)h(of)f(a)g(handle)2200 4018 y(in)34 b(a)g(graph,)h(a)e(sp)r(ecial)h(t)n(yp)r(e)g(of)g(comp)r(onen)n (t/separator,)f(to)2200 4118 y(design)e(e\016cien)n(t)g(algorithms)f (for)h(certain)f(classes)g(of)h(graphs)2200 4218 y(without)42 b(holes.)77 b(W)-7 b(e)41 b(conclude)g(the)h(pap)r(er)e(b)n(y)h(prop)r (osing)2200 4317 y(some)36 b(problems)g(for)g(further)h(w)n(ork.)62 b(Designing)36 b(an)h(O\()p Fl(n)4132 4287 y Fe(2)4169 4317 y Fj(\))2200 4417 y(algorithm)50 b(to)g(\014nd)h(a)f(t)n(w)n (o-pair)f(in)i(an)g(arbitrary)d(graph)2200 4516 y(w)n(ould)19 b(impro)n(v)n(e)e(almost)i(ev)n(ery)e(algorithm)h(kno)n(wn)h(for)f(w)n (eakly)2200 4616 y(c)n(hordal)37 b(graphs.)66 b(W)-7 b(e)39 b(also)e(prop)r(ose)g(designing)g(an)h(O\()p Fl(n)4132 4586 y Fe(2)4169 4616 y Fj(\))2200 4716 y(algorithm)30 b(to)i(\014nd)g(a)f(t)n(w)n(o-pair)f(in)h(a)g(giv)n(en)g(w)n(eakly)f(c) n(hordal)2200 4815 y(graph)j(as)g(a)h(problem;)j(this)d(w)n(ould)g (su\016ce)g(to)g(impro)n(v)n(e)f(the)2200 4915 y(recognition)41 b(and)i(optimization)f(algorithms.)81 b(In)43 b(view)f(of)2200 5015 y(the)33 b(pro)r(of)f(of)h(Theorem)f(2.1,)h(a)g(faster)f (algorithm)g(to)g(\014nd)h(a)2200 5114 y(handle)40 b(in)g(an)f (arbitrary)f(\(w)n(eakly)h(c)n(hordal\))g(graph)f(w)n(ould)2200 5214 y(in)47 b(turn)g(imply)g(a)g(faster)f(algorithm)g(to)g(\014nd)h(a) g(t)n(w)n(o-pair)2200 5313 y(in)c(an)g(arbitrary)e(\(w)n(eakly)h(c)n (hordal\))g(graph.)82 b(Finally)-7 b(,)46 b(w)n(e)2200 5413 y(prop)r(ose)40 b(designing)g(an)h(O\()p Fl(n)3175 5383 y Fe(4)3212 5413 y Fj(\))g(algorithm)f(to)g(\014nd)i(a)e(hole)2200 5513 y(in)28 b(an)f(arbitrary)f(graph)g(as)h(a)g(problem.)p eop %%Page: 49 8 49 7 bop -116 299 a Fd(Pro)r(ceedings)26 b(of)h(11th)g(A)n(CM-SIAM)h (SOD)n(A)g(\(2000\))e(42-49)2075 b Fj(49)-116 523 y Fr(References)-59 780 y Fq([1])43 b(S.)28 b(Arik)l(ati)h(and)g(C.)g(Rangan,)h(An)e (E\016cien)n(t)h(Algorithm)g(for)64 872 y(Finding)43 b(a)h(Tw)n(o-P)n(air,)50 b(and)43 b(its)h(Applications,)49 b Fp(Discr)l(ete)64 963 y(Applie)l(d)27 b(Mathematics)p Fq(,)h Fa(31)e Fq(\(1991\),)h(71-74.)-59 1054 y([2])43 b(R.)25 b(B.)g(Ha)n(yw)n(ard,)g(W)-6 b(eakly)25 b(T)-6 b(riangulated)26 b(Graphs,)g Fp(Journal)64 1146 y(of)e(Combinatorial)i (The)l(ory)g(Series)g(B)p Fq(,)e Fa(39)f Fq(\(1985\),)i(200-209.)-59 1237 y([3])43 b(R.)23 b(B.)h(Ha)n(yw)n(ard,)g(Meyniel)g(W)-6 b(eakly)23 b(T)-6 b(riangulated)24 b(Graphs.)64 1328 y(I.)c(Co-P)n(erfect)i(Orderabilit)n(y)-6 b(,)21 b Fp(Discr)l(ete)j (Applie)l(d)f(Mathemat-)64 1420 y(ics)p Fq(,)j Fa(73)g Fq(\(1997\),)h(199-210.)-59 1511 y([4])43 b(R.)23 b(B.)h(Ha)n(yw)n (ard,)g(Meyniel)g(W)-6 b(eakly)23 b(T)-6 b(riangulated)24 b(Graphs.)64 1602 y(I)r(I.)c(A)h(Theorem)g(of)g(Dirac,)i Fp(Discr)l(ete)i(Applie)l(d)e(Mathematics)p Fq(,)64 1694 y Fa(78)j Fq(\(1997\),)h(283-289.)-59 1785 y([5])43 b(R.B.)27 b(Ha)n(yw)n(ard,)g(C.T.)h(Ho\022)-38 b(ang,)28 b(and)e(F.)i(Ma\013ra)n (y)-6 b(,)27 b(Optimiz-)64 1876 y(ing)e(w)n(eakly)g(triangulated)h (graphs,)f Fp(Gr)l(aphs)k(and)e(Combina-)64 1968 y(torics)p Fq(,)g Fa(5)f Fq(\(1989\),)h(339-349;)h(erratum)d(in)g Fa(6)h Fq(\(1990\),)h(33-35.)-59 2059 y([6])43 b(D.J.)27 b(Rose,)h(R.E.)f(T)-6 b(arjan,)28 b(and)f(G.S.)g(Leuk)n(er,)g (Algorithmic)64 2150 y(Asp)r(ects)22 b(of)h(V)-6 b(ertex)21 b(Elimination)i(on)g(Graphs,)g Fp(SIAM)h(Jour-)64 2242 y(nal)j(on)h(Computing)p Fq(,)e Fa(5)g Fq(\(1976\),)h(266-283.)-59 2333 y([7])43 b(J.)26 b(Spinrad,)f(Finding)g(Large)h(Holes,)h Fp(Information)g(Pr)l(o)l(c)l(ess-)64 2424 y(ing)g(L)l(etters)p Fq(,)h Fa(39)e Fq(\(1991\),)i(227-229.)-59 2516 y([8])43 b(J.)35 b(Spinrad)g(and)g(R.)g(Sritharan,)i(Algorithms)e(for)h(W)-6 b(eakly)64 2607 y(T)g(riangulated)39 b(Graphs,)j Fp(Discr)l(ete)f (Applie)l(d)e(Mathematics)p Fq(,)64 2698 y Fa(59)26 b Fq(\(1995\),)h(181-191.)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF