36:
28:
763:) where the vertices in each level are visited in order of their predecessor's numbering from lowest to highest. Where the predecessors are the same, vertices are distinguished by degree (again ordered from lowest to highest).
664:
439:
398:
288:
475:
167:
200:
729:
695:
559:
532:
505:
254:
227:
126:
749:
603:
583:
360:
329:
87:) due to Alan George and Joseph Liu is the same algorithm but with the resulting index numbers reversed. In practice this generally results in less
802:
869:
611:
697:
ascending by minimum predecessor (the already-visited neighbor with the earliest position in R), and as a tiebreak ascending by
295:
847:
898:
76:
857:
903:
828:
J. A. George and J. W-H. Liu, Computer
Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981
815:
44:
893:
851:
698:
339:
299:
838:
760:
95:
406:
365:
267:
17:
444:
335:
131:
56:
172:
291:
68:
707:
673:
537:
510:
483:
232:
205:
104:
772:
756:
99:
816:"Ciprian Zavoianu - weblog: Tutorial: Bandwidth reduction - The CutHill-McKee Algorithm"
98:
algorithm used in graph algorithms. It starts with a peripheral node and then generates
863:
734:
588:
568:
345:
314:
887:
777:
88:
64:
72:
796:
60:
306:
35:
27:
877:
873:
34:
26:
256:. These nodes are ordered according to predecessors and degree.
755:
In other words, number the vertices according to a particular
302:
of the graph to reduce the bandwidth of the adjacency matrix.
659:{\displaystyle A_{i}:=\operatorname {Adj} (R_{i})\setminus R}
91:
than the CM ordering when
Gaussian elimination is applied.
837:
The
Reverse Cuthill-McKee Algorithm in Distributed-Memory
298:. The Cuthill–McKee algorithm is then a relabeling of the
94:
The
Cuthill McKee algorithm is a variant of the standard
858:
A detailed description of the
Cuthill–McKee algorithm
737:
710:
676:
614:
591:
571:
540:
513:
486:
447:
409:
368:
348:
317:
270:
235:
208:
175:
134:
107:
331:
of vertices which is the new order of the vertices.
798:
Reducing the bandwidth of sparse symmetric matrices
743:
723:
689:
658:
597:
577:
553:
526:
499:
469:
433:
392:
354:
323:
282:
248:
221:
194:
161:
120:
229:by listing all vertices adjacent to all nodes in
585:) and exclude the vertices we already have in
8:
384:
378:
736:
715:
709:
681:
675:
641:
619:
613:
590:
570:
545:
539:
518:
512:
491:
485:
456:
448:
446:
408:
367:
347:
316:
269:
240:
234:
213:
207:
180:
174:
133:
112:
106:
788:
650:
169:until all nodes are exhausted. The set
290:matrix we visualize the matrix as the
441:we iterate the following steps while
7:
305:The algorithm produces an ordered
31:Cuthill-McKee ordering of a matrix
25:
866:MATLAB's implementation of RCM.
81:reverse Cuthill–McKee algorithm
39:RCM ordering of the same matrix
18:Reverse Cuthill–McKee algorithm
647:
634:
457:
449:
387:
375:
1:
480:Construct the adjacency set
434:{\displaystyle i=1,2,\dots }
338:(the vertex with the lowest
848:Cuthill–McKee documentation
920:
393:{\displaystyle R:=(\{x\})}
71:sparsity pattern into a
801:In Proc. 24th Nat. Conf.
795:E. Cuthill and J. McKee.
283:{\displaystyle n\times n}
470:{\displaystyle |R|<n}
162:{\displaystyle i=1,2,..}
45:numerical linear algebra
195:{\displaystyle R_{i+1}}
59:and James McKee, is an
49:Cuthill–McKee algorithm
805:, pages 157–172, 1969.
745:
725:
691:
660:
599:
579:
555:
528:
501:
471:
435:
394:
356:
325:
284:
250:
223:
196:
163:
122:
40:
32:
870:reverse_cuthill_mckee
746:
726:
724:{\displaystyle A_{i}}
692:
690:{\displaystyle A_{i}}
661:
600:
580:
556:
554:{\displaystyle R_{i}}
529:
527:{\displaystyle R_{i}}
502:
500:{\displaystyle A_{i}}
472:
436:
395:
357:
326:
285:
251:
249:{\displaystyle R_{i}}
224:
222:{\displaystyle R_{i}}
197:
164:
123:
121:{\displaystyle R_{i}}
38:
30:
761:breadth-first search
735:
708:
674:
612:
589:
569:
538:
511:
484:
445:
407:
366:
346:
315:
268:
233:
206:
202:is created from set
173:
132:
105:
96:breadth-first search
852:Boost C++ Libraries
741:
731:to the Result set
721:
687:
656:
595:
575:
551:
524:
497:
467:
431:
390:
352:
334:First we choose a
321:
280:
264:Given a symmetric
246:
219:
192:
159:
118:
75:form with a small
41:
33:
872:RCM routine from
744:{\displaystyle R}
598:{\displaystyle R}
578:{\displaystyle R}
565:-th component of
355:{\displaystyle x}
336:peripheral vertex
324:{\displaystyle R}
57:Elizabeth Cuthill
16:(Redirected from
911:
899:Graph algorithms
841:
835:
829:
826:
820:
819:
812:
806:
793:
750:
748:
747:
742:
730:
728:
727:
722:
720:
719:
696:
694:
693:
688:
686:
685:
665:
663:
662:
657:
646:
645:
624:
623:
604:
602:
601:
596:
584:
582:
581:
576:
560:
558:
557:
552:
550:
549:
533:
531:
530:
525:
523:
522:
506:
504:
503:
498:
496:
495:
476:
474:
473:
468:
460:
452:
440:
438:
437:
432:
399:
397:
396:
391:
361:
359:
358:
353:
330:
328:
327:
322:
292:adjacency matrix
289:
287:
286:
281:
255:
253:
252:
247:
245:
244:
228:
226:
225:
220:
218:
217:
201:
199:
198:
193:
191:
190:
168:
166:
165:
160:
127:
125:
124:
119:
117:
116:
21:
919:
918:
914:
913:
912:
910:
909:
908:
904:Sparse matrices
884:
883:
844:
840:, slide 8, 2016
836:
832:
827:
823:
814:
813:
809:
794:
790:
786:
773:Graph bandwidth
769:
757:level structure
733:
732:
711:
706:
705:
677:
672:
671:
637:
615:
610:
609:
587:
586:
567:
566:
541:
536:
535:
514:
509:
508:
487:
482:
481:
443:
442:
405:
404:
364:
363:
344:
343:
313:
312:
266:
265:
262:
236:
231:
230:
209:
204:
203:
176:
171:
170:
130:
129:
108:
103:
102:
55:), named after
23:
22:
15:
12:
11:
5:
917:
915:
907:
906:
901:
896:
886:
885:
882:
881:
867:
861:
855:
843:
842:
830:
821:
807:
787:
785:
782:
781:
780:
775:
768:
765:
753:
752:
740:
718:
714:
702:
684:
680:
667:
666:
655:
652:
649:
644:
640:
636:
633:
630:
627:
622:
618:
606:
605:
594:
574:
548:
544:
521:
517:
494:
490:
466:
463:
459:
455:
451:
430:
427:
424:
421:
418:
415:
412:
389:
386:
383:
380:
377:
374:
371:
351:
320:
279:
276:
273:
261:
258:
243:
239:
216:
212:
189:
186:
183:
179:
158:
155:
152:
149:
146:
143:
140:
137:
115:
111:
24:
14:
13:
10:
9:
6:
4:
3:
2:
916:
905:
902:
900:
897:
895:
894:Matrix theory
892:
891:
889:
879:
875:
871:
868:
865:
862:
859:
856:
853:
849:
846:
845:
839:
834:
831:
825:
822:
817:
811:
808:
804:
800:
799:
792:
789:
783:
779:
778:Sparse matrix
776:
774:
771:
770:
766:
764:
762:
759:(computed by
758:
738:
716:
712:
703:
700:
699:vertex degree
682:
678:
669:
668:
653:
642:
638:
631:
628:
625:
620:
616:
608:
607:
592:
572:
564:
546:
542:
519:
515:
492:
488:
479:
478:
477:
464:
461:
453:
428:
425:
422:
419:
416:
413:
410:
401:
381:
372:
369:
349:
341:
337:
332:
318:
311:
309:
303:
301:
297:
293:
277:
274:
271:
259:
257:
241:
237:
214:
210:
187:
184:
181:
177:
156:
153:
150:
147:
144:
141:
138:
135:
113:
109:
101:
97:
92:
90:
86:
82:
78:
74:
70:
66:
65:sparse matrix
63:to permute a
62:
58:
54:
50:
46:
37:
29:
19:
833:
824:
810:
797:
791:
754:
562:
402:
333:
307:
304:
263:
93:
84:
80:
52:
48:
42:
876:written in
73:band matrix
67:that has a
888:Categories
784:References
651:∖
632:
429:…
403:Then for
275:×
260:Algorithm
77:bandwidth
69:symmetric
61:algorithm
850:for the
767:See also
362:and set
300:vertices
704:Append
89:fill-in
878:Cython
864:symrcm
534:(with
340:degree
310:-tuple
100:levels
79:. The
47:, the
874:SciPy
670:Sort
296:graph
294:of a
561:the
462:<
128:for
803:ACM
629:Adj
507:of
85:RCM
43:In
890::
626::=
400:.
373::=
342:)
53:CM
880:.
860:.
854:.
818:.
751:.
739:R
717:i
713:A
701:.
683:i
679:A
654:R
648:)
643:i
639:R
635:(
621:i
617:A
593:R
573:R
563:i
547:i
543:R
520:i
516:R
493:i
489:A
465:n
458:|
454:R
450:|
426:,
423:2
420:,
417:1
414:=
411:i
388:)
385:}
382:x
379:{
376:(
370:R
350:x
319:R
308:n
278:n
272:n
242:i
238:R
215:i
211:R
188:1
185:+
182:i
178:R
157:.
154:.
151:,
148:2
145:,
142:1
139:=
136:i
114:i
110:R
83:(
51:(
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
