531:
29:
715:
727:
Computing the strength of a graph can be done in polynomial time, and the first such algorithm was discovered by
Cunningham (1985). The algorithm with best complexity for computing exactly the strength is due to Trubin (1993), uses the flow decomposition of Goldberg and Rao (1998), in time
360:
318:
548:
831:
526:{\displaystyle \sigma (G)=\max \left\{\sum _{T\in {\mathcal {T}}}\lambda _{T}\ :\ \forall T\in {\mathcal {T}}\ \lambda _{T}\geq 0{\mbox{ and }}\forall e\in E\ \sum _{T\ni e}\lambda _{T}\leq 1\right\}.}
1072:
898:
1110:
942:
345:
990:
199:
225:
113:
710:{\displaystyle \sigma (G)=\min \left\{\sum _{e\in E}y_{e}\ :\ \forall e\in E\ y_{e}\geq 0{\mbox{ and }}\forall T\in {\mathcal {T}}\ \sum _{e\in E}y_{e}\geq 1\right\}.}
230:
1021:
152:
176:
39:
33:
A graph with strength 2: the graph is here decomposed into three parts, with 4 edges between the parts, giving a ratio of 4/(3-1)=2.
731:
56:
1173:
1026:
1123:
problem, the partitions output by computing the strength are not necessarily balanced (i.e. of almost equal size).
1178:
845:
1080:
903:
1146:
326:
1142:
947:
181:
204:
155:
68:
313:{\displaystyle \displaystyle \sigma (G)=\min _{\pi \in \Pi }{\frac {|\partial \pi |}{|\pi |-1}}}
89:
71:
of the set of vertices and detect zones of high concentration of edges, and is analogous to
999:
1120:
137:
72:
161:
1167:
116:
48:
1112:
is the maximum number of edge-disjoint spanning trees that can be contained in
1134:
1155:
67:
in a decomposition of the graph in question. It is a method to compute
28:
826:{\displaystyle O(\min({\sqrt {m}},n^{2/3})mn\log(n^{2}/m+2))}
659:
437:
400:
332:
201:
be the set of edges crossing over the sets of the partition
1160:, Cybernetics and Systems Analysis, 29:379–384, 1993.
1157:
Strength of a graph and packing of trees and branchings,
642:
462:
1083:
1029:
1002:
950:
906:
848:
734:
551:
363:
329:
234:
233:
207:
184:
164:
140:
92:
21:
1104:
1066:
1015:
984:
936:
892:
825:
709:
525:
339:
312:
219:
193:
170:
146:
107:
741:
567:
379:
251:
75:which is defined similarly for vertex removal.
1136:Optimal attack and reinforcement of a network,
1067:{\displaystyle \sigma (G_{k})\geq \sigma (G)}
8:
1099:
1084:
931:
913:
887:
855:
893:{\displaystyle \pi =\{V_{1},\dots ,V_{k}\}}
1105:{\displaystyle \lfloor \sigma (G)\rfloor }
130:) admits the three following definitions:
1082:
1040:
1028:
1007:
1001:
976:
967:
955:
949:
905:
900:is one partition that maximizes, and for
881:
862:
847:
803:
797:
765:
761:
747:
733:
687:
671:
658:
657:
641:
629:
595:
579:
550:
503:
487:
461:
449:
436:
435:
411:
399:
398:
391:
362:
331:
330:
328:
295:
287:
280:
269:
266:
254:
232:
206:
183:
163:
139:
91:
18:
16:Graph-theoretic connectivity parameter
7:
347:is the set of all spanning trees of
59:corresponds to the minimum ratio of
937:{\displaystyle i\in \{1,\dots ,k\}}
1077:The Tutte-Nash-Williams theorem:
648:
610:
539:And by linear programming duality,
468:
426:
274:
261:
214:
185:
141:
14:
1139:J of ACM, 32:549–561, 1985.
27:
1096:
1090:
1061:
1055:
1046:
1033:
820:
817:
790:
775:
744:
738:
561:
555:
373:
367:
340:{\displaystyle {\mathcal {T}}}
296:
288:
281:
270:
244:
238:
102:
96:
40:Table of graphs and parameters
1:
985:{\displaystyle G_{i}=G/V_{i}}
194:{\displaystyle \partial \pi }
220:{\displaystyle \pi \in \Pi }
22:Strength of a graph: example
1148:Combinatorial Optimization,
1195:
108:{\displaystyle \sigma (G)}
38:
26:
1106:
1068:
1017:
992:is the restriction of
986:
938:
894:
827:
711:
527:
341:
314:
221:
195:
172:
148:
109:
1107:
1069:
1018:
1016:{\displaystyle V_{i}}
987:
939:
895:
828:
712:
528:
342:
315:
222:
196:
173:
149:
110:
1081:
1027:
1000:
948:
904:
846:
732:
549:
361:
327:
231:
205:
182:
162:
147:{\displaystyle \Pi }
138:
90:
1174:Graph connectivity
1133:W. H. Cunningham.
1102:
1064:
1013:
982:
934:
890:
823:
707:
682:
646:
590:
523:
498:
466:
406:
337:
310:
309:
265:
217:
191:
168:
154:be the set of all
144:
105:
65:components created
752:
667:
666:
645:
624:
609:
603:
575:
483:
482:
465:
444:
425:
419:
387:
307:
250:
171:{\displaystyle V}
115:of an undirected
55:of an undirected
45:
44:
1186:
1179:Graph invariants
1119:Contrary to the
1111:
1109:
1108:
1103:
1073:
1071:
1070:
1065:
1045:
1044:
1022:
1020:
1019:
1014:
1012:
1011:
991:
989:
988:
983:
981:
980:
971:
960:
959:
943:
941:
940:
935:
899:
897:
896:
891:
886:
885:
867:
866:
832:
830:
829:
824:
807:
802:
801:
774:
773:
769:
753:
748:
716:
714:
713:
708:
703:
699:
692:
691:
681:
664:
663:
662:
647:
643:
634:
633:
622:
607:
601:
600:
599:
589:
532:
530:
529:
524:
519:
515:
508:
507:
497:
480:
467:
463:
454:
453:
442:
441:
440:
423:
417:
416:
415:
405:
404:
403:
346:
344:
343:
338:
336:
335:
319:
317:
316:
311:
308:
306:
299:
291:
285:
284:
273:
267:
264:
226:
224:
223:
218:
200:
198:
197:
192:
177:
175:
174:
169:
153:
151:
150:
145:
114:
112:
111:
106:
31:
19:
1194:
1193:
1189:
1188:
1187:
1185:
1184:
1183:
1164:
1163:
1151:Springer, 2003.
1130:
1121:graph partition
1079:
1078:
1036:
1025:
1024:
1003:
998:
997:
972:
951:
946:
945:
902:
901:
877:
858:
844:
843:
839:
793:
757:
730:
729:
725:
683:
644: and
625:
591:
574:
570:
547:
546:
499:
464: and
445:
407:
386:
382:
359:
358:
325:
324:
286:
268:
229:
228:
203:
202:
180:
179:
160:
159:
136:
135:
88:
87:
81:
73:graph toughness
34:
17:
12:
11:
5:
1192:
1190:
1182:
1181:
1176:
1166:
1165:
1162:
1161:
1154:V. A. Trubin.
1152:
1145:. Chapter 51.
1140:
1129:
1126:
1125:
1124:
1117:
1101:
1098:
1095:
1092:
1089:
1086:
1075:
1063:
1060:
1057:
1054:
1051:
1048:
1043:
1039:
1035:
1032:
1010:
1006:
979:
975:
970:
966:
963:
958:
954:
933:
930:
927:
924:
921:
918:
915:
912:
909:
889:
884:
880:
876:
873:
870:
865:
861:
857:
854:
851:
838:
835:
822:
819:
816:
813:
810:
806:
800:
796:
792:
789:
786:
783:
780:
777:
772:
768:
764:
760:
756:
751:
746:
743:
740:
737:
724:
721:
720:
719:
718:
717:
706:
702:
698:
695:
690:
686:
680:
677:
674:
670:
661:
656:
653:
650:
640:
637:
632:
628:
621:
618:
615:
612:
606:
598:
594:
588:
585:
582:
578:
573:
569:
566:
563:
560:
557:
554:
541:
540:
536:
535:
534:
533:
522:
518:
514:
511:
506:
502:
496:
493:
490:
486:
479:
476:
473:
470:
460:
457:
452:
448:
439:
434:
431:
428:
422:
414:
410:
402:
397:
394:
390:
385:
381:
378:
375:
372:
369:
366:
353:
352:
334:
321:
305:
302:
298:
294:
290:
283:
279:
276:
272:
263:
260:
257:
253:
249:
246:
243:
240:
237:
216:
213:
210:
190:
187:
167:
143:
122: = (
104:
101:
98:
95:
80:
77:
43:
42:
36:
35:
32:
24:
23:
15:
13:
10:
9:
6:
4:
3:
2:
1191:
1180:
1177:
1175:
1172:
1171:
1169:
1159:
1158:
1153:
1150:
1149:
1144:
1141:
1138:
1137:
1132:
1131:
1127:
1122:
1118:
1115:
1093:
1087:
1076:
1058:
1052:
1049:
1041:
1037:
1030:
1008:
1004:
995:
977:
973:
968:
964:
961:
956:
952:
928:
925:
922:
919:
916:
910:
907:
882:
878:
874:
871:
868:
863:
859:
852:
849:
841:
840:
836:
834:
814:
811:
808:
804:
798:
794:
787:
784:
781:
778:
770:
766:
762:
758:
754:
749:
735:
722:
704:
700:
696:
693:
688:
684:
678:
675:
672:
668:
654:
651:
638:
635:
630:
626:
619:
616:
613:
604:
596:
592:
586:
583:
580:
576:
571:
564:
558:
552:
545:
544:
543:
542:
538:
537:
520:
516:
512:
509:
504:
500:
494:
491:
488:
484:
477:
474:
471:
458:
455:
450:
446:
432:
429:
420:
412:
408:
395:
392:
388:
383:
376:
370:
364:
357:
356:
355:
354:
350:
322:
303:
300:
292:
277:
258:
255:
247:
241:
235:
211:
208:
188:
165:
157:
133:
132:
131:
129:
125:
121:
118:
99:
93:
86:
78:
76:
74:
70:
66:
62:
61:edges removed
58:
54:
50:
41:
37:
30:
25:
20:
1156:
1147:
1143:A. Schrijver
1135:
1113:
993:
726:
348:
127:
123:
119:
117:simple graph
84:
82:
64:
60:
52:
49:graph theory
46:
996:to the set
79:Definitions
1168:Categories
1128:References
837:Properties
723:Complexity
156:partitions
69:partitions
1100:⌋
1088:σ
1085:⌊
1053:σ
1050:≥
1031:σ
923:…
911:∈
872:…
850:π
788:
694:≥
676:∈
669:∑
655:∈
649:∀
636:≥
617:∈
611:∀
584:∈
577:∑
553:σ
510:≤
501:λ
492:∋
485:∑
475:∈
469:∀
456:≥
447:λ
433:∈
427:∀
409:λ
396:∈
389:∑
365:σ
301:−
293:π
278:π
275:∂
262:Π
259:∈
256:π
236:σ
215:Π
212:∈
209:π
189:π
186:∂
142:Π
94:σ
323:Also if
227:, then
85:strength
53:strength
1023:, then
126:,
665:
623:
608:
602:
481:
443:
424:
418:
351:, then
178:, and
51:, the
57:graph
134:Let
83:The
842:If
785:log
742:min
568:min
380:max
252:min
158:of
47:In
1170::
944:,
833:.
1116:.
1114:G
1097:)
1094:G
1091:(
1074:.
1062:)
1059:G
1056:(
1047:)
1042:k
1038:G
1034:(
1009:i
1005:V
994:G
978:i
974:V
969:/
965:G
962:=
957:i
953:G
932:}
929:k
926:,
920:,
917:1
914:{
908:i
888:}
883:k
879:V
875:,
869:,
864:1
860:V
856:{
853:=
821:)
818:)
815:2
812:+
809:m
805:/
799:2
795:n
791:(
782:n
779:m
776:)
771:3
767:/
763:2
759:n
755:,
750:m
745:(
739:(
736:O
705:.
701:}
697:1
689:e
685:y
679:E
673:e
660:T
652:T
639:0
631:e
627:y
620:E
614:e
605::
597:e
593:y
587:E
581:e
572:{
565:=
562:)
559:G
556:(
521:.
517:}
513:1
505:T
495:e
489:T
478:E
472:e
459:0
451:T
438:T
430:T
421::
413:T
401:T
393:T
384:{
377:=
374:)
371:G
368:(
349:G
333:T
320:.
304:1
297:|
289:|
282:|
271:|
248:=
245:)
242:G
239:(
166:V
128:E
124:V
120:G
103:)
100:G
97:(
63:/
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
