25:
1583:
It is helpful to find a layout of minimum size when designing a VLSI circuit. Such a problem can often be modeled as a graph embedding problem. The objective is to find an embedding for which the layout area is minimized. Finding the minimum layout area is also NP-hard. An approximation algorithm has
530:
The research on the relationship between the max-flow and min-cut of multicommodity flow problem has obtained great interest since Ford and
Fulkerson's result for 1-commodity flow problems. Hu showed that the max-flow and min-cut are always equal for two commodities. Okamura and Seymour illustrated a
287:, such that the total amount of all commodities passing through any edge is no greater than its capacity. (In the case of undirected edges, the sum of the flows in both directions cannot exceed the capacity of the edge). Specially, a 1-commodity (or single commodity) flow problem is also known as a
769:
To prove
Theorem 2, both the max-flow and the min-cut should be discussed. For the max-flow, the techniques from duality theory of linear programming have to be employed. According to the duality theory of linear programming, an optimal distance function results in a total weight that is equal to
385:
In a uniform multicommodity flow problem, there is a commodity for every pair of nodes and the demand for every commodity is the same. (Without loss of generality, the demand for every commodity is set to one.) The underlying network and capacities are arbitrary.
535:
also proved that the max-flow and min-cut are equal provided the dual of the flow problem satisfies a certain cut condition in a uniform multicommodity flow problem. Many other researchers also showed concrete research results in similar problems
1151:
is a partition for which the ratio of the number of edges connecting the two partitioned components over the product of the numbers of nodes of both components is minimized. This is a NP-hard problem, and it can be approximated to within
987:
The major difference in the proof methodology compared to
Theorem 2 is that, now the edge directions need to be considered when defining distance labels in stage 1 and for growing the regions in stage 2, more details can be found in.
889:
In a directed multicommodity flow problem, each edge has a direction, and the flow is restricted to move in the specified direction. In a directed uniform multicommodity flow problem, the demand is set to 1 for every directed edge.
1058:
957:
851:
739:
1830:
673:
1573:
1490:
1374:
1708:. The objective is to find an embedding that minimizes the forwarding index. Using embedding approaches it is possible to bound the node and edge-forwarding indices to within an
1624:
343:
223:
1741:
1220:
1185:
1082:
981:
875:
763:
621:
375:
43:
1403:
1270:
1149:
456:
2130:
Leighton, Tom; Rao, Satish (1988). "An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms".
498:
418:
1702:
1667:
281:
254:
196:
169:
142:
569:
584:
There are two theorems first introduced by Tom
Leighton and Satish Rao in 1988 and then extended in 1999. Theorem 2 gives a tighter bound compared to Theorem 1.
1005:
904:
798:
686:
1988:
474:. The uniform multicommodity flow problem is a special case of the product multicommodity flow problem for which the weight is set to 1 for all nodes
1105:
problem and its variations. Here below we briefly introduce a few examples, and the in-depth elaborations can be found in
Leighton and Rao (1999).
776:
Stage 2: Starting from a source or a sink, grow a region in the graph until find a cut of small enough capacity separating the root from its mate.
2147:
773:
Stage 1: Consider the dual of uniform commodity flow problem and use the optimal solution to define a graph with distance labels on the edges.
1758:
1907:
Leighton, Tom; Rao, Satish (November 1999). "Multicommodity Max-Flow Min-Cut
Theorems and Their Use in Designing Approximation Algorithms".
1187:
factor using
Theorem 2. Also, a sparsest cut problem with weighted edges, weighted nodes or directed edges can be approximated within an
377:
of the capacity of the cut to the demand of the cut. Max-flow is always upper bounded by the min-cut for a multicommodity flow problem.
626:
61:
2062:
Klein, P.; Plotkin, S.; Rao, S.; Tardos, E. (1997). "Bounds on the max-flow min-cut ratio for directed multicommodity flows".
2200:
1516:
1435:
1302:
2195:
1959:
881:
The proof methodology is similar to that for
Theorem 2; the major difference is to take node weights into consideration.
292:
90:
518:
is the problem of apportioning a fixed amount of weight (where weights can be considered as distances) to the edges of
2086:
Garg, N.; Vazarani, V.; Yannakakis, M. (1996). "Approximate max-flow min-(multi)cut theorems and their applications".
2145:
Chung, F. K.; Coffman, E. G.; Reiman, M. I.; Simon, B. E. (1987). "The forwarding index of communication networks".
2088:
1513:. Then we repeat the process then finally obtain the result that total weight of the edges in the cut is at most
770:
the max-flow of the uniform multicommodity flow problem. For the min-cut, a 3-stage process has to be followed:
1845:
82:
1094:
571:
of the capacity of each edge. This is not a good result especially in case of large numbers of commodities.
94:
2115:
Plitkin, S.; Tardos, E. (1993). "Improved bounds on the max-flow min-cut ratio for multicommodity flows".
1918:
288:
1923:
1587:
318:
110:
1413:
problem. An approximation algorithm has been designed for this problem, and the core idea is that
201:
2044:
2025:
1936:
1909:
509:
1711:
1190:
1155:
1067:
966:
860:
748:
606:
360:
2176:
VLSI partitioning approximation algorithms based on multicommodity flows and other techniques
1379:
1237:
1116:
423:
2156:
2097:
2034:
1997:
1968:
1928:
991:
Similarly, for product multicommodity flow problem, we have the following extended theorem:
779:
Stage 3: Remove the region and repeat the process of stage 2 until all nodes get processed.
477:
397:
1680:
1645:
259:
232:
174:
147:
120:
1102:
98:
546:
531:
4-commodity flow problem with max-flow equals to 3/4 and min-cut equals 1. Shahrokhi and
2001:
394:
In a product multicommodity flow problem, there is a nonnegative weight for each node
2189:
2064:
1755:
Tragoudas uses the approximation algorithm for balanced separators to find a set of
1677:
of the embedding to be the maximum number of paths (each corresponding to an edge of
1940:
2048:
2016:
532:
78:
1053:{\displaystyle \Omega \left({\frac {\varphi }{\log k}}\right)\leq f\leq \varphi }
952:{\displaystyle \Omega \left({\frac {\varphi }{\log n}}\right)\leq f\leq \varphi }
846:{\displaystyle \Omega \left({\frac {\varphi }{\log k}}\right)\leq f\leq \varphi }
734:{\displaystyle \Omega \left({\frac {\varphi }{\log n}}\right)\leq f\leq \varphi }
522:
such that to maximize the cumulative distance between the source and sink pairs.
86:
1272:
that partitions the graph into nearly equal-size pieces. We usually call a cut
2101:
2160:
1986:
Okamura, H.; Seymour, P. D. (1981). "Multicommodity flows in planar graphs".
1226:
is the number of nodes with nonzero weight according to
Theorem 3, 4 and 5.
2178:(Ph.D. dissertation). Department of Computer Sciences, University of Texas.
295:, the max-flow and min-cut are always equal in a 1-commodity flow problem.
1972:
1932:
2132:
Proceedings of the 29th IEEE Symposium on
Foundations of Computer Science
1954:
2039:
2020:
1825:{\displaystyle O\left((R\log n+{\sqrt {nR}})\log {\frac {n}{R}}\right)}
1410:
1098:
539:
For a general network flow problem, the max-flow is within a factor of
543:
of the min-cut since each commodity can be optimized separately using
85:
deal with the relationship between maximum flow rate ("max-flow") and
109:
A "commodity" in a network flow problem is a pair of source and sink
1844:
before it becomes planar. It remains an open question if there is a
2117:
Proceedings of the 25th Annual ACM Symposium on Theory of Computing
1084:
is the directed min-cut of the product multicommodity flow problem.
315:
is the common fraction of each commodity that is routed, such that
514:
In general, the dual of a multicommodity flow problem for a graph
668:{\displaystyle f\leq O\left({\frac {\varphi }{\log n}}\right)}
18:
1234:
In some applications, we want to find a small cut in a graph
1840:
is the minimum number of edges that need to be removed from
998:
For any directed product multicommodity flow problem with
983:
is the min-cut of the uniform multicommodity flow problem.
897:
For any directed uniform multicommodity flow problem with
877:
is the min-cut of the product multicommodity flow problem.
765:
is the min-cut of the uniform multicommodity flow problem.
599:-node uniform multicommodity flow problem with max-flow
39:
1761:
1714:
1683:
1648:
1590:
1568:{\displaystyle O\left({\frac {S\log n}{b-b'}}\right)}
1519:
1485:{\displaystyle O\left(S\log {\frac {n}{b}}-b'\right)}
1438:
1382:
1369:{\displaystyle b\pi (V)\leq \pi (U)\leq (1-b)\pi (V)}
1305:
1240:
1193:
1158:
1119:
1070:
1008:
969:
907:
863:
801:
751:
689:
629:
609:
549:
480:
426:
400:
363:
321:
262:
235:
204:
177:
150:
123:
34:
may be too technical for most readers to understand
1824:
1735:
1696:
1661:
1618:
1567:
1484:
1397:
1368:
1264:
1214:
1179:
1143:
1076:
1052:
975:
951:
869:
845:
783:Generalized to product multicommodity flow problem
757:
733:
667:
615:
563:
492:
450:
412:
369:
337:
275:
248:
217:
190:
163:
136:
791:For any product multicommodity flow problem with
1832:edges whose removal from a bounded-degree graph
885:Extended to directed multicommodity flow problem
580:Theorems of uniform multicommodity flow problems
16:Mathematical propositions in network flow theory
113:. In a multi-commodity flow problem, there are
93:. The theorems have enabled the development of
1902:
1900:
1898:
1896:
1894:
1892:
1890:
1888:
1093:The above theorems are very useful to design
683:For any uniform multicommodity flow problem,
458:. The demand for the commodity between nodes
8:
1886:
1884:
1882:
1880:
1878:
1876:
1874:
1872:
1870:
1868:
353:without violating any capacity constraints.
198:. The objective is to simultaneously route
1851:times optimal approximation algorithm for
2038:
1989:Journal of Combinatorial Theory, Series B
1922:
1807:
1788:
1760:
1713:
1688:
1682:
1653:
1647:
1601:
1589:
1527:
1518:
1456:
1437:
1381:
1304:
1239:
1192:
1157:
1118:
1069:
1016:
1007:
968:
915:
906:
862:
809:
800:
750:
697:
688:
643:
628:
608:
553:
548:
479:
425:
399:
362:
329:
320:
267:
261:
240:
234:
209:
203:
182:
176:
155:
149:
128:
122:
62:Learn how and when to remove this message
46:, without removing the technical details.
2081:
2079:
1957:(1963). "Multicommodity network flows".
1089:Applications to approximation algorithms
357:is the minimum of all cuts of the ratio
2148:IEEE Transactions on Information Theory
1864:
466:is the product of the weights of node
349:can be simultaneously routed for each
117:commodities, each with its own source
2021:"The maximum concurrent flow problem"
575:Approximate max-flow min-cut theorems
75:Approximate max-flow min-cut theorems
44:make it understandable to non-experts
7:
390:Product multicommodity flow problem
381:Uniform multicommodity flow problem
1584:been introduced and the result is
1405:is the sum of the node weights in
1009:
908:
802:
690:
303:In a multicommodity flow problem,
14:
1836:results in a planar graph, where
77:are mathematical propositions in
1704:) that pass through any node of
23:
1798:
1770:
1730:
1718:
1613:
1594:
1392:
1386:
1363:
1357:
1351:
1339:
1333:
1327:
1318:
1312:
1259:
1247:
1209:
1197:
1174:
1162:
1138:
1126:
445:
433:
1:
2002:10.1016/S0095-8956(81)80012-3
1619:{\displaystyle O(\log ^{6}n)}
504:Duality of linear programming
338:{\displaystyle fD_{\text{i}}}
1230:Balanced cuts and separators
218:{\displaystyle D_{\text{i}}}
91:multi-commodity flow problem
1673:, Chung et al. defined the
105:Multicommodity flow problem
2217:
1113:A sparsest cut of a graph
507:
2102:10.1137/s0097539793243016
2089:SIAM Journal on Computing
1736:{\displaystyle O(\log n)}
1215:{\displaystyle O(\log p)}
1180:{\displaystyle O(\log n)}
83:max-flow min-cut theorems
2161:10.1109/tit.1987.1057290
1743:-factor for every graph
1630:Forwarding index problem
1095:approximation algorithms
1077:{\displaystyle \varphi }
976:{\displaystyle \varphi }
870:{\displaystyle \varphi }
758:{\displaystyle \varphi }
616:{\displaystyle \varphi }
370:{\displaystyle \varphi }
307:is the maximum value of
293:Ford–Fulkerson algorithm
95:approximation algorithms
1511:′ ≤ 1/3
1501:′ <
1398:{\displaystyle \pi (U)}
1265:{\displaystyle G=(V,E)}
1144:{\displaystyle G=(V,E)}
451:{\displaystyle G=(V,E)}
2174:Tragoudas, S. (1990).
1826:
1737:
1698:
1663:
1620:
1569:
1486:
1432:-balanced cut of size
1421:-balanced cut of size
1399:
1370:
1266:
1216:
1181:
1145:
1101:problems, such as the
1078:
1054:
977:
953:
871:
847:
759:
735:
669:
617:
565:
494:
493:{\displaystyle u\in V}
452:
414:
413:{\displaystyle v\in V}
371:
339:
277:
250:
219:
192:
165:
138:
101:and related problems.
2201:Mathematical theorems
1973:10.1287/opre.11.3.344
1933:10.1145/331524.331526
1827:
1738:
1699:
1697:{\displaystyle K_{n}}
1664:
1662:{\displaystyle K_{n}}
1621:
1570:
1487:
1400:
1371:
1282:,1 −
1267:
1217:
1182:
1146:
1079:
1055:
978:
954:
872:
848:
760:
736:
670:
618:
566:
495:
453:
415:
372:
340:
278:
276:{\displaystyle t_{i}}
251:
249:{\displaystyle s_{i}}
220:
193:
191:{\displaystyle D_{i}}
166:
164:{\displaystyle t_{i}}
139:
137:{\displaystyle s_{i}}
2196:Network flow problem
1759:
1751:Planar edge deletion
1712:
1681:
1646:
1642:and an embedding of
1588:
1579:VLSI layout problems
1517:
1436:
1380:
1303:
1238:
1191:
1156:
1117:
1068:
1064:is the max-flow and
1006:
967:
963:is the max-flow and
905:
861:
857:is the max-flow and
799:
749:
745:is the max-flow and
687:
627:
607:
547:
478:
424:
398:
361:
319:
299:Max-flow and min-cut
289:maximum flow problem
260:
233:
202:
175:
148:
121:
81:theory. Approximate
2040:10.1145/77600.77620
1960:Operations Research
564:{\displaystyle 1/k}
345:units of commodity
291:. According to the
225:units of commodity
2026:Journal of the ACM
1910:Journal of the ACM
1822:
1733:
1694:
1659:
1616:
1565:
1482:
1409:. This is also an
1395:
1366:
1262:
1212:
1177:
1141:
1074:
1050:
973:
949:
867:
843:
755:
731:
665:
613:
561:
510:Linear programming
490:
448:
410:
367:
335:
273:
246:
215:
188:
161:
134:
1815:
1796:
1559:
1464:
1425:, then we find a
1032:
931:
825:
713:
659:
332:
212:
89:("min-cut") in a
72:
71:
64:
2208:
2180:
2179:
2171:
2165:
2164:
2142:
2136:
2135:
2127:
2121:
2120:
2112:
2106:
2105:
2083:
2074:
2073:
2059:
2053:
2052:
2042:
2017:Matula, David W.
2012:
2006:
2005:
1983:
1977:
1976:
1951:
1945:
1944:
1926:
1904:
1854:
1850:
1843:
1839:
1835:
1831:
1829:
1828:
1823:
1821:
1817:
1816:
1808:
1797:
1789:
1746:
1742:
1740:
1739:
1734:
1707:
1703:
1701:
1700:
1695:
1693:
1692:
1675:forwarding index
1672:
1668:
1666:
1665:
1660:
1658:
1657:
1641:
1637:
1625:
1623:
1622:
1617:
1606:
1605:
1574:
1572:
1571:
1566:
1564:
1560:
1558:
1557:
1542:
1528:
1512:
1505:
1495:
1491:
1489:
1488:
1483:
1481:
1477:
1476:
1465:
1457:
1431:
1424:
1420:
1416:
1408:
1404:
1402:
1401:
1396:
1375:
1373:
1372:
1367:
1298:
1297: ≤ 1/2
1287:
1271:
1269:
1268:
1263:
1225:
1221:
1219:
1218:
1213:
1186:
1184:
1183:
1178:
1150:
1148:
1147:
1142:
1083:
1081:
1080:
1075:
1063:
1059:
1057:
1056:
1051:
1037:
1033:
1031:
1017:
1001:
982:
980:
979:
974:
962:
958:
956:
955:
950:
936:
932:
930:
916:
900:
876:
874:
873:
868:
856:
852:
850:
849:
844:
830:
826:
824:
810:
794:
764:
762:
761:
756:
744:
740:
738:
737:
732:
718:
714:
712:
698:
674:
672:
671:
666:
664:
660:
658:
644:
622:
620:
619:
614:
602:
598:
594:
570:
568:
567:
562:
557:
542:
521:
517:
499:
497:
496:
491:
473:
469:
465:
461:
457:
455:
454:
449:
419:
417:
416:
411:
376:
374:
373:
368:
352:
348:
344:
342:
341:
336:
334:
333:
330:
314:
310:
286:
282:
280:
279:
274:
272:
271:
255:
253:
252:
247:
245:
244:
228:
224:
222:
221:
216:
214:
213:
210:
197:
195:
194:
189:
187:
186:
170:
168:
167:
162:
160:
159:
143:
141:
140:
135:
133:
132:
116:
67:
60:
56:
53:
47:
27:
26:
19:
2216:
2215:
2211:
2210:
2209:
2207:
2206:
2205:
2186:
2185:
2184:
2183:
2173:
2172:
2168:
2144:
2143:
2139:
2129:
2128:
2124:
2114:
2113:
2109:
2085:
2084:
2077:
2061:
2060:
2056:
2015:Shahrokri, F.;
2014:
2013:
2009:
1985:
1984:
1980:
1953:
1952:
1948:
1924:10.1.1.640.2995
1906:
1905:
1866:
1861:
1852:
1848:
1841:
1837:
1833:
1769:
1765:
1757:
1756:
1753:
1744:
1710:
1709:
1705:
1684:
1679:
1678:
1670:
1649:
1644:
1643:
1639:
1635:
1632:
1626:times optimal.
1597:
1586:
1585:
1581:
1550:
1543:
1529:
1523:
1515:
1514:
1507:
1497:
1493:
1469:
1446:
1442:
1434:
1433:
1426:
1422:
1418:
1414:
1406:
1378:
1377:
1301:
1300:
1293:
1277:
1236:
1235:
1232:
1223:
1189:
1188:
1154:
1153:
1115:
1114:
1111:
1103:graph partition
1091:
1066:
1065:
1061:
1021:
1012:
1004:
1003:
999:
965:
964:
960:
920:
911:
903:
902:
898:
887:
859:
858:
854:
814:
805:
797:
796:
792:
785:
747:
746:
742:
702:
693:
685:
684:
648:
639:
625:
624:
605:
604:
600:
596:
592:
582:
577:
545:
544:
540:
528:
519:
515:
512:
506:
476:
475:
471:
467:
463:
459:
422:
421:
396:
395:
392:
383:
359:
358:
350:
346:
325:
317:
316:
312:
308:
301:
284:
263:
258:
257:
236:
231:
230:
226:
205:
200:
199:
178:
173:
172:
151:
146:
145:
124:
119:
118:
114:
107:
99:graph partition
68:
57:
51:
48:
40:help improve it
37:
28:
24:
17:
12:
11:
5:
2214:
2212:
2204:
2203:
2198:
2188:
2187:
2182:
2181:
2166:
2155:(2): 224–232.
2137:
2122:
2107:
2096:(2): 235–251.
2075:
2054:
2033:(2): 318–334.
2007:
1978:
1967:(3): 344–360.
1946:
1917:(6): 787–832.
1863:
1862:
1860:
1857:
1820:
1814:
1811:
1806:
1803:
1800:
1795:
1792:
1787:
1784:
1781:
1778:
1775:
1772:
1768:
1764:
1752:
1749:
1732:
1729:
1726:
1723:
1720:
1717:
1691:
1687:
1656:
1652:
1631:
1628:
1615:
1612:
1609:
1604:
1600:
1596:
1593:
1580:
1577:
1563:
1556:
1553:
1549:
1546:
1541:
1538:
1535:
1532:
1526:
1522:
1480:
1475:
1472:
1468:
1463:
1460:
1455:
1452:
1449:
1445:
1441:
1394:
1391:
1388:
1385:
1365:
1362:
1359:
1356:
1353:
1350:
1347:
1344:
1341:
1338:
1335:
1332:
1329:
1326:
1323:
1320:
1317:
1314:
1311:
1308:
1261:
1258:
1255:
1252:
1249:
1246:
1243:
1231:
1228:
1211:
1208:
1205:
1202:
1199:
1196:
1176:
1173:
1170:
1167:
1164:
1161:
1140:
1137:
1134:
1131:
1128:
1125:
1122:
1110:
1107:
1090:
1087:
1073:
1049:
1046:
1043:
1040:
1036:
1030:
1027:
1024:
1020:
1015:
1011:
972:
948:
945:
942:
939:
935:
929:
926:
923:
919:
914:
910:
886:
883:
866:
842:
839:
836:
833:
829:
823:
820:
817:
813:
808:
804:
784:
781:
754:
730:
727:
724:
721:
717:
711:
708:
705:
701:
696:
692:
663:
657:
654:
651:
647:
642:
638:
635:
632:
612:
595:, there is an
581:
578:
576:
573:
560:
556:
552:
527:
524:
505:
502:
489:
486:
483:
447:
444:
441:
438:
435:
432:
429:
409:
406:
403:
391:
388:
382:
379:
366:
328:
324:
300:
297:
270:
266:
243:
239:
208:
185:
181:
158:
154:
131:
127:
106:
103:
70:
69:
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
2213:
2202:
2199:
2197:
2194:
2193:
2191:
2177:
2170:
2167:
2162:
2158:
2154:
2150:
2149:
2141:
2138:
2133:
2126:
2123:
2118:
2111:
2108:
2103:
2099:
2095:
2091:
2090:
2082:
2080:
2076:
2071:
2067:
2066:
2065:J. Algorithms
2058:
2055:
2050:
2046:
2041:
2036:
2032:
2028:
2027:
2022:
2018:
2011:
2008:
2003:
1999:
1995:
1991:
1990:
1982:
1979:
1974:
1970:
1966:
1962:
1961:
1956:
1950:
1947:
1942:
1938:
1934:
1930:
1925:
1920:
1916:
1912:
1911:
1903:
1901:
1899:
1897:
1895:
1893:
1891:
1889:
1887:
1885:
1883:
1881:
1879:
1877:
1875:
1873:
1871:
1869:
1865:
1858:
1856:
1847:
1818:
1812:
1809:
1804:
1801:
1793:
1790:
1785:
1782:
1779:
1776:
1773:
1766:
1762:
1750:
1748:
1727:
1724:
1721:
1715:
1689:
1685:
1676:
1654:
1650:
1629:
1627:
1610:
1607:
1602:
1598:
1591:
1578:
1576:
1561:
1554:
1551:
1547:
1544:
1539:
1536:
1533:
1530:
1524:
1520:
1510:
1504:
1500:
1478:
1473:
1470:
1466:
1461:
1458:
1453:
1450:
1447:
1443:
1439:
1429:
1412:
1389:
1383:
1360:
1354:
1348:
1345:
1342:
1336:
1330:
1324:
1321:
1315:
1309:
1306:
1296:
1291:
1285:
1281:
1275:
1256:
1253:
1250:
1244:
1241:
1229:
1227:
1222:factor where
1206:
1203:
1200:
1194:
1171:
1168:
1165:
1159:
1135:
1132:
1129:
1123:
1120:
1109:Sparsest cuts
1108:
1106:
1104:
1100:
1096:
1088:
1086:
1085:
1071:
1047:
1044:
1041:
1038:
1034:
1028:
1025:
1022:
1018:
1013:
1002:commodities,
996:
992:
989:
985:
984:
970:
946:
943:
940:
937:
933:
927:
924:
921:
917:
912:
895:
891:
884:
882:
879:
878:
864:
840:
837:
834:
831:
827:
821:
818:
815:
811:
806:
795:commodities,
789:
782:
780:
777:
774:
771:
767:
766:
752:
728:
725:
722:
719:
715:
709:
706:
703:
699:
694:
681:
677:
676:
661:
655:
652:
649:
645:
640:
636:
633:
630:
610:
589:
585:
579:
574:
572:
558:
554:
550:
537:
534:
525:
523:
511:
503:
501:
487:
484:
481:
442:
439:
436:
430:
427:
407:
404:
401:
389:
387:
380:
378:
364:
356:
326:
322:
306:
298:
296:
294:
290:
268:
264:
241:
237:
206:
183:
179:
171:, and demand
156:
152:
129:
125:
112:
104:
102:
100:
96:
92:
88:
84:
80:
76:
66:
63:
55:
45:
41:
35:
32:This article
30:
21:
20:
2175:
2169:
2152:
2146:
2140:
2131:
2125:
2116:
2110:
2093:
2087:
2069:
2063:
2057:
2030:
2024:
2010:
1993:
1987:
1981:
1964:
1958:
1949:
1914:
1908:
1754:
1674:
1638:-node graph
1633:
1582:
1508:
1502:
1498:
1427:
1294:
1289:
1283:
1279:
1273:
1233:
1112:
1092:
997:
994:
993:
990:
986:
896:
893:
892:
888:
880:
790:
787:
786:
778:
775:
772:
768:
682:
679:
678:
603:and min-cut
590:
587:
586:
583:
538:
529:
513:
393:
384:
354:
304:
302:
108:
79:network flow
74:
73:
58:
52:January 2016
49:
33:
97:for use in
87:minimum cut
2190:Categories
2134:: 422–431.
2119:: 691–697.
2072:: 241–269.
1859:References
1274:b-balanced
995:Theorem 5.
894:Theorem 4.
788:Theorem 3.
680:Theorem 2.
623:for which
588:Theorem 1.
508:See also:
1996:: 75–81.
1955:Hu, T. C.
1919:CiteSeerX
1805:
1780:
1725:
1634:Given an
1608:
1548:−
1537:
1467:−
1454:
1384:π
1355:π
1346:−
1337:≤
1325:π
1322:≤
1310:π
1290:separator
1204:
1169:
1072:φ
1048:φ
1045:≤
1039:≤
1026:
1019:φ
1010:Ω
971:φ
947:φ
944:≤
938:≤
925:
918:φ
909:Ω
865:φ
841:φ
838:≤
832:≤
819:
812:φ
803:Ω
753:φ
729:φ
726:≤
720:≤
707:
700:φ
691:Ω
653:
646:φ
634:≤
611:φ
485:∈
470:and node
420:in graph
405:∈
365:φ
283:for each
2019:(1990).
1941:18527968
1555:′
1492:for any
1474:′
1060:, where
959:, where
853:, where
741:, where
591:For any
311:, where
305:max-flow
2049:4469579
1846:polylog
1430:′
1411:NP-hard
1099:NP-hard
901:nodes,
526:History
355:min-cut
144:, sink
38:Please
2047:
1939:
1921:
1496:where
1417:has a
1376:where
533:Matula
2045:S2CID
1937:S2CID
1299:) if
1292:(for
1276:or a
229:from
111:nodes
1506:and
1097:for
462:and
2157:doi
2098:doi
2035:doi
1998:doi
1969:doi
1929:doi
1802:log
1777:log
1722:log
1669:in
1599:log
1534:log
1451:log
1201:log
1166:log
1023:log
922:log
816:log
704:log
650:log
256:to
115:k≥1
42:to
2192::
2153:33
2151:.
2094:25
2092:.
2078:^
2070:22
2068:.
2043:.
2031:37
2029:.
2023:.
1994:31
1992:.
1965:11
1963:.
1935:.
1927:.
1915:46
1913:.
1867:^
1855:.
1747:.
1575:.
1494:b'
500:.
2163:.
2159::
2104:.
2100::
2051:.
2037::
2004:.
2000::
1975:.
1971::
1943:.
1931::
1853:R
1849:n
1842:G
1838:R
1834:G
1819:)
1813:R
1810:n
1799:)
1794:R
1791:n
1786:+
1783:n
1774:R
1771:(
1767:(
1763:O
1745:G
1731:)
1728:n
1719:(
1716:O
1706:G
1690:n
1686:K
1671:G
1655:n
1651:K
1640:G
1636:n
1614:)
1611:n
1603:6
1595:(
1592:O
1562:)
1552:b
1545:b
1540:n
1531:S
1525:(
1521:O
1509:b
1503:b
1499:b
1479:)
1471:b
1462:b
1459:n
1448:S
1444:(
1440:O
1428:b
1423:S
1419:b
1415:G
1407:U
1393:)
1390:U
1387:(
1364:)
1361:V
1358:(
1352:)
1349:b
1343:1
1340:(
1334:)
1331:U
1328:(
1319:)
1316:V
1313:(
1307:b
1295:b
1288:-
1286:)
1284:b
1280:b
1278:(
1260:)
1257:E
1254:,
1251:V
1248:(
1245:=
1242:G
1224:p
1210:)
1207:p
1198:(
1195:O
1175:)
1172:n
1163:(
1160:O
1139:)
1136:E
1133:,
1130:V
1127:(
1124:=
1121:G
1062:f
1042:f
1035:)
1029:k
1014:(
1000:k
961:f
941:f
934:)
928:n
913:(
899:n
855:f
835:f
828:)
822:k
807:(
793:k
743:f
723:f
716:)
710:n
695:(
675:.
662:)
656:n
641:(
637:O
631:f
601:f
597:n
593:n
559:k
555:/
551:1
541:k
520:G
516:G
488:V
482:u
472:v
468:u
464:v
460:u
446:)
443:E
440:,
437:V
434:(
431:=
428:G
408:V
402:v
351:i
347:i
331:i
327:D
323:f
313:f
309:f
285:i
269:i
265:t
242:i
238:s
227:i
211:i
207:D
184:i
180:D
157:i
153:t
130:i
126:s
65:)
59:(
54:)
50:(
36:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.