-
Notifications
You must be signed in to change notification settings - Fork 1
/
dmtcs.ps
5535 lines (5258 loc) · 216 KB
/
dmtcs.ps
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
%!PS-Adobe-2.0
%%Creator: dvipsk 5.86 p1.5d Copyright 1996-2001 ASCII Corp.(www-ptex@ascii.co.jp)
%%based on dvipsk 5.86 Copyright 1999 Radical Eye Software (www.radicaleye.com)
%%Title: permu-dmtcs.dvi
%%Pages: 16
%%PageOrder: Ascend
%%BoundingBox: 0 0 596 842
%%DocumentFonts: Times-Italic Times-Bold Times-Roman Helvetica-Oblique
%%+ Courier-Oblique Helvetica Symbol Times-BoldItalic
%%EndComments
%DVIPSWebPage: (www.radicaleye.com)
%DVIPSCommandLine: dvips permu-dmtcs.dvi -o permu-dmtcs.ps
%DVIPSParameters: dpi=600, compressed
%DVIPSSource: TeX output 2002.04.24:2155
%%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
/dir 0 def/dyy{/dir 0 def}B/dyt{/dir 1 def}B/dty{/dir 2 def}B/dtt{/dir 3
def}B/p{dir 2 eq{-90 rotate show 90 rotate}{dir 3 eq{-90 rotate show 90
rotate}{show}ifelse}ifelse}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
%%BeginProcSet: 8r.enc
% @@psencodingfile@{
% author = "S. Rahtz, P. MacKay, Alan Jeffrey, B. Horn, K. Berry",
% version = "0.6",
% date = "1 July 1998",
% filename = "8r.enc",
% email = "tex-fonts@@tug.org",
% docstring = "Encoding for TrueType or Type 1 fonts
% to be used with TeX."
% @}
%
% Idea is to have all the characters normally included in Type 1 fonts
% available for typesetting. This is effectively the characters in Adobe
% Standard Encoding + ISO Latin 1 + extra characters from Lucida.
%
% Character code assignments were made as follows:
%
% (1) the Windows ANSI characters are almost all in their Windows ANSI
% positions, because some Windows users cannot easily reencode the
% fonts, and it makes no difference on other systems. The only Windows
% ANSI characters not available are those that make no sense for
% typesetting -- rubout (127 decimal), nobreakspace (160), softhyphen
% (173). quotesingle and grave are moved just because it's such an
% irritation not having them in TeX positions.
%
% (2) Remaining characters are assigned arbitrarily to the lower part
% of the range, avoiding 0, 10 and 13 in case we meet dumb software.
%
% (3) Y&Y Lucida Bright includes some extra text characters; in the
% hopes that other PostScript fonts, perhaps created for public
% consumption, will include them, they are included starting at 0x12.
%
% (4) Remaining positions left undefined are for use in (hopefully)
% upward-compatible revisions, if someday more characters are generally
% available.
%
% (5) hyphen appears twice for compatibility with both
% ASCII and Windows.
%
/TeXBase1Encoding [
% 0x00 (encoded characters from Adobe Standard not in Windows 3.1)
/.notdef /dotaccent /fi /fl
/fraction /hungarumlaut /Lslash /lslash
/ogonek /ring /.notdef
/breve /minus /.notdef
% These are the only two remaining unencoded characters, so may as
% well include them.
/Zcaron /zcaron
% 0x10
/caron /dotlessi
% (unusual TeX characters available in, e.g., Lucida Bright)
/dotlessj /ff /ffi /ffl
/.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef
% very contentious; it's so painful not having quoteleft and quoteright
% at 96 and 145 that we move the things normally found there to here.
/grave /quotesingle
% 0x20 (ASCII begins)
/space /exclam /quotedbl /numbersign
/dollar /percent /ampersand /quoteright
/parenleft /parenright /asterisk /plus /comma /hyphen /period /slash
% 0x30
/zero /one /two /three /four /five /six /seven
/eight /nine /colon /semicolon /less /equal /greater /question
% 0x40
/at /A /B /C /D /E /F /G /H /I /J /K /L /M /N /O
% 0x50
/P /Q /R /S /T /U /V /W
/X /Y /Z /bracketleft /backslash /bracketright /asciicircum /underscore
% 0x60
/quoteleft /a /b /c /d /e /f /g /h /i /j /k /l /m /n /o
% 0x70
/p /q /r /s /t /u /v /w
/x /y /z /braceleft /bar /braceright /asciitilde
/.notdef % rubout; ASCII ends
% 0x80
/.notdef /.notdef /quotesinglbase /florin
/quotedblbase /ellipsis /dagger /daggerdbl
/circumflex /perthousand /Scaron /guilsinglleft
/OE /.notdef /.notdef /.notdef
% 0x90
/.notdef /.notdef /.notdef /quotedblleft
/quotedblright /bullet /endash /emdash
/tilde /trademark /scaron /guilsinglright
/oe /.notdef /.notdef /Ydieresis
% 0xA0
/.notdef % nobreakspace
/exclamdown /cent /sterling
/currency /yen /brokenbar /section
/dieresis /copyright /ordfeminine /guillemotleft
/logicalnot
/hyphen % Y&Y (also at 45); Windows' softhyphen
/registered
/macron
% 0xD0
/degree /plusminus /twosuperior /threesuperior
/acute /mu /paragraph /periodcentered
/cedilla /onesuperior /ordmasculine /guillemotright
/onequarter /onehalf /threequarters /questiondown
% 0xC0
/Agrave /Aacute /Acircumflex /Atilde /Adieresis /Aring /AE /Ccedilla
/Egrave /Eacute /Ecircumflex /Edieresis
/Igrave /Iacute /Icircumflex /Idieresis
% 0xD0
/Eth /Ntilde /Ograve /Oacute
/Ocircumflex /Otilde /Odieresis /multiply
/Oslash /Ugrave /Uacute /Ucircumflex
/Udieresis /Yacute /Thorn /germandbls
% 0xE0
/agrave /aacute /acircumflex /atilde
/adieresis /aring /ae /ccedilla
/egrave /eacute /ecircumflex /edieresis
/igrave /iacute /icircumflex /idieresis
% 0xF0
/eth /ntilde /ograve /oacute
/ocircumflex /otilde /odieresis /divide
/oslash /ugrave /uacute /ucircumflex
/udieresis /yacute /thorn /ydieresis
] def
%%EndProcSet
%%BeginProcSet: texps.pro
%!
TeXDict begin/rf{findfont dup length 1 add dict begin{1 index/FID ne 2
index/UniqueID ne and{def}{pop pop}ifelse}forall[1 index 0 6 -1 roll
exec 0 exch 5 -1 roll VResolution Resolution div mul neg 0 0]/Metrics
exch def dict begin 0 1 255{exch dup type/integertype ne{pop pop 1 sub
dup 0 le{pop}{[}ifelse}{FontMatrix 0 get div Metrics 0 get div def}
ifelse}for Metrics/Metrics currentdict end def[2 index currentdict end
definefont 3 -1 roll makefont/setfont cvx]cvx def}def/ObliqueSlant{dup
sin S cos div neg}B/SlantFont{4 index mul add}def/ExtendFont{3 -1 roll
mul exch}def/ReEncodeFont{CharStrings rcheck{/Encoding false def dup[
exch{dup CharStrings exch known not{pop/.notdef/Encoding true def}if}
forall Encoding{]exch pop}{cleartomark}ifelse}if/Encoding exch def}def
end
%%EndProcSet
%%BeginProcSet: special.pro
%!
TeXDict begin/SDict 200 dict N SDict begin/@SpecialDefaults{/hs 612 N
/vs 792 N/ho 0 N/vo 0 N/hsc 1 N/vsc 1 N/ang 0 N/CLIP 0 N/rwiSeen false N
/rhiSeen false N/letter{}N/note{}N/a4{}N/legal{}N}B/@scaleunit 100 N
/@hscale{@scaleunit div/hsc X}B/@vscale{@scaleunit div/vsc X}B/@hsize{
/hs X/CLIP 1 N}B/@vsize{/vs X/CLIP 1 N}B/@clip{/CLIP 2 N}B/@hoffset{/ho
X}B/@voffset{/vo X}B/@angle{/ang X}B/@rwi{10 div/rwi X/rwiSeen true N}B
/@rhi{10 div/rhi X/rhiSeen true N}B/@llx{/llx X}B/@lly{/lly X}B/@urx{
/urx X}B/@ury{/ury X}B/magscale true def end/@MacSetUp{userdict/md known
{userdict/md get type/dicttype eq{userdict begin md length 10 add md
maxlength ge{/md md dup length 20 add dict copy def}if end md begin
/letter{}N/note{}N/legal{}N/od{txpose 1 0 mtx defaultmatrix dtransform S
atan/pa X newpath clippath mark{transform{itransform moveto}}{transform{
itransform lineto}}{6 -2 roll transform 6 -2 roll transform 6 -2 roll
transform{itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll
curveto}}{{closepath}}pathforall newpath counttomark array astore/gc xdf
pop ct 39 0 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack}
if}N/txpose{pxs pys scale ppr aload pop por{noflips{pop S neg S TR pop 1
-1 scale}if xflip yflip and{pop S neg S TR 180 rotate 1 -1 scale ppr 3
get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip
yflip not and{pop S neg S TR pop 180 rotate ppr 3 get ppr 1 get neg sub
neg 0 TR}if yflip xflip not and{ppr 1 get neg ppr 0 get neg TR}if}{
noflips{TR pop pop 270 rotate 1 -1 scale}if xflip yflip and{TR pop pop
90 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get
neg sub neg TR}if xflip yflip not and{TR pop pop 90 rotate ppr 3 get ppr
1 get neg sub neg 0 TR}if yflip xflip not and{TR pop pop 270 rotate ppr
2 get ppr 0 get neg sub neg 0 S TR}if}ifelse scaleby96{ppr aload pop 4
-1 roll add 2 div 3 1 roll add 2 div 2 copy TR .96 dup scale neg S neg S
TR}if}N/cp{pop pop showpage pm restore}N end}if}if}N/normalscale{
Resolution 72 div VResolution 72 div neg scale magscale{DVImag dup scale
}if 0 setgray}N/psfts{S 65781.76 div N}N/startTexFig{/psf$SavedState
save N userdict maxlength dict begin/magscale true def normalscale
currentpoint TR/psf$ury psfts/psf$urx psfts/psf$lly psfts/psf$llx psfts
/psf$y psfts/psf$x psfts currentpoint/psf$cy X/psf$cx X/psf$sx psf$x
psf$urx psf$llx sub div N/psf$sy psf$y psf$ury psf$lly sub div N psf$sx
psf$sy scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub
TR/showpage{}N/erasepage{}N/copypage{}N/p 3 def @MacSetUp}N/doclip{
psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2
roll moveto 6 -1 roll S lineto S lineto S lineto closepath clip newpath
moveto}N/endTexFig{end psf$SavedState restore}N/@beginspecial{SDict
begin/SpecialSave save N gsave normalscale currentpoint TR
@SpecialDefaults count/ocount X/dcount countdictstack N}N/@setspecial{
CLIP 1 eq{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto
closepath clip}if ho vo TR hsc vsc scale ang rotate rwiSeen{rwi urx llx
sub div rhiSeen{rhi ury lly sub div}{dup}ifelse scale llx neg lly neg TR
}{rhiSeen{rhi ury lly sub div dup scale llx neg lly neg TR}if}ifelse
CLIP 2 eq{newpath llx lly moveto urx lly lineto urx ury lineto llx ury
lineto closepath clip}if/showpage{}N/erasepage{}N/copypage{}N newpath}N
/@endspecial{count ocount sub{pop}repeat countdictstack dcount sub{end}
repeat grestore SpecialSave restore end}N/@defspecial{SDict begin}N
/@fedspecial{end}B/li{lineto}B/rl{rlineto}B/rc{rcurveto}B/np{/SaveX
currentpoint/SaveY X N 1 setlinecap newpath}N/st{stroke SaveX SaveY
moveto}N/fil{fill SaveX SaveY moveto}N/ellipse{/endangle X/startangle X
/yrad X/xrad X/savematrix matrix currentmatrix N TR xrad yrad scale 0 0
1 startangle endangle arc savematrix setmatrix}N end
%%EndProcSet
TeXDict begin 39158280 55380996 1000 600 600 (permu-dmtcs.dvi)
@start
%DVIPSBitmapFont: Fa cmsy10 6 1
/Fa 1 49 df<EA03C0EA07E0A4EA0FC0A31380121F1300A3121E123EA2123CA25AA31270
A212F05A12600B1A7F9B0E> 48 D E
%EndDVIPSBitmapFont
%DVIPSBitmapFont: Fb cmex10 10 6
/Fb 6 18 df<1430147014E0EB01C01303EB0780EB0F00A2131E5BA25B13F85B12015B12
03A2485AA3485AA3121F90C7FCA25AA3123EA2127EA6127C12FCB3A2127C127EA6123EA2
123FA37EA27F120FA36C7EA36C7EA212017F12007F13787FA27F7FA2EB0780EB03C01301
EB00E0147014301462738226> 0 D<12C07E12707E123C7E7EA26C7E6C7EA26C7E7F1200
7F1378137CA27FA37FA31480130FA214C0A31307A214E0A6130314F0B3A214E01307A614
C0A2130FA31480A2131F1400A3133EA35BA2137813F85B12015B485AA2485A48C7FCA212
1E5A12385A5A5A14627C8226> I<1538EC01F8EC07E0EC1F80EC7E005CEB03F85C495AA2
495AB3AB131F5CA249C7FC137E5BEA03F8EA07E0EA3F8000FCC8FCA2EA3F80EA07E0EA03
F8C67E137E7F6D7EA280130FB3AB6D7EA26D7E80EB00FC147EEC1F80EC07E0EC01F8EC00
381D62778230> 8 D<12E012FCEA3F80EA07E0EA03F8C67E137E7F6D7EA280130FB3AB6D
7EA26D7E80EB00FC147EEC1F80EC07E0EC01F8A2EC07E0EC1F80EC7E005CEB03F85C495A
A2495AB3AB131F5CA249C7FC137E5BEA03F8EA07E0EA3F8000FCC8FC12E01D62778230>
I<151E153E157C15F8EC01F0EC03E01407EC0FC0EC1F8015005C147E5CA2495A495AA249
5AA2495AA2495AA249C7FCA2137EA213FE5B12015BA212035BA21207A25B120FA35B121F
A45B123FA548C8FCA912FEB3A8127FA96C7EA5121F7FA4120F7FA312077FA21203A27F12
01A27F12007F137EA27FA26D7EA26D7EA26D7EA26D7EA26D7E6D7EA2147E80801580EC0F
C0EC07E01403EC01F0EC00F8157C153E151E1F94718232> 16 D<12F07E127C7E7E6C7E
7F6C7E6C7E12017F6C7E137EA27F6D7EA26D7EA26D7EA26D7EA26D7EA26D7EA280147E14
7F80A21580141FA215C0A2140F15E0A3140715F0A4140315F8A5EC01FCA9EC00FEB3A8EC
01FCA9EC03F8A515F01407A415E0140FA315C0141FA21580A2143F1500A25C147E14FE5C
A2495AA2495AA2495AA2495AA2495AA249C7FC137EA25B485A5B1203485A485A5B48C8FC
123E5A5A5A1F947D8232> I E
%EndDVIPSBitmapFont
%DVIPSBitmapFont: Fc lasy10 10 1
/Fc 1 51 df<003FB712FEB9FCA300F0C9120FB3B3A4B9FCA4303079B43E> 50
D E
%EndDVIPSBitmapFont
%DVIPSBitmapFont: Fd cmr10 9 1
/Fd 1 62 df<B91280A3CCFCADB91280A331137C9B3A> 61 D E
%EndDVIPSBitmapFont
%DVIPSBitmapFont: Fe cmmi10 9 2
/Fe 2 60 df<123C127E12FFA4127E123C08087A8715> 58 D<123C127EB4FCA21380A2
127F123D1201A412031300A25A1206120E120C5A12385A122009177A8715> I
E
%EndDVIPSBitmapFont
/Ff 140[ 45 115[{ } 1 74.7198 /Symbol rf /Fg 133[ 50
50 1[ 72 50 55 28 50 33 2[ 55 55 83 22 50 1[ 22 55 55
28 55 55 50 1[ 55 12[ 61 3[ 66 1[ 72 83 55 5[ 61 11[ 28
5[ 55 55 55 55 2[ 28 43[ 50 2[{ TeXBase1Encoding ReEncodeFont} 34
99.6264 /Helvetica-Oblique rf
%DVIPSBitmapFont: Fh msam10 10 1
/Fh 1 63 df<126012F812FEEA7F80EA3FE0EA0FF8EA03FEC66C7EEB3FE0EB0FF8EB03FE
903800FF80EC3FE0EC0FF8EC03FE913800FF80ED3FE0ED0FF8ED03FE923800FF80EE3FE0
EE0FF8EE03FE933800FF80EF3FC0171FEF7F80933801FF00EE07FCEE1FF0EE7FC04B48C7
FCED07FCED1FF0ED7FC04A48C8FCEC07FCEC1FF0EC7FC04948C9FCEB07FCD91FF0EC0180
D97FC0EC07C04848C8121FD807FCED7F80D81FF0913801FF00D87FC0EC07FC48C8EA1FF0
00FCED7FC000704A48C7FCC8EA07FCED1FF0ED7FC04A48C8FCEC07FCEC1FF0EC7FC04948
C9FCEB07FCEB1FF0EB7FC04848CAFCEA07FCEA1FF0EA7FC048CBFC12FC1270324479B441
> 62 D E
%EndDVIPSBitmapFont
%DVIPSBitmapFont: Fi cmsy10 7.39999 6
/Fi 6 104 df<B712F8A325037B9030> 0 D<0107B512F8133F5BD801FCC8FCEA03E048
5A48C9FC121E121C123C123812781270A212F05AA77E1270A212781238123C121C121E7E
EA07C0EA03F0EA01FED8007FB512F8131F130325257BA130> 26
D<13F0EA01F81203A3EA07F0A313E0A2120F13C0A21380A2121F1300A3123EA2123CA35A
A3127012F05AA20D1F7EA111> 48 D<903807FFFC133F5BD801FCC7FCEA03E0485A48C8
FC121E121C123C123812781270A212F05AA2B612FCA300E0C8FCA27E1270A21278123812
3C121C121E7EEA07C0EA03F0EA01FC39007FFFFC131F13071E257BA129> 50
D<14FC1303EB0FC0EB1F00133C137C1378B35BA2485AEA07C0B4C7FC12F8B4FCEA07C0EA
01E06C7EA21378B3137C133C131FEB0FC0EB03FC1300163D7CAD1F> 102
D<12FCB4FCEA0FC0EA03E0C67E7F1378B37FA27FEB0F80EB03FCEB007CEB03FCEB0F80EB
1E005BA25BB313F85BEA03E0EA0FC0B4C7FC12FC163D7CAD1F> I
E
%EndDVIPSBitmapFont
%DVIPSBitmapFont: Fj cmsy10 10 16
/Fj 16 111 df<007FB81280B912C0A26C17803204799641> 0 D<EB1FF0EBFFFE487F00
0714C04814E04814F04814F8A24814FCA3B612FEA96C14FCA36C14F8A26C14F06C14E06C
14C0000114006C5BEB1FF01F1F7BA42A> 15 D<126012F812FEEA7F80EA3FE0EA0FF8EA
03FEC66C7EEB3FE0EB0FF8EB03FE903800FF80EC3FE0EC0FF8EC03FE913800FF80ED3FE0
ED0FF8ED03FE923800FF80EE3FE0EE0FF8EE03FE933800FF80EF3FC0171FEF7F80933801
FF00EE07FCEE1FF0EE7FC04B48C7FCED07FCED1FF0ED7FC04A48C8FCEC07FCEC1FF0EC7F
C04948C9FCEB07FCEB1FF0EB7FC04848CAFCEA07FCEA1FF0EA7FC048CBFC12FC1270CCFC
AE007FB81280B912C0A26C1780324479B441> 21 D<020FB6128091B712C01303010F16
80D91FF8C9FCEB7F8001FECAFCEA01F8485A485A485A5B48CBFCA2123EA25AA2127812F8
A25AA87EA21278127CA27EA27EA26C7E7F6C7E6C7E6C7EEA00FEEB7F80EB1FF86DB71280
010316C01300020F1580323279AD41> 26 D<1478A414F85CA213015C1303495AA2495A
49CCFC5B137E5B485A485AEA0FE0003FBA12FEBCFCA2003F19FED80FE0CCFCEA03F06C7E
6C7E137E7F7F6D7E6D7EA26D7E1301801300A2801478A4482C7BAA53> 32
D<173CA2173E171E171F8384717E170384717E717E187C007FB812FEBAFC856C84CBEA03
F0727EF000FEF13F80F11FE0F107F8F101FFA2F107F8F11FE0F13F80F1FE00F001F84E5A
007FB912C0BA5A96C7FC6C5FCB127C604D5A4D5A6017074D5A95C8FC5F171E173E173CA2
48307BAC53> 41 D<91381FFFFE91B6FC1303010F14FED91FF0C7FCEB7F8001FEC8FCEA
01F8485A485A485A5B48C9FCA2123EA25AA2127812F8A25AA2B712FE16FFA216FE00F0C9
FCA27EA21278127CA27EA27EA26C7E7F6C7E6C7E6C7EEA00FEEB7F80EB1FF06DB512FE01
0314FF1300021F13FE283279AD37> 50 D<EE0180EE03C01607A2EE0F80A2EE1F00A216
3EA25EA25EA24B5AA24B5AA24B5A150F5E4BC7FCA2153EA25DA25DA24A5AA24A5AA24A5A
A24A5AA24AC8FCA2143EA25CA25CA2495AA2495AA2495AA2495AA249C9FCA2133EA25B13
FC5B485AA2485AA2485AA2485AA248CAFCA2123EA25AA25AA25A12602A4E75BB00> 54
D<0060161800F0163C6C167CA200781678007C16F8A2003C16F0003E1501A26CED03E0A2
6C16C06D1407A2000716806D140FA26C6CEC1F00A26CB612FEA36C5D01F8C7127CA2017C
5CA2013C5C013E1301A2011E5C011F1303A26D6C485AA201075CECC00FA2010391C7FC6E
5AA2903801F03EA20100133CECF87CA2EC7878EC7CF8A2EC3FF0A26E5AA36E5AA36E5A6E
C8FC2E3C80B92F> 56 D<007FB612F0B712F8A27EC91278B3A5003FB612F85AA27EC912
78B3A5007FB612F8B7FCA26C15F0253A7CB92E> I<0060161800F0163CB3B26C167CA200
7C16F8A26CED01F0003F15036C6CEC07E06C6CEC0FC0D807F0EC3F80D803FE903801FF00
3A00FFC00FFC6DB55A011F14E0010391C7FC9038007FF82E347CB137> 91
D<EC7FF80103B5FC011F14E0017F14F89039FFC00FFC3A03FE0001FFD807F09038003F80
D80FC0EC0FC04848EC07E048C8EA03F0003E150148ED00F8A248167CA248163CB3B20060
16182E347CB137> I<EC01F8140FEC3F80ECFC00495A495A495AA2130F5CB3A7131F5C13
3F49C7FC13FEEA03F8EA7FE048C8FCEA7FE0EA03F8EA00FE137F6D7E131F80130FB3A780
1307A26D7E6D7E6D7EEC3F80EC0FF814011D537ABD2A> 102 D<12FCEAFFC0EA07F0EA01
FCEA007E7F80131F80130FB3A7801307806D7E6D7EEB007EEC1FF0EC07F8EC1FF0EC7E00
495A495A495A5C130F5CB3A7131F5C133F91C7FC137E485AEA07F0EAFFC000FCC8FC1D53
7ABD2A> I<126012F0B3B3B3B3A91260045377BD17> 106 D<126012F07EA21278127CA2
123C123EA2121E121FA27E7FA212077FA212037FA212017FA212007FA21378137CA2133C
133EA2131E131FA27F80A2130780A26D7EA2130180A2130080A21478147CA2143C143EA2
141E141FA2801580A2140715C0A2140315E0A2140115F0A2140015F8A21578157CA2153C
153EA2151E150C1F537BBD2A> 110 D E
%EndDVIPSBitmapFont
%DVIPSBitmapFont: Fk cmsy8 8 1
/Fk 1 14 df<ED7FF80207B57E021F14E091397FC00FF8D901FCC712FED903F0143FD90F
C0EC0FC049C8EA03E0013E6F7E0178ED0078498248488248488249820007188048CAEA03
C0000E1701001E18E0001C1700003C18F0003818700078187800701838A300F0183C4818
1CA96C183C00701838A30078187800381870003C18F0001C18E0001E1701000E18C0000F
17036C6CEE0780000318006D5E6C6C161E6C6C5E01785E013E4B5A6D4B5AD90FC0EC0FC0
D903F0023FC7FCD901FC14FE903A007FC00FF8021FB512E0020714809126007FF8C8FC3E
3D7CAE47> 13 D E
%EndDVIPSBitmapFont
/Fl 105[ 33 28[ 33 3[ 33 18 26 22 1[ 33 33 33 52 18 2[ 18
33 2[ 29 33 29 1[ 29 12[ 41 37 4[ 48 59 6[ 37 1[ 48 44
10[ 33 1[ 33 33 1[ 33 33 33 33 3[ 17 2[ 22 22 40[{
TeXBase1Encoding ReEncodeFont} 34 66.4176 /Times-Roman
rf /Fm 133[ 32 37 1[ 55 37 46 23 32 32 1[ 42 42 46 65
23 42 1[ 23 46 42 28 37 42 37 42 42 19[ 74 8[ 60 68[{
TeXBase1Encoding ReEncodeFont} 25 83.022 /Times-BoldItalic
rf /Fn 148[ 22 107[{ TeXBase1Encoding ReEncodeFont} 1
49.8132 /Times-Italic rf /Fo 206[ 25 49[{ TeXBase1Encoding ReEncodeFont}
1 49.8132 /Times-Roman rf /Fp 256[{ } 0 49.8132 /Symbol
rf
%DVIPSBitmapFont: Fq cmr10 7.39999 4
/Fq 4 94 df<141CB3B81280A3C7001CC8FCB329297DA330> 43
D<B81280A3CBFCA9B81280A3290F7D9630> 61 D<EAFFC0A3EAE000B3B3B3EAFFC0A30A
3D7BAD11> 91 D<EAFFC0A31201B3B3B312FFA30A3D7FAD11> 93
D E
%EndDVIPSBitmapFont
/Fr 198[ 31 31 2[ 31 1[ 31 31 31 31 48[{ TeXBase1Encoding ReEncodeFont}
7 61.4362 /Times-Roman rf
%DVIPSBitmapFont: Fs cmmi10 7.39999 1
/Fs 1 60 df<1238127C12FEA212FF127F123B1203A41206A2120CA21218123812701220
08137B8611> 59 D E
%EndDVIPSBitmapFont
/Ft 135[ 27 5[ 24 5[ 17 27 17 17 7[ 31 16[ 38 1[ 41 51
5[ 44 71[{ TeXBase1Encoding ReEncodeFont} 11 61.4362
/Times-Italic rf /Fu 256[{ } 0 61.4362 /Symbol rf
%DVIPSBitmapFont: Fv cmr10 10 6
/Fv 6 94 df<146014E0EB01C0EB0380EB0700130E131E5B5BA25B485AA2485AA212075B
120F90C7FCA25A121EA2123EA35AA65AB2127CA67EA3121EA2121F7EA27F12077F1203A2
6C7EA26C7E1378A27F7F130E7FEB0380EB01C0EB00E01460135278BD20> 40
D<12C07E12707E7E7E120F6C7E6C7EA26C7E6C7EA21378A2137C133C133E131EA2131F7F
A21480A3EB07C0A6EB03E0B2EB07C0A6EB0F80A31400A25B131EA2133E133C137C1378A2
5BA2485A485AA2485A48C7FC120E5A5A5A5A5A13527CBD20> I<15301578B3A6007FB812
F8B912FCA26C17F8C80078C8FCB3A6153036367BAF41> 43 D<007FB812F8B912FCA26C
17F8CCFCAE007FB812F8B912FCA26C17F836167B9F41> 61 D<EAFFF8A4EAF000B3B3B3
B3A3EAFFF8A40D5378BD17> 91 D<EAFFF8A4EA0078B3B3B3B3A3EAFFF8A40D537FBD17>
93 D E
%EndDVIPSBitmapFont
%DVIPSBitmapFont: Fw cmmi10 10 4
/Fw 4 62 df<121C127FEAFF80A5EA7F00121C0909798817> 58
D<121C127FEAFF80A213C0A3127F121C1200A412011380A2120313005A1206120E5A5A5A
12600A19798817> I<EF0380EF0FC0173FEFFF80933803FE00EE0FF8EE3FE0EEFF80DB03
FEC7FCED0FF8ED3FE0EDFF80DA03FEC8FCEC0FF8EC3FE0ECFF80D903FEC9FCEB0FF8EB3F
E0EBFF80D803FECAFCEA0FF8EA3FE0EA7F8000FECBFCA2EA7F80EA3FE0EA0FF8EA03FEC6
6C7EEB3FE0EB0FF8EB03FE903800FF80EC3FE0EC0FF8EC03FE913800FF80ED3FE0ED0FF8
ED03FE923800FF80EE3FE0EE0FF8EE03FE933800FF80EF3FC0170FEF0380323279AD41>
I<150C151E153EA2153C157CA2157815F8A215F01401A215E01403A215C01407A2158014
0FA215005CA2141E143EA2143C147CA2147814F8A25C1301A25C1303A2495AA25C130FA2
91C7FC5BA2131E133EA2133C137CA2137813F8A25B1201A25B1203A25B1207A25B120FA2
90C8FC5AA2121E123EA2123C127CA2127812F8A25A12601F537BBD2A> I
E
%EndDVIPSBitmapFont
/Fx 140[ 50 16[ 46 52 25[ 50 22[ 42 23 47[{ } 6 83.022
/Symbol rf /Fy 134[ 60 60 86 1[ 66 33 60 40 1[ 66 66
66 100 27 60 1[ 27 66 66 33 66 66 60 1[ 66 12[ 73 1[ 86
4[ 100 5[ 93 73 2[ 86 1[ 80 10[ 66 66 66 66 66 66 49[{
TeXBase1Encoding ReEncodeFont} 34 119.552 /Helvetica
rf /Fz 134[ 37 1[ 54 3[ 29 33 2[ 37 5[ 21 1[ 37 1[ 33
42 24[ 58 4[ 46 11[ 25 2[ 37 37 37 37 37 37 37 2[ 19
46[{ TeXBase1Encoding ReEncodeFont} 20 74.7198 /Times-Bold
rf /FA 133[ 33 37 37 54 37 37 21 29 25 1[ 37 37 37 58
21 37 21 21 37 37 25 33 37 33 37 33 3[ 25 1[ 25 6[ 46
42 2[ 42 54 1[ 66 3[ 25 54 54 42 4[ 54 10[ 37 37 37 37
1[ 37 37 1[ 19 25 19 41[ 42 2[{ TeXBase1Encoding ReEncodeFont} 47
74.7198 /Times-Roman rf
%DVIPSBitmapFont: FB cmsy9 9 2
/FB 2 104 df<EC07E0143FECFE00EB03F8495A495A5C131F5CB3A5133F91C7FC137E5B
EA03F8EA7FE048C8FCEA7FE0EA03F8C67E137E7F80131FB3A580130F806D7E6D7EEB00FE
EC3FE014071B4B7BB726> 102 D<12FCEAFFC0EA07F0EA01FC6C7E137F7F80131FB3A580
130F6D7E6D7EEB01FC9038007FC0EC1FE0EC7FC0903801FC00EB03F0495A495A131F5CB3
A5133F91C7FC5B13FE485AEA07F0EAFFC000FCC8FC1B4B7BB726> I
E
%EndDVIPSBitmapFont
/FC 139[ 45 1[ 45 1[ 45 45 45 45 45 2[ 45 45 45 45 45
1[ 45 45 45 32[ 45 5[ 45 11[ 45 1[ 45 44[{ TeXBase1Encoding ReEncodeFont
} 19 74.7198 /Courier-Oblique rf /FD 75[ 25 29[ 37 29[ 33
1[ 33 37 21 29 29 1[ 37 37 37 1[ 21 2[ 21 3[ 33 37 33
1[ 37 11[ 54 1[ 37 46 3[ 50 62 42 2[ 25 2[ 46 2[ 50 1[ 46
7[ 37 2[ 37 37 37 37 37 37 37 2[ 25 19 44[{
TeXBase1Encoding ReEncodeFont} 37 74.7198 /Times-Italic
rf /FE 139[ 33 47 40 1[ 60 60 60 1[ 33 2[ 33 60 60 1[ 53
60 53 60 53 19[ 106 4[ 86 1[ 66 2[ 80 22[ 30 41[ 66 2[{
TeXBase1Encoding ReEncodeFont} 21 119.552 /Times-Roman
rf /FF 133[ 86 4[ 96 48 86 57 1[ 96 96 96 143 3[ 38 96
96 1[ 96 96 86 1[ 96 16[ 115 8[ 134 105 1[ 124 68[{
TeXBase1Encoding ReEncodeFont} 20 172.188 /Helvetica-Oblique
rf /FG 75[ 28 11[ 28 17[ 42 1[ 37 37 10[ 28 13[ 37 42
42 60 42 42 23 32 28 42 42 42 42 65 23 42 23 23 42 42
28 37 42 37 42 37 3[ 28 1[ 28 1[ 60 1[ 78 60 60 51 46
55 1[ 46 60 60 74 51 60 32 28 60 60 46 51 60 55 55 60
5[ 23 23 42 42 42 42 42 42 42 42 42 42 1[ 21 28 21 2[ 28
28 28 5[ 28 2[ 28 27[ 46 2[{ TeXBase1Encoding ReEncodeFont} 78
83.022 /Times-Roman rf /FH 134[ 42 1[ 60 42 46 28 32
37 1[ 46 42 46 69 23 1[ 28 23 46 42 28 37 46 37 46 42
12[ 55 3[ 51 1[ 60 78 55 5[ 51 1[ 60 60 8[ 28 3[ 42 42
42 42 42 42 7[ 28 28 37[ 46 2[{ TeXBase1Encoding ReEncodeFont} 40
83.022 /Times-Bold rf /FI 75[ 28 57[ 32 37 37 55 37 42
23 32 32 42 42 42 42 60 23 37 23 23 42 42 23 37 42 37
42 42 8[ 51 69 1[ 60 46 42 51 1[ 51 60 55 69 46 1[ 37
28 60 60 51 51 60 55 1[ 51 6[ 28 42 42 42 42 1[ 42 42
42 42 42 1[ 21 28 21 2[ 28 28 28 36[ 42 2[{
TeXBase1Encoding ReEncodeFont} 64 83.022 /Times-Italic
rf end
%%EndProlog
%%BeginSetup
%%Feature: *Resolution 600dpi
TeXDict begin
%%PaperSize: A4
%%EndSetup
%%Page: 55 1
55 0 bop FI 83 232 a(Discr) m(ete) 21 b(Mathematics) f(and) f(Theor) m
(etical) g(Computer) h(Science) p FH 20 w(5) p FG(,) g(200) n(2,) g
(55\2267) n(0) p FF 83 713 a(Gr) n(aph) 48 b(Decompositions) f(and) g
(F) -9 b(actor) s(izing) 83 921 y(P) g(er) t(m) n(utations) p
FE 83 1240 a(Christian) 29 b(Capelle,) h(Michel) h(Habib) f(and) f(F) n
(abien) i(de) f(Montgol\002er) p FD 83 1418 a(LIRMM) 18
b(\226) h(UMR) g(5506) h(Univer) o(sit) t(\264) -29 b(e) 19
b(Montpellier) h(II) e(et) h(CNRS) 83 1510 y(161,) g(rue) h(Ada) f
(\226) g(34) g(392) h(Montpellier) f(Cede) o(x) g(05) h(-) e(F) l(r) o
(ance) p FC 83 1601 a(email:) p FB 44 w(f) p FC(capelle,hab) n
(ib,montgolfi) n(er) p FB(g) p FC(@lirmm.fr) p FI 83
1788 a(r) m(eceived) i(J) m(ul) g(16,) g(199) n(8) p
FG(,) p FI 20 w(r) m(e) o(vised) g(A) n(ug) g(22,) g(200) n(0) p
FG(,) p FI 20 w(accepted) f(Sep) h(22,) f(2001) p FG
-2 w(.) p 83 1879 3487 9 v FA 83 2036 a(A) f(f) o(actorizing) h
(permutation) h(of) e(a) g(gi) n(v) o(en) i(graph) f(is) f(simply) h(a)
f(permutation) h(of) g(its) f(v) o(ertices) g(of) g(which) h(all) f
(decomp) r(osition) g(sets) h(are) 83 2127 y(f) o(actors) 24
b([3) q(].) 38 b(Such) 24 b(a) g(conce) r(pt) g(appears) h(to) f(play) g
(a) g(central) g(role) g(in) g(recent) h(papers) g(dealing) f(with) g
(graph) h(decomp) r(osition.) 39 b(It) 23 b(is) 83 2218
y(applied) e(here) f(for) g(modu) r(lar) f(decomp) r(osition) h(of) g
(directed) h(graphs,) g(and) g(we) f(propose) h(a) f(simple) g(linear) g
(algorithm) h(that) f(computes) 83 2310 y(the) f(whole) g(decom) r
(position) g(tree) g(when) g(a) g(f) o(actorizing) h(permutation) f(is)
g(pro) o(vided.) 83 2438 y(The) 25 b(approa) r(ch) g(of) h(using) g
(parenthesized) h(f) o(actors) e(of) h(a) f(list) g(w) o(as) g(\002rst)
g(used) h(by) g(Hopcroft) f(and) h(T) -6 b(arjan) 26
b(for) f(triconnected) h(com-) 83 2529 y(ponen) r(ts) e(search) h([14) q
(].) 40 b(Our) 25 b(algorithm) g(can) g(be) g(seen) h(as) e(a) h
(common) h(generalization) g(of) f(Hsu) g(and) g(Ma) g([16) q(,) f(15) q
(]) g(for) h(modular) 83 2621 y(decomp) r(osition) c(of) g(chordal) h
(graphs) g(and) f(Habib,) h(Huchard) g(and) f(Spinrad) h([10]) f(for) g
(inheritance) g(graph) r(s) f(decom) r(position) h([1].) 29
b(It) 83 2712 y(also) 19 b(suggests) h(man) o(y) g(ne) n(w) f(decompo) r
(sition) g(algorithms) g(for) g(v) n(arious) g(notions) h(of) f(graph) h
(decompo) r(sitions.) p Fz 83 2894 a(K) n(eyw) o(or) r(ds:) p
FA 22 w(Graph) g(algorithms,) f(graph) g(deco) r(mpositions,) g
(modular) h(decompo) r(sition.) p 83 3002 V Fy 83 3263
a(1) 120 b(Gener) o(a) r(l) 32 b(deco) r(mposition) h(fr) o(ame) n(w) o
(or) r(k) p FG 83 3417 a(Man) o(y) f(optim) n(ization) h(metho) n(ds) g
(for) f(graph) n(s) i(be) o(g) n(in) f(with) g(some) g(deco) n
(mposition) f(techn) n(iques,) k(using) c(the) h(classic) 83
3516 y(di) n(vide) 17 b(and) g(conq) n(uer) g(paradig) n(m.) 25
b(W) -7 b(e) 18 b(restrict) g(our) f(study) g(to) h(deco) n(mpositions)
f(that) h(lead) f(to) h(a) g(decom) n(position) f(tree) h(of) 83
3616 y(the) j(set) h(of) e(v) o(ertices.) 27 b(F) o(or) 21
b(a) g(gi) n(v) o(en) e(graph) p FI 20 w(G) p Fv 19 w(=) f(\() p
FI(X) p Fw 8 w(;) p FI 9 w(E) p Fv 6 w(\)) p FG(,) k(such) e(a) i(deco)
n(mposition) e(tree) p FI 21 w(T) p Ft 2668 3628 a(G) p
FG 2738 3616 a(is) i(de\002ned) e(as) h(follo) n(ws:) 26
b(the) 83 3716 y(v) o(ertices) 19 b(of) p FI 19 w(G) p
FG 19 w(are) g(in) h(one-) n(to-one) e(correspo) n(nden) n(ce) i(with) f
(the) h(lea) n(v) o(es) f(of) p FI 19 w(T) p Ft 2296
3728 a(G) p FG 2344 3716 a(,) h(and) f(a) g(node) f(of) h(the) h(tree) f
(corr) n(espond) f(to) 83 3815 y(a) 23 b(subset) h(of) p
FI 22 w(X) p FG 8 w(:) 31 b(the) 24 b(lea) n(v) o(es) f(that) g
(descend) f(from) g(it.) 34 b(Theref) n(ore) 23 b(a) g(node) f(of) p
FI 23 w(T) p Ft 2388 3827 a(G) p FG 2460 3815 a(may) h(be) g
(identi\002ed) f(with) h(the) g(subset) 83 3915 y(of) g(v) o(ertices) g
(it) h(induce) n(s.) 36 b(The) 23 b(roo) n(t) h(is) h(then) e(the) g(v)
o(erte) o(x) f(set) p FI 24 w(X) p FG 31 w(itself.) 36
b(If) 23 b(a) h(nod) n(e) p FI 24 w(N) p FG 29 w(of) p
FI 23 w(T) p Ft 2711 3927 a(G) p FG 2784 3915 a(has) f(children) p
FI 22 w(N) p Fr 3267 3927 a(1) p Fw 3302 3915 a(;) 9
b(:) g(:) g(:) h(;) p FI 9 w(N) p Ft 3516 3928 a(k) p
FG 3549 3915 a(,) 83 4014 y(this) 20 b(means) f(that) h(the) g(indu) n
(ced) g(subg) n(raph) p FI 19 w(G) p Ft 1389 4026 a(N) p
FG 1458 4014 a(admits) f(the) h(decom) n(position) p
FI 19 w(G) p Ft 2390 4026 a(N) p Fo 2429 4038 a(1) p
Fw 2463 4014 a(;) 9 b(:) g(:) g(:) h(;) p FI 9 w(G) p
Ft 2684 4026 a(N) p Fn 2723 4039 a(k) p FG 2754 4014
a(.) 26 b(Let) 19 b(us) h(call) g(the) g(node) n(s) h(of) 83
4114 y(a) g(deco) n(mposition) e(tree) i(\(and) e(the) h(sets) h(of) f
(v) o(ertices) g(the) o(y) f(induce\)) p Fm 19 w(decom) n(position) h
(sets) p FG(.) 166 4216 y(The) j(e) o(xistence) g(of) g(such) g(decom) n
(position) g(trees) h(is) g(the) f(conseque) n(nce) h(of) f(uniq) n
(ueness) h(deco) n(mposition) f(theor) n(ems) 83 4315
y(\(see) 32 b(Cunning) n(ham) f(and) h(Edm) n(onds) g([5) o(]) g(for) f
(a) h(gener) n(al) h(theor) n(y) f(on) f(these) h(combin) n(atorial) g
(decom) n(positions\)) f(and) 83 4415 y(in) e(the) g(follo) n(win) n(g)
h(we) f(will) h(assume) f(that) g(the) g(deco) n(mposition) f(trees) h
(we) h(constru) n(ct) g(are) f(uniq) n(uely) g(de\002ned) f(up) g(to) 83
4514 y(isomorp) n(hism.) 166 4616 y(This) i(paper) e(deals) i(with) g
(the) f(notion) g(of) g(a) p Fm 30 w(facto) n(rizing) i(permutation) p
Fx 29 w(s) p FG 30 w(of) e(the) h(v) o(erte) o(x) e(set) p
FI 30 w(X) p FG 8 w(,) k(and) d(it) h(will) h(be) 83
4716 y(con) m(v) m(enient) 20 b(to) g(conside) n(r) p
Fx 21 w(s) p FG 21 w(as) h(a) f(w) o(ord) p Fx 20 w(s) p
Fv(\() p FG(1) p Fv(\)) p Fx(s) p Fv(\() p FG(2) p Fv(\)) p
Fw 9 w(:) 9 b(:) g(:) p Fx 10 w(s) p Fv(\() p FI(n) p
Fv(\)) p FG(.) p Fl 83 4844 a(1365\226805) r(0) 419 4842
y(c) p Fk 399 4844 a(\015) p Fl 16 w(2002) 17 b(Discret) r(e) g(Mathe) r
(matics) h(and) f(Theoret) r(ical) h(Compute) r(r) f(Scienc) r(e) g
(\(DMTCS\),) f(Nanc) o(y) l(,) h(France) p 90 rotate
dyy eop
%%Page: 56 2
56 1 bop FG 83 232 a(56) p FI 1403 w(Christian) 21 b(Capelle) o(,) e
(Mic) o(hel) i(Habib) e(and) g(F) -6 b(abien) 19 b(de) h(Montgo) n
(l\002er) p FH 83 415 a(De\002nition) g(1) p FI 41 w(A) k(permutatio) n
(n) p Fx 23 w(s) p FI 24 w(of) g(the) f(verte) n(x) h(set) g(X) 31
b(is) 24 b(called) f(a) g(factorizing) g(permuta) n(tion) g(for) h(a) f
(given) g(deco) n(m-) 83 515 y(position) c(if) i(e) o(very) g(deco) n
(mposition) f(set) h(is) g(a) f(factor) g(of) p Fx 20
w(s) p FI 21 w(\(i.e) o(.) 25 b(its) c(vertices) g(app) n(ear) g
(consecu) n(tively) g(in) p Fx 20 w(s) p FI(\).) p FG
166 680 a(Such) c(a) h(permu) n(tation) f(al) o(w) o(ays) h(e) o(xists)
g(as) g(soon) f(as) h(the) g(deco) n(mposition) f(tree) g(is) h(pro) o
(v) n(ided,) g(since) f(it) h(can) g(be) f(obtaine) n(d) 83
779 y(by) j(a) g(simple) h(preo) n(rder) f(tra) n(v) o(er) n(sal) h(of)
f(the) g(tree.) 25 b(In) 20 b(this) h(paper) e(we) i(consid) n(er) g
(the) f(in) m(v) o(e) n(rse) h(pro) n(blem.) p FH 83
982 a(Central) f(Pr) o(o) n(blem:) 216 1164 y(Data) n(:) p
FG 100 w(a) g(graph) p FI 19 w(G) p Fv 19 w(=) d(\() p
FI(X) p Fw 8 w(;) p FI 9 w(E) p Fv 6 w(\)) p FG 21 w(and) j(a) g(f) o
(actorizing) 514 1263 y(perm) n(utation) p Fx 20 w(s) p
FG(.) p FH 220 1363 a(Find:) p FG 100 w(the) g(decom) n(position) g
(tree) 514 1463 y(\(or) f(the) i(deco) n(mposition) e(sets\).) 166
1604 y(F) o(or) k(a) h(leading) e(e) o(xam) n(ple) i(of) f(such) g(a) g
(graph) f(decomp) n(osition,) h(one) g(can) g(tak) o(e) h(the) p
Fm 23 w(mod) n(ular) g(decomp) n(osition) p FG(,) g(also) 83
1704 y(called) p Fm 18 w(substitution) c(deco) n(mposition) p
FG(,) e(of) g(graph) n(s) h(\(an) f(o) o(v) o(er) n(vie) n(w) h(of) f
(this) h(theor) n(y) g(and) e(its) j(applica) n(tions) f(can) f(be) g
(foun) n(d) 83 1803 y(in) 23 b([21) n(]\).) 32 b(W) -7
b(e) 24 b(presen) n(t) f(the) g(basic) f(concepts) g(of) g(this) h
(decom) n(position) f(in) h(the) f(follo) n(win) n(g) h(section.) 31
b(In) 23 b(this) g(article) f(we) 83 1903 y(deal) c(with) h(the) f
(genera) n(l) h(case) g(of) f(decomp) n(osition) g(of) g(directed) f
(graph) n(s.) 26 b(Other) 18 b(e) o(xam) n(ples) h(are) f(modu) n(les) h
(or) f(blocks) g(for) 83 2003 y(inheritan) n(ce) j(ac) o(yc) n(lic) g
(directed) e(graph) n(s) j(leadin) n(g) f(also) f(to) h(deco) n
(mposition) e(trees) i([17) n(,) g(10) o(,) f(2,) g(1].) 166
2106 y(Clearly) j(it) g(could) f(be) h(hard) f(to) h(\002nd) g(a) g(f) o
(actorizin) n(g) g(permu) n(tation,) g(b) n(ut) g(in) g(some) g(cases) g
(a) g(f) o(actorizing) f(perm) n(utation) 83 2206 y(is) k(gi) n(v) o
(en) e(for) h(free.) 40 b(As) 26 b(for) f(e) o(xamp) n(le) h(as) g
(noticed) e(by) h(Hsu) h(and) f(Ma) h([16) n(,) g(15) o(]) f(in) h(the)
f(case) h(of) f(chord) n(al) h(graph) n(s,) h(the) 83
2305 y(cardin) n(ality) h(le) o(xicog) n(raphic) f(brea) n(dth) g
(\002rst) h(search) f(of) g(the) h(grap) n(h) g(yields) f(a) h(f) o
(actor) n(izing) f(permuta) n(tion) h(for) e(modu) n(lar) 83
2405 y(decom) n(position.) e(Similarly) -5 b(,) 18 b(as) h(noticed) f
(by) g(Ducou) n(rnau) g(and) g(Habib) g([8) o(],) h(an) o(y) e
(depth-\002r) n(st) j(greed) n(y) f(linear) f(e) o(xtensio) n(n) 83
2505 y(of) 31 b(an) g(inheritan) n(ce) g(graph) f(yields) h(a) h(f) o
(actorizin) n(g) f(permu) n(tation) g(for) g(the) g(mod) n(ule) h(deco)
n(mposition) e(of) h(inheritan) n(ce) 83 2604 y(graph) n(s.) 166
2708 y(Moreo) m(v) o(er) 23 b(Habib) g(and) g(P) o(aul) h([12) o(]) g
(ha) n(v) o(e) f(pro) n(posed) g(a) h(v) o(ery) f(simple) p
FI 24 w(O) p Fv(\() p FI(n) p Fv 13 w(+) p FI 13 w(m) p
Fv -2 w(\)) p FG 25 w(algorith) n(m) h(to) g(comp) n(ute) g(a) g(f) o
(actor) n(-) 83 2807 y(izing) 29 b(permu) n(tation) g(of) g(a) h(cogr) n
(aph.) 52 b(This) 30 b(w) o(ork) e(has) i(been) f(gene) n(ralized) g
(to) h(mod) n(ular) f(decomp) n(osition) g([13) o(]) g(with) 83
2907 y(an) p FI 26 w(O) p Fv(\() p FI(n) p Fv 14 w(+) p
FI 14 w(m) p FG 7 w(log) p FI 9 w(n) p Fv(\)) p FG 26
w(algor) n(ithm) d(for) f(undirec) n(ted) h(graph) n(s.) 43
b(These) 26 b(algor) n(ithms) g(are) g(easy) g(to) g(unde) n(rstand.) 42
b(As) 26 b(in) g(the) 83 3007 y(pre) n(v) n(ious) c(e) o(xam) n(ples,) g
(the) o(y) e(sho) n(w) h(the) g(usefulne) n(ss) i(of) e(di) n(vid) n
(ing) g(the) g(calculation) f(of) h(the) g(decom) n(position) g(tree) g
(in) g(tw) o(o) 83 3106 y(steps) g(:) 26 b(calculatio) n(n) 21
b(of) f(the) g(f) o(actorizin) n(g) g(permu) n(tation,) g(and) g
(calculation) f(of) h(the) g(tree) g(from) f(this) i(permu) n(tation.)
166 3210 y(Our) k(algorithm) f(deals) i(with) g(the) f(modu) n(lar) h
(decomp) n(osition) f(of) h(grap) n(hs) g(\(directed) e(or) i(not\)) n
(,) i(b) n(ut) d(it) h(can) g(easily) g(be) 83 3309 y(adapted) d(for) i
(the) f(other) g(decomp) n(ositions) h(mentio) n(ned) f(abo) o(v) o(e) f
(for) i(inher) n(itance) g(grap) n(hs.) 39 b(It) 25 b(runs) f(in) p
FI 25 w(O) p Fv(\() p FI(n) p Fv 13 w(+) p FI 13 w(m) p
Fv(\)) p FG(,) i(and) 83 3409 y(therefo) n(re) h(is) h(a) f(comm) n(on)
g(gen) n(eralization) f(of) h(Hsu) g(and) f(Ma) h([16) n(]) g(and) f
(Habib) p FI 27 w(et) h(al.) p FG 44 w([10) o(]) g(which) f(were) h
(relati) n(v) o(e) n(ly) 83 3509 y(sophisticated) p FI
19 w(ad) 20 b(hoc) p FG 20 w(algor) n(ithms.) 25 b(Here) 20
b(we) h(prop) n(ose) g(a) f(simpler) g(algorith) n(m.) 166
3612 y(As) 28 b(a) f(consequ) n(ence,) i(such) e(an) g(algo) n(rithm) g
(and) g(the) g(notio) n(n) g(of) g(f) o(actorizing) f(perm) n(utation) h
(intro) n(duce) g(some) g(ne) n(w) 83 3712 y(perspecti) n(v) m(es) 22
b(for) f(graph) f(decomp) n(osition) h(algorithm) n(s.) 30
b(Indee) n(d,) 22 b(the) g(deco) n(mposition) f(pro) n(cess) i(can) e
(be) h(di) n(vid) n(ed) g(into) 83 3811 y(tw) o(o) 30
b(steps.) 53 b(First,) 32 b(\002nd) d(a) h(w) o(ay) g(to) f(produ) n
(ce) h(a) g(f) o(actor) n(izing) f(permutatio) n(n,) j(and) d(then) g
(use) g(the) h(gene) n(ral) g(algorith) n(m) 83 3911
y(de\002ned) 16 b(here) h(to) h(comp) n(ute) g(the) f(decomp) n
(osition) g(tree.) 24 b(Theref) n(ore) 17 b(one) g(can) h(focu) n(s) g
(on) f(the) h(search) f(of) g(such) g(f) o(actorizin) n(g) 83
4011 y(permu) n(tations.) 166 4114 y(Our) h(central) g(prob) n(lem) h
(is) h(conn) n(ected) e(to) h(the) g(search) f(of) g(the) h(tree) f
(structure) g(in) m(v) n(o) n(lv) o(ed) g(in) h(f) o(actorizin) n(g) g
(permu) n(tation,) 83 4214 y(and) h(therefor) n(e) i(a) f(prob) n(lem) g
(of) g(interest) g(by) f(its) i(o) n(wn.) 27 b(One) 20
b(of) h(the) g(main) g(results) g(of) g(this) g(w) o(ork) f(is) i(to) f
(prop) n(ose) h(a) f(linear) 83 4313 y(algorith) n(m) k(that) f
(applies) h(both) e(for) h(directed) f(or) h(undirec) n(ted) h(grap) n
(hs.) 38 b(Furtherm) n(ore,) 25 b(other) f(grap) n(h) h(deco) n
(mpositions) 83 4413 y(\(for) 19 b(e) o(xamp) n(le) i(those) f
(associated) g(with) g(edge-p) n(artitioning) n(\)) h(can) f(also) g
(be) g(considere) n(d) h(using) e(this) i(appro) n(ach) f([2) o(].) 166
4516 y(Anothe) n(r) j(e) o(xamp) n(le) h(of) e(this) h(parad) n(igm) g
(could) e(be) i(foun) n(d) g(in) g(Hopc) n(roft) g(and) f(T) -7
b(arjan') g(s) 24 b(pioneer) n(ing) f(w) o(ork) n(.) 33
b(Namely) 83 4616 y(their) 26 b(algorith) n(m) h([14) n(]) g(for) e
(triconn) n(ected) h(graph) f(recog) n(nition) h(uses) h(tw) o(o) f
(depth) n(-\002rst) h(searches) f(and) g(collect) g(tricon) n(-) 83
4716 y(nected) 19 b(compo) n(nents) h(by) g(\223f) o(actors\224.) p
90 rotate dyy eop
%%Page: 57 3
57 2 bop FI 83 232 a(Gr) o(aph) 19 b(Decompo) n(sitions) i(and) e(F) -6
b(actorizing) 19 b(P) -7 b(ermutations) p FG 1623 w(57) 166
415 y(This) 25 b(paper) f(is) i(or) o(g) n(anized) e(as) i(follo) n
(ws.) 39 b(The) 24 b(ne) o(xt) h(section) f(presents) h(main) g
(results) g(abou) n(t) h(Modu) n(lar) g(Decom) n(po-) 83
515 y(sition.) 35 b(In) 23 b(Section) h(3) f(we) h(introdu) n(ce) g(a) g
(ne) n(w) f(object,) h(the) f(fracture) g(tree,) h(and) f(present) g
(its) h(prope) n(rties.) 36 b(In) 23 b(Section) g(4) 83
614 y(we) h(pro) n(pose) f(a) h(simple) f(algorith) n(m) h(leading) e
(from) g(the) h(fracture) f(tree) h(to) h(the) f(modu) n(lar) g(decomp)
n(osition) g(tree,) h(and) e(its) 83 714 y(linearity) j(is) i(pro) o(v)
m(en) f(in) g(Section) g(5.) 42 b(In) 26 b(Section) g(6) g(\(Conclu) n
(sion\)) g(se) n(v) o(eral) f(directions) h(for) f(furth) n(er) h
(research) g(and) f(a) 83 814 y(conjectu) n(re) c(are) f(presen) n
(ted.) p Fy 83 1054 a(2) 120 b(Modular) 34 b(decompo) r(sition) p
FG 83 1207 a(The) c(modu) n(lar) h(decomp) n(osition) f(\(also) h
(called) g(substitution) e(decomp) n(osition\)) h(is) i(v) o(ery) d
(importan) n(t) i(since) g(its) h(study) 83 1307 y(plays) 18
b(a) h(centr) n(al) g(role) f(in) g(the) g(area) g(of) g(partial) g
(orde) n(rs,) h(compar) n(ability) f(graph) n(s,) h(and) f(transiti) n
(v) o(e) f(orientation) n(s) i([9) o(].) 25 b(Here) 83
1406 y(we) c(focu) n(s) g(on) f(decom) n(position) g(sets) h(that) f
(are) g(called) g(strong) g(mod) n(ules,) g(which) g(are) g(de\002ned) f
(as) i(follo) n(ws:) p FH 83 1665 a(De\002nition) f(2) p
FI 41 w(T) -6 b(wo) 20 b(set) g(E) 26 b(and) 18 b(F) p
FH 26 w(o) o(v) o(erlap) p FI 19 w(if) i(E) p Fj 16 w(\\) p
FI 11 w(F) p Fj 24 w(6) p Fv(=) p Fx 1755 1663 a(/) 1746
1665 y(0) p FI(,) g(E) p Fj 16 w(n) p FI 11 w(F) p Fj
23 w(6) p Fv(=) p Fx 2114 1663 a(/) 2105 1665 y(0) p
FI(,) g(and) e(F) p Fj 17 w(n) p FI 11 w(E) p Fj 23 w(6) p
Fv(=) p Fx 2618 1663 a(/) 2609 1665 y(0) p FI(.) 24 b(Let) c(G) p
Fv 18 w(=) d(\() p FI(X) p Fw 8 w(;) p FI 9 w(E) p Fv
6 w(\)) p FI 19 w(be) j(a) f(gr) o(ap) n(h) 83 1765 y(with) 24
b(n) f(vertices) h(and) e(m) i(ar) m(cs.) 34 b(The) 24
b(outer) f(neigh) n(borhoo) n(d) g(of) h(v) f(is) h(written) p
Fx 24 w(G) p Fq 2398 1735 a(+) p Fv 2450 1765 a(\() p
FI(v) p Fv(\)) p FI 24 w(and) f(its) h(inner) f(neigh) n(borhoo) n(d) h
(is) p Fx 83 1865 a(G) p Fi 133 1834 a(\000) p Fv 185
1865 a(\() p FI(v) p Fv(\)) p FI(.) i(A) 20 b(subset) h(M) j(of) c(X) 28
b(is) 22 b(a) p FH 20 w(module) p FI 20 w(if) p Fj 21
w(8) p FI(v) p Fj 18 w(2) p FI 19 w(X) p Fj 19 w(n) p
FI 12 w(M) s(,) e(M) k(does) c(not) g(o) o(verlap) f(neither) p
Fx 20 w(G) p Fq 2764 1834 a(+) p Fv 2816 1865 a(\() p
FI(v) p Fv(\)) p FI 21 w(nor) p Fx 20 w(G) p Fi 3124
1834 a(\000) p Fv 3176 1865 a(\() p FI(v) p Fv(\)) p
FI(.) p FG 166 2022 a(Ev) o(ery) 26 b(set) j(with) f(1) g(or) p
FI 28 w(n) p FG 28 w(v) o(er) n(tices) h(is) g(a) p Fm
28 w(trivial) p FG 29 w(modu) n(le.) 49 b(A) 28 b(graph) f(with) h(no) f
(non-) n(tri) n(vial) h(modu) n(le) g(is) p Fm 29 w(prime) p
FG(.) 48 b(A) p Fm 83 2121 a(strong) 25 b(mod) n(ule) p
FG 25 w(is) g(a) f(module) f(that) h(does) g(not) g(o) o(v) o(e) n
(rlap) g(an) o(y) f(other) h(mod) n(ule.) 37 b(The) o(y) 23
b(are) h(the) g(decom) n(position) g(sets) h(of) 83 2221
y(the) d(mod) n(ular) g(deco) n(mposition) n(.) 30 b(In) 21
b(the) h(follo) n(win) n(g) g(a) p Fm 22 w(factorizing) f(permutation) p
FG 21 w(is) i(conside) n(red) f(with) f(respect) h(to) f(the) 83
2321 y(strong) j(modu) n(les.) 40 b(Notice) 25 b(that) g(a) g(gi) n(v) o
(en) f(graph) g(may) g(ha) n(v) o(e) h(man) o(y) e(f) o(actorizing) h
(perm) n(utations,) i(up) e(to) p FI 25 w(n) p FG(!) h(for) f(prime) 83
2420 y(graph) n(s.) 166 2522 y(The) p Fm 23 w(Modula) n(r) g(decom) n
(position) f(tree) p FG 24 w(of) g(a) g(graph) p FI 22
w(G) p FG 23 w(is) h(the) f(transiti) n(v) o(e) f(reductio) n(n) h(of) g
(the) g(inclusion) f(order) g(of) g(the) 83 2622 y(strong) d(modu) n
(les) i(of) p FI 20 w(G) p FG(.) 166 2723 y(Each) c(node) p
FI 16 w(N) p FG 24 w(\() p FI(N) p Fj 21 w(\032) p FI
15 w(X) p FG 26 w(is) h(the) f(strong) g(modu) n(le) h(represen) n(ted)
g(by) f(this) h(nod) n(e\)) g(of) f(the) g(decomp) n(osition) g(tree) h
(is) g(labeled) 83 2823 y(by) k(the) h(quo) n(tient) g(graph) e(of) p
FI 22 w(G) p Ft 973 2835 a(N) p FG 1045 2823 a(accordin) n(g) i(to) f
(its) i(children) n(.) 33 b(Such) 22 b(a) h(quo) n(tient) g(graph) e
(is) j(called) e(the) p Fm 23 w(representativ) o(e) 83
2922 y(graph) p FG 20 w(of) e(the) g(nod) n(e) p FI 21
w(N) p FG 5 w(.) 166 3024 y(F) o(our) f(mutually) g(e) o(xclusi) n(v) o
(e) g(cases) i(can) f(be) g(distinguishe) n(d) h(:) p
Fj 208 3181 a(\017) p FG 41 w(A) f(node) f(is) j(labeled) p
Fm 19 w(series) p FG 22 w(if) e(its) h(represen) n(tati) n(v) o(e) f
(graph) f(is) i(a) g(clique.) p Fj 208 3355 a(\017) p
FG 41 w(A) f(node) f(is) j(labeled) p Fm 19 w(parallel) p
FG 21 w(if) e(its) h(representati) n(v) m(e) g(grap) n(h) f(is) h(a) g
(stable) g(set.) p Fj 208 3529 a(\017) p FG 41 w(A) f(node) f(is) j
(labeled) p Fm 19 w(order) p FG 20 w(if) f(its) g(represen) n(tati) n
(v) o(e) f(graph) f(is) i(a) g(total) f(order) n(ing.) p
Fj 208 3703 a(\017) p FG 41 w(If) h(no) g(one) g(of) h(the) f(pre) n
(viou) n(s) i(cases) f(apply) -7 b(,) 22 b(a) g(node) p
FI 21 w(N) p FG 28 w(is) g(labelled) p Fm 21 w(prime) p
FG(.) 29 b(The) 22 b(repr) n(esentati) n(v) o(e) f(graph) g(of) p
FI 21 w(N) p FG 28 w(is) 291 3802 y(a) f(prime) g(grap) n(h.) 166
3960 y(Let) g(us) h(recall) f(the) g(well-kno) n(w) n(n) h(deco) n
(mposition) e(theorem) g(\(for) g(e) o(xamp) n(le) i(see) g([21) o(]\))
p FH 83 4119 a(Theor) o(em) f(1) g(\(Modular) g(Decomposition\)) p
FI 40 w(Let) k(G) p Fv 20 w(=) 19 b(\() p FI(X) p Fw
8 w(;) p FI 9 w(E) p Fv 6 w(\)) p FI 23 w(be) k(a) g(digr) o(ap) n(h) g
(suc) o(h) g(that) p Fj 22 w(j) p FI(X) p Fj 8 w(j) p
Fh 20 w(>) p FG 19 w(2) p FI(.) 33 b(One) 23 b(of) g(the) g(four) 83
4218 y(following) d(claims) g(is) h(true:) -21 4378 y(1.) 41
b(G) 21 b(is) f(not) g(conn) n(ected) g(and) f(it) i(can) e(be) h
(decompo) n(sed) g(accor) m(din) n(g) g(to) h(its) g(con) n(nected) f
(comp) n(onents.) 25 b(The) 20 b(corr) m(espon) n(ding) 83
4477 y(node) f(in) i(T) p Ft 391 4489 a(G) p FI 460 4477
a(will) g(be) f(a) g(par) o(allel) g(nod) n(e) o(.) -21
4616 y(2.) p 83 4550 60 4 v 41 w(G) k(is) h(not) f(conn) n(ected) g
(and) f(G) h(can) g(be) g(deco) n(mposed) g(acco) n(r) m(ding) g(to) g
(the) g(conn) n(ected) g(compo) n(nents) g(of) p 3099
4550 V 24 w(G.) 37 b(The) 24 b(corr) m(e-) 83 4716 y(spond) n(ing) c
(node) f(in) i(T) p Ft 716 4728 a(G) p FI 785 4716 a(will) g(be) f(a) h
(series) g(node) o(.) p 90 rotate dyy eop
%%Page: 58 4
58 3 bop FG 83 232 a(58) p FI 1403 w(Christian) 21 b(Capelle) o(,) e
(Mic) o(hel) i(Habib) e(and) g(F) -6 b(abien) 19 b(de) h(Montgo) n
(l\002er) -21 415 y(3.) 41 b(G) 22 b(can) f(be) g(decomp) n(osed) h(in)
f(str) l(ong) h(modu) n(les) h(suc) o(h) d(that) i(the) f(quotien) n(t)
h(gr) o(aph) e(is) j(a) e(non-trivia) n(l) i(total) e(or) m(dering) m
(.) 29 b(The) 83 515 y(corr) m(espond) n(ing) 20 b(node) f(in) h(T) p
Ft 892 527 a(G) p FI 962 515 a(will) h(be) f(an) g(or) m(der) g(node) m
(.) -21 661 y(4.) 41 b(Else) o(,) 26 b(the) f(maxima) n(l) g
(non-trivial) f(str) l(ong) g(modules) g(of) h(G) g(do) f(not) g(o) o
(verlap.) 37 b(The) 24 b(quotient) g(gr) o(ap) n(h) h(is) g(prime) g
(and) e(the) 83 760 y(corr) m(espond) n(ing) d(node) f(in) h(T) p
Ft 892 772 a(G) p FI 962 760 a(will) h(be) f(a) g(prime) h(nod) n(e) o
(.) p FG 166 927 a(Ev) o(en) 16 b(thou) n(gh) h(a) g(gi) n(v) o(en) f
(grap) n(h) h(could) f(ha) n(v) o(e) g(e) o(xpo) n(nentially) g(man) o
(y) g(modu) n(les,) i(it) g(has) p FI 17 w(O) p Fv(\() p
FI(n) p Fv(\)) p FG 17 w(strong) e(modu) n(les.) 25 b(Ther) n(e-) 83
1027 y(fore) 19 b(an) i(algor) n(ithm) f(has) h(to) f(deal) g(only) f
(with) i(the) f(good) f(ones,) g(the) i(strong) e(modu) n(les.) 166
1131 y(Let) i(us) h(deno) n(te) g(by) p FI 21 w(L) l(C) r(A) p
Fv(\() p FI(x) p Fw(;) p FI 9 w(y) p Fv(\)) p FG 22 w(the) f(Least) h
(Common) e(Ancestor) g(of) h(the) g(v) o(ertices) p FI
21 w(x) p FG 22 w(and) p FI 20 w(y) p FG 22 w(in) g(the) h(mod) n(ular)
f(decom) n(-) 83 1230 y(position) e(tree.) 25 b(The) 20
b(follo) n(win) n(g) h(pro) n(perty) f(tri) n(vially) f(holds:) p
FH 83 1381 a(Pr) o(opert) n(y) h(1) p FI 91 w(L) l(C) r(A) p
Fv(\() p FI(x) p Fw(;) p FI 9 w(y) p Fv(\)) p FI 22 w(is) h(a) f(ser) r
(ies) i(nod) r(e) p Fj 19 w(\)) p Fv 18 w(\() p FI(x) p
Fw(;) p FI 9 w(y) p Fv(\)) p Fj 19 w(2) p FI 19 w(E) 27
b(and) p Fv 23 w(\() p FI(y) p Fw -5 w(;) p FI 9 w(x) p
Fv(\)) p Fj 20 w(2) p FI 18 w(E) 553 1480 y(L) l(C) r(A) p
Fv(\() p FI(x) p Fw(;) p FI 9 w(y) p Fv(\)) p FI 22 w(is) 21
b(an) f(or) o(d) t(er) i(nod) t(e) p Fj 17 w(\)) p FI
19 w(ei) n(t) 6 b(her) p Fv 22 w(\() p FI(x) p Fw(;) p
FI 9 w(y) p Fv(\)) p Fj 19 w(2) p FI 18 w(E) 27 b(or) p
Fv 22 w(\() p FI(y) p Fw -5 w(;) p FI 9 w(x) p Fv(\)) p
Fj 20 w(2) p FI 19 w(E) 553 1580 y(L) l(C) r(A) p Fv(\() p
FI(x) p Fw(;) p FI 9 w(y) p Fv(\)) p FI 22 w(is) 21 b(a) 26
b(par) q(al) t(l) t(el) e(nod) t(e) p Fj 18 w(\)) p Fv
18 w(\() p FI(x) p Fw(;) p FI 9 w(y) p Fv(\)) p Fw 28
w(=) p Fj -51 w(2) p FI 19 w(E) i(and) p Fv 24 w(\() p
FI(y) p Fw -5 w(;) p FI 9 w(x) p Fv(\)) p Fw 29 w(=) p
Fj -51 w(2) p FI 18 w(E) p FG 166 1721 a(Althoug) n(h) 32
b(linear) g(deco) n(mposition) f(algorith) n(ms) i(are) e(no) n(w) h(a)
n(v) n(ailable) f([4) o(,) i(20) o(,) f(7) o(],) j(the) o(y) c(remain) g
(rather) g(hard) g(to) 83 1821 y(implemen) n(t,) 20 b(and) e(it) i(is) g
(still) h(w) o(orthwh) n(ile) f(to) f(search) g(for) f
(simpli\002cations.) 24 b(The) 19 b(result) g(presented) f(here) h(can)
g(be) g(und) n(er) n(-) 83 1920 y(stood) h(as) h(a) g(step) f(forw) o
(ard) f(in) i(this) g(directio) n(n.) 26 b(Moreo) m(v) o(er) m(,) 19
b(e) o(xisting) h(algorith) n(ms) h(deal) f(only) g(with) g(undirec) n
(ted) h(grap) n(hs,) 83 2020 y(while) k(ours) g(deals) g(with) h(both) e
(directed) g(and) h(und) n(irected) g(grap) n(hs.) 41
b(The) 24 b(ne) o(xt) h(section) g(presen) n(ts) i(an) e(interesting) f
(de-) 83 2119 y(comp) n(osition) c(tool;) g(namely) g(the) g(fractu) n
(re) h(tree.) p Fy 83 2369 a(3) 120 b(The) 34 b(F) -5
b(r) o(acture) 34 b(T) -14 b(ree) p Fg 83 2544 a(3.1) 100
b(Notations) 29 b(and) g(de\002nitions) p FH 83 2694
a(Notat) n(ions) p FG 23 w(In) 21 b(the) h(follo) n(win) n(g,) p
FI 23 w(G) p Fv 19 w(=) d(\() p FI(X) p Fw 8 w(;) p FI
9 w(E) p Fv 6 w(\)) p FG 22 w(is) k(a) f(graph) f(\(dire) n(cted) h(or)
g(not\)) f(with) p FI 22 w(n) p FG 22 w(v) o(ertices) g(and) p
FI 22 w(m) p FG 22 w(arcs,) h(and) p Fx 22 w(s) p Fv(\() p
FI(G) p Fv(\)) p FG 83 2794 a(\(or) p Fx 24 w(s) p FG
26 w(if) j(unam) n(biguo) n(us\)) g(a) g(f) o(actorizing) e(permuta) n
(tion) i(of) p FI 24 w(G) p FG(.) 40 b(The) 24 b(successor) h(of) p
FI 24 w(x) p FG 26 w(in) p Fx 24 w(s) p FG 26 w(is) p
FI 26 w(x) p Fi 2883 2763 a(0) p FG 2929 2794 a(and) f(its) i(prede) n
(cessor) 83 2893 y(is) p Fi 160 2863 a(0) p FI 181 2893
a(x) p FG(.) j(If) p Fx 21 w(s) p Fi 395 2863 a(\000) p
Fr(1) p Fv 478 2893 a(\() p FI(x) p Fv(\)) p Fw 19 w(<) p
Fx 19 w(s) p Fi 732 2863 a(\000) p Fr(1) p Fv 815 2893
a(\() p FI(y) p Fv(\)) p FG 22 w(then) p FI 21 w(x) p
FG 21 w(is) 23 b(to) e(the) g(left) h(of) p FI 21 w(y) p
FG(.) 28 b(If) p FI 21 w(G) p FG 22 w(is) 22 b(undirec) n(ted,) g(it) g
(is) g(treated) f(as) h(a) f(directed) f(symmetric) 83
2993 y(graph) n(,) h(so) f(the) g(same) h(notatio) n(ns) g(are) f(used)
g(for) g(both) f(cases.) p FH 83 3164 a(De\002nition) h(3) p
FI 41 w(Given) i(a) g(set) h(S) p Fj 19 w(\032) p FI
19 w(X) 30 b(of) 22 b(vertices,) h(a) f(verte) n(x) g(x) h(is) f(a) p
FH 22 w(cutter) p FI 22 w(of) g(S) g(if) h(S) f(is) h(not) f(a) f
(module) g(of) h(the) g(induce) n(d) 83 3264 y(gr) o(aph) 28
b(G) p Fv(\() p FI(S) p Fj 15 w([) 15 b(f) p FI(x) p
Fj(g) p Fv(\)) p FI(.) 53 b(This) 30 b(mean) n(s) h(that) e(x) p
Fw 32 w(=) p Fj -51 w(2) p FI 24 w(S) h(and) e(that) i(at) f(least) h
(two) g(vertices) g(of) f(S) h(have) f(dif) o(fer) m(en) n(t) h
(adjacen) n(cy) 83 3363 y(r) m(elations) 20 b(with) h(x.) k(The) c(set)
g(of) f(cutter) o(s) h(of) f(S) h(is) g(denoted) e(by) d(C) r(u) n(t) p
Fv 6 w(\() p FI(S) p Fv 1 w(\)) p FI(.) p FG 166 3530
a(Of) k(course) p FI 20 w(M) p FG 24 w(is) h(a) g(mod) n(ule) g(if) f
(and) g(only) f(if) p FI 17 w(C) r(u) n(t) p Fv 6 w(\() p
FI(M) p Fv 3 w(\)) f(=) p Fx 1829 3528 a(/) 1820 3530
y(0) p FG(.) 25 b(Furtherm) n(ore) 20 b(we) g(ha) n(v) o(e) p
FH 83 3680 a(Pr) o(opert) n(y) g(2) p FI 41 w(let) h(M) j(be) d(a) f
(modu) n(le) h(and) e(S) i(a) g(subset) f(of) g(M) s(,) h(then) 16
b(C) r(u) n(t) p Fv 6 w(\() p FI(S) p Fv 1 w(\)) p Fj
17 w(\032) p FI 18 w(M) s(.) p FG 166 3826 a(Since) p
Fx 21 w(s) p FG 22 w(is) 23 b(supp) n(osed) f(to) f(be) g(a) h(f) o
(actorizin) n(g) g(perm) n(utation,) f(the) g(strong) g(mod) n(ules) h
(are) f(f) o(actors) g(of) g(it,) i(so) e(the) h(cutters) 83
3926 y(\224gath) n(er) i(togeth) n(er\224) f(in) h(the) f(vicinity) g
(of) g(an) o(y) f(f) o(actor) p FI 23 w(S) p FG 1 w(,) h(in) h(a) f
(manner) f(sho) n(wn) h(belo) l(w) -5 b(.) 35 b(In) 23
b(ord) n(er) h(to) f(reach) f(linear) h(time) 83 4026
y(for) f(our) g(algorithm) n(,) i(the) f(only) f(subsets) h(we) g(deal)
g(with) g(are) g(the) p Fm 23 w(pairs) p FG(,) g(made) f(up) h(with) g
(tw) o(o) p FI 23 w(consecu) n(tive) p FG 23 w(v) o(ertices) g(of) p
Fx 83 4125 a(s) p FG(.) j(F) o(ortun) n(ately) 21 b(there) f(is) h(no) f
(need) g(of) g(comp) n(uting) g(the) g(set) i(of) e(all) h(cutters) f
(of) g(a) h(gi) n(v) o(e) n(n) g(pair:) k(it) c(is) h(enou) n(gh) e(to)
h(consid) n(er) 83 4225 y(the) f(furthe) n(st) i(one) n(s.) p
FH 83 4396 a(De\002nition) e(4) p FI 41 w(Let) i(P) p
Fv 18 w(=) p Fj 18 w(f) p FI(x) p Fw(;) p FI 9 w(x) p
Fi 965 4366 a(0) p Fj 986 4396 a(g) p FI 21 w(be) e(a) h(pair) f(of) h
(vertices.) 27 b(The) p FH 20 w(\002rst) 21 b(cutter) p
FI 21 w(of) f(P,) h(deno) n(ted) g(by) 32 b(f) 12 b(c) p
Fv(\() p FI(P) p Fv(\)) p FI(,) 22 b(is) f(the) g(leftmost) 83
4496 y(verte) n(x) i(of) c(C) r(u) n(t) p Fv 6 w(\() p
FI(P) p Fv(\)) p FI 22 w(\(if) k(any\)) f(app) n(earing) g(in) h(the) f
(factor) p Fx 23 w(s) p Fv(\() p FG(1) p Fv(\)) p Fw
9 w(:) 9 b(:) g(:) p FI 10 w(x.) 32 b(If) 23 b(suc) o(h) f(a) h(verte) n
(x) g(e) n(xists,) h(the) p FH 23 w(left) e(fract) n(ur) o(e) p
FI 23 w(of) g(P,) 83 4595 y(deno) n(ted) h(by) f(L) 12
b(f) p Fv 12 w(\() p FI(P) p Fv(\)) p FI(,) 24 b(is) g(the) e(factor) 34
b(f) 12 b(c) p Fv(\() p FI(P) p Fv(\)) p Fw 9 w(:) d(:) g(:) p
FI 11 w(x.) 32 b(The) p FH 22 w(last) 23 b(cutter) p
FI 21 w(of) g(P,) g(l) t(c) p Fv(\() p FI(P) p Fv(\)) p
FI(,) g(is) h(the) e(rightmost) g(verte) n(x) h(of) c(C) r(u) n(t) p
Fv 6 w(\() p FI(P) p Fv -2 w(\)) p FI 83 4695 a(appe) n(aring) h(in) g
(x) p Fi 567 4665 a(0) p Fw 598 4695 a(:) 9 b(:) g(:) p
Fx 9 w(s) p Fv(\() p FI(n) p Fv(\)) p FI 21 w(and) 20
b(the) p FH 20 w(right) g(fract) n(ur) o(e) p FI(,) g(R) 12
b(f) p Fv 12 w(\() p FI(P) p Fv(\)) p FI(,) 21 b(is) g(the) g(factor) f
(x) p Fi 2375 4665 a(0) p Fw 2405 4695 a(:) 9 b(:) g(:) p
FI 10 w(l) t(c) p Fv(\() p FI(P) p Fv(\)) p FI(.) p 90 rotate
dyy eop
%%Page: 59 5
59 4 bop FI 83 232 a(Gr) o(aph) 19 b(Decompo) n(sitions) i(and) e(F) -6
b(actorizing) 19 b(P) -7 b(ermutations) p FG 1623 w(59) 257
1973 y @beginspecial 0 @llx 0 @lly 273 @urx 121 @ury
3765 @rwi @setspecial
%%BeginDocument: graphe.eps
%!PS-Adobe-2.0 EPSF-2.0
%%Title: graphe.eps
%%Creator: fig2dev Version 3.2 Patchlevel 3a
%%CreationDate: Wed Jul 5 17:43:34 2000
%%For: montgolfier@jujube (Fabien de MONTGOLFIER,,,Habib,DEA2000,20000930)
%%BoundingBox: 0 0 273 121
%%Magnification: 1.0000
%%EndComments
/$F2psDict 200 dict def
$F2psDict begin
$F2psDict /mtrx matrix put
/col-1 {0 setgray} bind def
/col0 {0.000 0.000 0.000 srgb} bind def
/col1 {0.000 0.000 1.000 srgb} bind def
/col2 {0.000 1.000 0.000 srgb} bind def
/col3 {0.000 1.000 1.000 srgb} bind def
/col4 {1.000 0.000 0.000 srgb} bind def
/col5 {1.000 0.000 1.000 srgb} bind def
/col6 {1.000 1.000 0.000 srgb} bind def
/col7 {1.000 1.000 1.000 srgb} bind def
/col8 {0.000 0.000 0.560 srgb} bind def
/col9 {0.000 0.000 0.690 srgb} bind def
/col10 {0.000 0.000 0.820 srgb} bind def
/col11 {0.530 0.810 1.000 srgb} bind def
/col12 {0.000 0.560 0.000 srgb} bind def
/col13 {0.000 0.690 0.000 srgb} bind def
/col14 {0.000 0.820 0.000 srgb} bind def
/col15 {0.000 0.560 0.560 srgb} bind def
/col16 {0.000 0.690 0.690 srgb} bind def
/col17 {0.000 0.820 0.820 srgb} bind def
/col18 {0.560 0.000 0.000 srgb} bind def
/col19 {0.690 0.000 0.000 srgb} bind def
/col20 {0.820 0.000 0.000 srgb} bind def
/col21 {0.560 0.000 0.560 srgb} bind def
/col22 {0.690 0.000 0.690 srgb} bind def
/col23 {0.820 0.000 0.820 srgb} bind def
/col24 {0.500 0.190 0.000 srgb} bind def