38:
687:, and it can be used to partition the edges into equivalence classes, subsets of edges with the property that two edges are related to each other if and only if they belong to the same equivalence class. The subgraphs formed by the edges in each equivalence class are the biconnected components of the given graph. Thus, the biconnected components partition the edges of the graph; however, they may share vertices with each other.
771:
378:
283:
The root vertex must be handled separately: it is a cut vertex if and only if it has at least two children in the DFS tree. Thus, it suffices to simply build one component out of each child subtree of the root (including the root).
767:. This tree has a vertex for each block and for each articulation point of the given graph. There is an edge in the block-cut tree for each pair of a block and an articulation point that belongs to that block.
969:
503:
version of the problem, vertices and edges are added (but not removed) dynamically, and a data structure must maintain the biconnected components.
41:
Each color corresponds to a biconnected component. Multi-colored vertices are cut vertices, and thus belong to multiple biconnected components.
942:
260:
separates the graph into different biconnected components. This can be represented by computing one biconnected component out of every such
755:
is a vertex that is shared by two or more blocks. The structure of the blocks and cutpoints of a connected graph can be described by a
101:
568:
324:
parent := i GetArticulationPoints(ni, d + 1) childCount := childCount + 1
1222:
512:
69:
550:
198:
150:
1085:
913:
65:
224:
is a cut vertex (or articulation point) separating two biconnected components if and only if there is a child
451:. This gives immediately a linear-time 2-connectivity test and can be extended to list all cut vertices of
1093:
903:
1056:
Westbrook, J.; Tarjan, R. E. (1992). "Maintaining bridge-connected and biconnected components on-line".
908:
468:
431:
411:
109:
81:
1171:
504:
1016:
684:
444:
126:
1098:
756:
656:
403:
373:
Note that the terms child and parent denote the relations in the DFS tree, not the original graph.
73:
1028:
963:
711:, and an edge between two vertices whenever the corresponding two blocks share a vertex. A graph
704:
564:
407:
146:
37:
948:
938:
62:
1187:
1103:
1065:
1038:
996:
500:
130:
606:
142:
1207:
244:. This property can be tested once the depth-first search returned from every child of
299:
depth := d low := d childCount := 0 isArticulation :=
1216:
957:
A cut-vertex is a vertex that if removed, the number of network components increases.
560:
508:
156:
The idea is to run a depth-first search while maintaining the following information:
138:
134:
1137:
628:
160:
the depth of each vertex in the depth-first-search tree (once it gets visited), and
46:
1083:
Tarjan, R.; Vishkin, U. (1985). "An
Efficient Parallel Biconnectivity Algorithm".
728:
556:
377:
185:
The depth is standard to maintain during a depth-first search. The lowpoint of
1042:
952:
770:
31:
609:
on the edges of an arbitrary undirected graph, according to which two edges
1001:
984:
17:
511:(1992) developed an efficient data structure for this problem based on
1069:
675:, then one can combine these two cycles to find a simple cycle through
1192:
1175:
933:
AL-TAIE, MOHAMMED ZUHAIR. KADRY, SEIFEDINE (2019). "3. Graph Theory".
1107:
410:-trees. Chain decompositions can be computed in linear time by this
213:
in the depth-first-search tree) and the lowpoint of all children of
1127:; however, Harary does not appear to describe it in explicit terms.
1033:
769:
36:
1019:(2013), "A Simple Test on 2-Vertex- and 2-Edge-Connectivity",
80:
of the graph. The blocks are attached to each other at shared
985:"Algorithm 447: efficient algorithms for graph manipulation"
916:
Counter part of biconnected components in directed graphs
707:
of its blocks. Thus, it has one vertex for each block of
104:. A block containing at most one cut vertex is called a
463:(with minimum degree 2) is a cut vertex if and only if
455:
in linear time using the following statement: A vertex
1123:
credit the definition of this equivalence relation to
252:
gets popped off the depth-first-search stack), and if
167:, the lowest depth of neighbors of all descendants of
1176:"A Sufficient Condition for Backtrack-Bounded Search"
488:. The list of cut vertices can be used to create the
149:. This algorithm is also outlined as Problem 22-2 of
406:, which are special ear decompositions depending on
129:
for computing biconnected components in a connected
100:
is any vertex whose removal increases the number of
381:A demo of Tarjan's algorithm to find cut vertices.
175:itself) in the depth-first-search tree, called the
1180:Journal of the Association for Computing Machinery
659:: if there exists a simple cycle containing edges
189:can be computed after visiting all descendants of
402:A simple alternative to the above algorithm uses
639:. Every edge is related to itself, and an edge
1120:
8:
1208:C++ implementation of Biconnected Components
968:: CS1 maint: multiple names: authors list (
667:, and another simple cycle containing edges
553:. This time bound is proved to be optimal.
1191:
1097:
1032:
1000:
376:
925:
197:gets popped off the depth-first-search
1155:
1124:
961:
220:The key fact is that a nonroot vertex
935:PYTHON FOR GRAPH AND NETWORK ANALYSIS
426:is 2-vertex-connected if and only if
76:of biconnected components called the
7:
727:with this property are known as the
715:is the block graph of another graph
723:are complete subgraphs. The graphs
489:
336:low := Min (low, low)
276:), and then erasing the subtree of
617:are related if and only if either
475:is the first vertex of a cycle in
25:
983:Hopcroft, J.; Tarjan, R. (1973).
344:low := Min (low, depth)
201:) as the minimum of the depth of
774:A graph, and its block-cut tree.
217:in the depth-first-search tree.
205:, the depth of all neighbors of
719:exactly when all the blocks of
370:Output i as articulation point
1021:Information Processing Letters
651:is related in the same way to
515:. Specifically, it processes
121:Linear time depth-first search
1:
153:(both 2nd and 3rd editions).
1144:, Addison-Wesley, p. 29
655:. Less obviously, this is a
513:disjoint-set data structures
418:be a chain decomposition of
268:will contain the subtree of
264:(a component which contains
27:Maximal biconnected subgraph
1121:Tarjan & Vishkin (1985)
643:is related to another edge
293:GetArticulationPoints(i, d)
1239:
551:inverse Ackermann function
209:(other than the parent of
151:Introduction to Algorithms
29:
1043:10.1016/j.ipl.2013.01.016
989:Communications of the ACM
914:Single-entry single-exit
683:. Therefore, this is an
627:or the graph contains a
30:Not to be confused with
332:isArticulation :=
112:in the block-cut tree.
904:Triconnected component
894:
390:
108:, it corresponds to a
57:(sometimes known as a
42:
1002:10.1145/362248.362272
909:Bridge (graph theory)
773:
519:vertex additions and
459:in a connected graph
380:
59:2-connected component
51:biconnected component
40:
685:equivalence relation
601:Equivalence relation
404:chain decompositions
127:sequential algorithm
102:connected components
657:transitive relation
563:(1985) designed a
366:childCount > 1)
248:(i.e., just before
193:(i.e., just before
141:(1973). It runs in
96:. Specifically, a
94:articulation points
90:separating vertices
1223:Graph connectivity
1070:10.1007/BF01758773
895:
749:articulation point
705:intersection graph
596:Related structures
565:parallel algorithm
545:total time, where
523:edge additions in
391:
385:denotes depth and
147:depth-first search
145:, and is based on
72:decomposes into a
43:
1193:10.1145/4221.4225
1172:Eugene C. Freuder
944:978-3-319-85037-5
699:of a given graph
605:One can define a
505:Jeffery Westbrook
467:is incident to a
389:denotes lowpoint.
16:(Redirected from
1230:
1197:
1195:
1159:
1153:
1147:
1145:
1134:
1128:
1118:
1112:
1111:
1101:
1080:
1074:
1073:
1064:(1–6): 433–464.
1053:
1047:
1045:
1036:
1017:Schmidt, Jens M.
1013:
1007:
1006:
1004:
980:
974:
973:
967:
959:
930:
893:
883:
873:
863:
849:
839:
829:
819:
809:
799:
789:
754:
726:
722:
718:
714:
710:
702:
682:
678:
674:
670:
666:
662:
654:
650:
646:
642:
638:
634:
626:
616:
612:
591:
581:
548:
544:
522:
518:
496:in linear time.
495:
487:
474:
466:
462:
458:
454:
450:
442:
429:
425:
421:
417:
398:Other algorithms
355:isArticulation)
295:visited :=
279:
275:
271:
267:
263:
259:
251:
247:
243:
231:
227:
223:
216:
212:
208:
204:
196:
192:
188:
180:
174:
170:
166:
163:for each vertex
131:undirected graph
21:
1238:
1237:
1233:
1232:
1231:
1229:
1228:
1227:
1213:
1212:
1204:
1170:
1167:
1162:
1154:
1150:
1136:
1135:
1131:
1119:
1115:
1108:10.1137/0214061
1099:10.1.1.465.8898
1086:SIAM J. Comput.
1082:
1081:
1077:
1055:
1054:
1050:
1015:
1014:
1010:
982:
981:
977:
960:
945:
932:
931:
927:
923:
900:
891:
885:
884:
881:
875:
874:
871:
865:
864:
861:
855:
854:
850:
847:
841:
840:
837:
831:
830:
827:
821:
820:
817:
811:
810:
807:
801:
800:
797:
791:
790:
787:
781:
780:
775:
752:
737:
724:
720:
716:
712:
708:
700:
693:
680:
676:
672:
668:
664:
660:
652:
648:
647:if and only if
644:
640:
636:
632:
618:
614:
610:
607:binary relation
603:
598:
583:
572:
546:
524:
520:
516:
493:
486:
476:
472:
464:
460:
456:
452:
448:
441:
435:
427:
423:
419:
415:
412:traversing rule
400:
394:
392:
371:
290:
280:from the tree.
277:
273:
269:
265:
261:
257:
249:
245:
233:
229:
225:
221:
214:
210:
206:
202:
194:
190:
186:
176:
172:
168:
164:
123:
118:
70:connected graph
61:) is a maximal
35:
28:
23:
22:
15:
12:
11:
5:
1236:
1234:
1226:
1225:
1215:
1214:
1211:
1210:
1203:
1202:External links
1200:
1199:
1198:
1186:(4): 755–761.
1166:
1163:
1161:
1160:
1148:
1129:
1113:
1092:(4): 862–874.
1075:
1048:
1027:(7): 241–244,
1008:
995:(6): 372–378.
975:
943:
924:
922:
919:
918:
917:
911:
906:
899:
896:
889:
879:
869:
859:
845:
835:
825:
815:
805:
795:
785:
761:block-cut tree
736:
735:Block-cut tree
733:
692:
689:
602:
599:
597:
594:
490:block-cut tree
484:
439:
399:
396:
375:
291:
289:
286:
183:
182:
161:
122:
119:
117:
114:
78:block-cut tree
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1235:
1224:
1221:
1220:
1218:
1209:
1206:
1205:
1201:
1194:
1189:
1185:
1181:
1177:
1173:
1169:
1168:
1164:
1158:, p. 36.
1157:
1156:Harary (1969)
1152:
1149:
1143:
1139:
1138:Harary, Frank
1133:
1130:
1126:
1125:Harary (1969)
1122:
1117:
1114:
1109:
1105:
1100:
1095:
1091:
1088:
1087:
1079:
1076:
1071:
1067:
1063:
1059:
1052:
1049:
1044:
1040:
1035:
1030:
1026:
1022:
1018:
1012:
1009:
1003:
998:
994:
990:
986:
979:
976:
971:
965:
958:
954:
950:
946:
940:
936:
929:
926:
920:
915:
912:
910:
907:
905:
902:
901:
897:
888:
878:
868:
858:
853:
844:
834:
824:
814:
804:
794:
784:
778:
772:
768:
766:
762:
758:
750:
746:
742:
734:
732:
730:
706:
698:
690:
688:
686:
658:
631:through both
630:
625:
621:
608:
600:
595:
593:
590:
586:
579:
575:
571:that runs in
570:
566:
562:
561:Robert Tarjan
558:
554:
552:
542:
538:
534:
531:
527:
514:
510:
509:Robert Tarjan
506:
502:
497:
491:
483:
479:
470:
446:
438:
433:
413:
409:
405:
397:
395:
388:
384:
379:
374:
369:
365:
362:
358:
354:
351:
347:
343:
339:
335:
331:
327:
323:
319:
316:
313:
309:
305:
302:
298:
294:
287:
285:
281:
255:
241:
237:
218:
200:
179:
162:
159:
158:
157:
154:
152:
148:
144:
140:
139:Robert Tarjan
136:
135:John Hopcroft
132:
128:
120:
115:
113:
111:
107:
103:
99:
95:
91:
87:
83:
79:
75:
71:
67:
64:
60:
56:
52:
48:
39:
33:
19:
1183:
1179:
1151:
1142:Graph Theory
1141:
1132:
1116:
1089:
1084:
1078:
1061:
1058:Algorithmica
1057:
1051:
1024:
1020:
1011:
992:
988:
978:
956:
937:. SPRINGER.
934:
928:
886:
876:
866:
856:
851:
842:
832:
822:
812:
802:
792:
782:
776:
764:
760:
748:
744:
740:
738:
729:block graphs
696:
694:
629:simple cycle
623:
619:
604:
592:processors.
588:
584:
577:
573:
555:
540:
536:
532:
529:
525:
498:
481:
477:
443:is the only
436:
430:has minimum
401:
393:
386:
382:
372:
367:
363:
360:
356:
352:
349:
345:
341:
340:ni ≠ parent
337:
333:
329:
328:low ≥ depth
325:
321:
317:
314:
311:
307:
303:
300:
296:
292:
282:
253:
239:
235:
219:
184:
177:
155:
125:The classic
124:
105:
97:
93:
89:
86:cut vertices
85:
77:
58:
54:
50:
47:graph theory
44:
759:called the
751:of a graph
697:block graph
691:Block graph
557:Uzi Vishkin
171:(including
143:linear time
110:leaf vertex
63:biconnected
1165:References
953:1047552679
852:Cutpoints:
745:cut vertex
582:time with
359:(parent =
348:(parent ≠
288:Pseudocode
238:) ≥ depth(
232:such that
133:is due to
116:Algorithms
106:leaf block
98:cut vertex
32:vertex cut
18:Cut vertex
1094:CiteSeerX
1034:1209.0700
964:cite book
234:lowpoint(
1217:Category
1174:(1985).
1140:(1969),
898:See also
741:cutpoint
567:on CRCW
320:visited
304:for each
178:lowpoint
82:vertices
66:subgraph
765:BC-tree
703:is the
549:is the
499:In the
422:. Then
338:else if
272:, plus
84:called
68:. Any
1096:
951:
941:
777:Blocks
501:online
469:bridge
434:2 and
432:degree
414:. Let
1029:arXiv
921:Notes
747:, or
576:(log
445:cycle
301:false
199:stack
55:block
970:link
949:OCLC
939:ISBN
892:= 10
757:tree
695:The
679:and
671:and
663:and
635:and
613:and
569:PRAM
559:and
507:and
368:then
361:null
350:null
342:then
334:true
330:then
322:then
310:adj
297:true
254:true
137:and
74:tree
49:, a
1188:doi
1104:doi
1066:doi
1039:doi
1025:113
997:doi
882:= 8
872:= 7
862:= 2
763:or
492:of
471:or
447:in
408:DFS
364:and
353:and
318:not
306:ni
228:of
92:or
88:or
53:or
45:In
1219::
1184:32
1182:.
1178:.
1102:.
1090:14
1060:.
1037:,
1023:,
993:16
991:.
987:.
966:}}
962:{{
955:.
947:.
848:=
838:=
828:=
818:=
808:=
798:=
788:=
779::
743:,
739:A
731:.
622:=
587:+
543:))
539:,
480:–
357:or
346:if
326:if
315:if
312:do
308:in
256:,
1196:.
1190::
1146:.
1110:.
1106::
1072:.
1068::
1062:7
1046:.
1041::
1031::
1005:.
999::
972:)
890:4
887:c
880:3
877:c
870:2
867:c
860:1
857:c
846:7
843:b
836:6
833:b
826:5
823:b
816:4
813:b
806:3
803:b
796:2
793:b
786:1
783:b
753:G
725:H
721:H
717:G
713:H
709:G
701:G
681:g
677:e
673:g
669:f
665:f
661:e
653:e
649:f
645:f
641:e
637:f
633:e
624:f
620:e
615:f
611:e
589:m
585:n
580:)
578:n
574:O
547:α
541:n
537:m
535:(
533:α
530:m
528:(
526:O
521:m
517:n
494:G
485:1
482:C
478:C
473:v
465:v
461:G
457:v
453:G
449:C
440:1
437:C
428:G
424:G
420:G
416:C
387:L
383:D
278:y
274:v
270:y
266:y
262:y
258:v
250:v
246:v
242:)
240:v
236:y
230:v
226:y
222:v
215:v
211:v
207:v
203:v
195:v
191:v
187:v
181:.
173:v
169:v
165:v
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
