1016:
1394:
1205:
2026:
776:
1604:
810:
2163:
can be modeled as an integer minimum cost multi-commodity flow problem: Values produced by instructions are source nodes, values consumed by instructions are sink nodes and registers as well as stack slots are edges.
1795:
1677:
310:
2422:
Add: Jean-Patrice Netter, Flow
Augmenting Meshings: a primal type of approach to the maximum integer flow in a multi-commodity network, Ph.D dissertation Johns Hopkins University, 1971
1219:
1030:
237:
642:
2081:
1858:
581:
466:
1478:
121:
2367:
157:
83:
1891:
1710:
520:
423:
366:
338:
1440:
487:
395:
178:
2132:
2112:
802:
1899:
656:
2188:
1011:{\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(u,w)\in E}f_{i}(u,w)-\sum _{(w,u)\in E}f_{i}(w,u)=0\quad \mathrm {when} \quad u\neq s_{i},t_{i}}
1486:
2351:
2398:
2146:
644:
otherwise (i.e. "single path routing"). Find an assignment of all flow variables which satisfies the following four constraints:
2218:
1718:
2439:
2434:
2035:, the demand of each commodity is not fixed, and the total throughput is maximized by maximizing the sum of all demands
2413:
2138:
are generalizations of all flow problems. That is, any flow problem can be viewed as a particular circulation problem.
2341:
1612:
1389:{\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(u,w)\in E}f_{i}(w,t_{i})-\sum _{(w,u)\in E}f_{i}(t_{i},w)=1}
1200:{\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(u,w)\in E}f_{i}(s_{i},w)-\sum _{(w,u)\in E}f_{i}(w,s_{i})=1}
2091:
242:
183:
2275:
S. Even and A. Itai and A. Shamir (1976). "On the
Complexity of Timetable and Multicommodity Flow Problems".
586:
2294:
Even, S.; Itai, A.; Shamir, A. (1975). "On the complexity of time table and multi-commodity flow problems".
2150:
2038:
17:
2172:
In the decision version of problems, the problem of producing an integer flow satisfying all demands is
1807:
525:
2329:
2177:
35:
2160:
2135:
428:
2361:
2307:
2257:
2184:
2390:
2382:
1445:
88:
2394:
2347:
126:
52:
2254:"Towards a more principled compiler: Register allocation and instruction selection revisited"
2219:
https://web.archive.org/web/20130306031532/http://typo.zib.de/opt-long_projects/Software/Mcf/
1863:
1682:
492:
400:
343:
315:
2333:
2325:
2299:
2284:
1410:
2021:{\displaystyle \sum _{(u,v)\in E}\left(a(u,v)\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}\right)}
471:
379:
162:
2090:
The minimum cost variant of the multi-commodity flow problem is a generalization of the
1679:. A common linearization of this problem is the minimization of the maximum utilization
2337:
2117:
2097:
787:
2183:
If fractional flows are allowed, the problem can be solved in polynomial time through
2428:
2311:
2261:
771:{\displaystyle \forall (u,v)\in E:\,\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}\leq c(u,v)}
47:
38:
with multiple commodities (flow demands) between different source and sink nodes.
2173:
2387:
Proceedings of the thirteenth annual ACM-SIAM symposium on
Discrete algorithms
2212:
1599:{\displaystyle U(u,v)={\frac {\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}}{c(u,v)}}}
2202:
Multicommodity flow is applied in the overlay routing in content delivery.
2383:"Faster approximation schemes for fractional multicommodity flow problems"
2303:
2176:, even for only two commodities and unit capacities (making the problem
650:
The sum of all flows routed over a link does not exceed its capacity.
2296:
16th Annual
Symposium on Foundations of Computer Science (SFCS 1975)
2288:
2154:
2237:
Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993).
2346:(3rd ed.). MIT Press and McGraw–Hill. p. 862.
1407:
is the attempt to route flows such that the utilization
583:
in case the flow can be split among multiple paths, and
2157:
would be approached via multi-commodity flow formulas.
1790:{\displaystyle \forall (u,v)\in E:\,U_{max}\geq U(u,v)}
2120:
2100:
2041:
1902:
1866:
1810:
1721:
1685:
1615:
1489:
1448:
1413:
1222:
1033:
813:
790:
659:
589:
528:
495:
474:
431:
403:
382:
346:
318:
245:
186:
165:
129:
91:
55:
2239:
784:The amount of a flow entering an intermediate node
2126:
2106:
2075:
2020:
1885:
1852:
1789:
1704:
1671:
1598:
1472:
1434:
1388:
1199:
1010:
796:
770:
636:
575:
514:
481:
460:
417:
389:
360:
332:
304:
231:
172:
151:
115:
77:
2211:Papers by Clifford Stein about this problem:
1609:The problem can be solved e.g. by minimizing
1024:A flow must exit its source node completely.
8:
2366:: CS1 maint: multiple names: authors list (
1672:{\displaystyle \sum _{u,v\in V}(U(u,v))^{2}}
1250:
1232:
1213:A flow must enter its sink node completely.
1061:
1043:
841:
823:
631:
619:
2213:http://www.columbia.edu/~cs2035/papers/#mcf
2189:fully polynomial time approximation schemes
305:{\displaystyle \,K_{i}=(s_{i},t_{i},d_{i})}
2119:
2099:
2067:
2057:
2046:
2040:
2007:
1979:
1969:
1958:
1907:
1901:
1867:
1865:
1809:
1802:minimum cost multi-commodity flow problem
1754:
1749:
1720:
1690:
1684:
1663:
1620:
1614:
1567:
1539:
1529:
1518:
1511:
1488:
1447:
1412:
1365:
1352:
1324:
1308:
1289:
1261:
1256:
1221:
1211:(4) Flow conservation at the destination:
1182:
1163:
1135:
1113:
1100:
1072:
1067:
1032:
1002:
989:
964:
936:
908:
880:
852:
847:
812:
789:
741:
713:
703:
692:
687:
658:
595:
590:
588:
534:
529:
527:
496:
494:
475:
473:
437:
432:
430:
409:
404:
402:
383:
381:
352:
347:
345:
324:
319:
317:
293:
280:
267:
251:
246:
244:
223:
204:
191:
185:
166:
164:
130:
128:
90:
56:
54:
18:Minimum cost multi-commodity flow problem
232:{\displaystyle K_{1},K_{2},\dots ,K_{k}}
2414:Algorithmic Nuggets in Content Delivery
2229:
782:(2) Flow conservation on transit nodes:
637:{\displaystyle \,f_{i}(u,v)\in \{0,1\}}
2359:
2187:, or through (typically much faster)
2094:(in which there is merely one source
7:
2076:{\displaystyle \sum _{i=1}^{k}d_{i}}
2033:maximum multi-commodity flow problem
1022:(3) Flow conservation at the source:
2256:(PhD). Carnegie Mellon University.
1400:Corresponding optimization problems
1853:{\displaystyle a(u,v)\cdot f(u,v)}
1722:
1223:
1034:
974:
971:
968:
965:
814:
660:
27:Network flow problem (mathematics)
25:
2147:Routing and wavelength assignment
804:is the same that exits the node.
576:{\displaystyle \,f_{i}(u,v)\in }
978:
963:
2217:Software solving the problem:
1997:
1985:
1951:
1939:
1920:
1908:
1880:
1868:
1847:
1835:
1826:
1814:
1784:
1772:
1737:
1725:
1660:
1656:
1644:
1638:
1590:
1578:
1557:
1545:
1505:
1493:
1461:
1449:
1429:
1417:
1377:
1358:
1337:
1325:
1314:
1295:
1274:
1262:
1188:
1169:
1148:
1136:
1125:
1106:
1085:
1073:
954:
942:
921:
909:
898:
886:
865:
853:
765:
753:
731:
719:
675:
663:
613:
601:
570:
558:
552:
540:
509:
497:
455:
443:
299:
260:
146:
134:
104:
92:
72:
60:
1:
1893:. You then need to minimize
468:defines the fraction of flow
461:{\displaystyle \,f_{i}(u,v)}
425:is its demand. The variable
32:multi-commodity flow problem
2456:
2381:George Karakostas (2002).
2343:Introduction to Algorithms
2086:Relation to other problems
1473:{\displaystyle (u,v)\in E}
116:{\displaystyle (u,v)\in E}
2277:SIAM Journal on Computing
2252:Koes, David Ryan (2009).
2092:minimum cost flow problem
152:{\displaystyle \,c(u,v)}
78:{\displaystyle \,G(V,E)}
2151:optical burst switching
1886:{\displaystyle \,(u,v)}
1705:{\displaystyle U_{max}}
515:{\displaystyle \,(u,v)}
418:{\displaystyle \,d_{i}}
361:{\displaystyle \,t_{i}}
333:{\displaystyle \,s_{i}}
2128:
2108:
2077:
2062:
2022:
1974:
1887:
1860:for sending a flow on
1854:
1791:
1706:
1673:
1600:
1534:
1474:
1436:
1435:{\displaystyle U(u,v)}
1390:
1201:
1012:
798:
772:
708:
638:
577:
516:
483:
462:
419:
391:
362:
334:
306:
233:
174:
153:
117:
79:
2129:
2109:
2078:
2042:
2023:
1954:
1888:
1855:
1792:
1707:
1674:
1601:
1514:
1475:
1437:
1391:
1202:
1013:
799:
773:
688:
639:
578:
517:
484:
463:
420:
392:
363:
335:
307:
234:
175:
154:
118:
80:
2440:NP-complete problems
2435:Network flow problem
2330:Charles E. Leiserson
2304:10.1109/SFCS.1975.21
2298:. pp. 184–193.
2283:(4). SIAM: 691–703.
2178:strongly NP-complete
2118:
2098:
2039:
1900:
1864:
1808:
1719:
1683:
1613:
1487:
1446:
1411:
1220:
1031:
811:
788:
657:
587:
526:
493:
472:
429:
401:
380:
344:
316:
243:
184:
163:
127:
89:
53:
36:network flow problem
2161:Register allocation
2136:circulation problem
2134:). Variants of the
482:{\displaystyle \,i}
390:{\displaystyle \,i}
173:{\displaystyle \,k}
2206:External resources
2185:linear programming
2124:
2104:
2073:
2018:
1930:
1883:
1850:
1804:, there is a cost
1787:
1702:
1669:
1637:
1596:
1470:
1432:
1386:
1347:
1284:
1197:
1158:
1095:
1008:
931:
875:
794:
768:
648:(1) Link capacity:
634:
573:
512:
479:
458:
415:
387:
358:
330:
302:
229:
170:
149:
113:
75:
2353:978-0-262-03384-8
2127:{\displaystyle t}
2107:{\displaystyle s}
1903:
1616:
1594:
1320:
1257:
1131:
1068:
904:
848:
797:{\displaystyle u}
16:(Redirected from
2447:
2417:
2411:
2405:
2404:
2378:
2372:
2371:
2365:
2357:
2334:Ronald L. Rivest
2326:Thomas H. Cormen
2322:
2316:
2315:
2292:
2272:
2266:
2265:
2249:
2243:
2242:
2241:. Prentice Hall.
2234:
2180:in this case).
2133:
2131:
2130:
2125:
2113:
2111:
2110:
2105:
2082:
2080:
2079:
2074:
2072:
2071:
2061:
2056:
2027:
2025:
2024:
2019:
2017:
2013:
2012:
2011:
1984:
1983:
1973:
1968:
1929:
1892:
1890:
1889:
1884:
1859:
1857:
1856:
1851:
1796:
1794:
1793:
1788:
1765:
1764:
1711:
1709:
1708:
1703:
1701:
1700:
1678:
1676:
1675:
1670:
1668:
1667:
1636:
1605:
1603:
1602:
1597:
1595:
1593:
1573:
1572:
1571:
1544:
1543:
1533:
1528:
1512:
1479:
1477:
1476:
1471:
1441:
1439:
1438:
1433:
1395:
1393:
1392:
1387:
1370:
1369:
1357:
1356:
1346:
1313:
1312:
1294:
1293:
1283:
1206:
1204:
1203:
1198:
1187:
1186:
1168:
1167:
1157:
1118:
1117:
1105:
1104:
1094:
1017:
1015:
1014:
1009:
1007:
1006:
994:
993:
977:
941:
940:
930:
885:
884:
874:
803:
801:
800:
795:
777:
775:
774:
769:
746:
745:
718:
717:
707:
702:
643:
641:
640:
635:
600:
599:
582:
580:
579:
574:
539:
538:
521:
519:
518:
513:
488:
486:
485:
480:
467:
465:
464:
459:
442:
441:
424:
422:
421:
416:
414:
413:
396:
394:
393:
388:
367:
365:
364:
359:
357:
356:
339:
337:
336:
331:
329:
328:
311:
309:
308:
303:
298:
297:
285:
284:
272:
271:
256:
255:
238:
236:
235:
230:
228:
227:
209:
208:
196:
195:
179:
177:
176:
171:
158:
156:
155:
150:
122:
120:
119:
114:
84:
82:
81:
76:
21:
2455:
2454:
2450:
2449:
2448:
2446:
2445:
2444:
2425:
2424:
2420:
2412:
2408:
2401:
2380:
2379:
2375:
2358:
2354:
2324:
2323:
2319:
2293:
2289:10.1137/0205048
2274:
2273:
2269:
2251:
2250:
2246:
2236:
2235:
2231:
2227:
2208:
2200:
2194:
2170:
2155:Optical Network
2144:
2116:
2115:
2096:
2095:
2088:
2063:
2037:
2036:
2003:
1975:
1935:
1931:
1898:
1897:
1862:
1861:
1806:
1805:
1750:
1717:
1716:
1686:
1681:
1680:
1659:
1611:
1610:
1574:
1563:
1535:
1513:
1485:
1484:
1480:is even, where
1444:
1443:
1409:
1408:
1402:
1361:
1348:
1304:
1285:
1218:
1217:
1178:
1159:
1109:
1096:
1029:
1028:
998:
985:
932:
876:
809:
808:
786:
785:
737:
709:
655:
654:
591:
585:
584:
530:
524:
523:
491:
490:
470:
469:
433:
427:
426:
405:
399:
398:
378:
377:
348:
342:
341:
320:
314:
313:
289:
276:
263:
247:
241:
240:
219:
200:
187:
182:
181:
161:
160:
125:
124:
87:
86:
51:
50:
44:
28:
23:
22:
15:
12:
11:
5:
2453:
2451:
2443:
2442:
2437:
2427:
2426:
2419:
2418:
2406:
2399:
2373:
2352:
2340:(2009). "29".
2338:Clifford Stein
2317:
2267:
2244:
2228:
2226:
2223:
2222:
2221:
2215:
2207:
2204:
2199:
2196:
2169:
2166:
2143:
2140:
2123:
2103:
2087:
2084:
2070:
2066:
2060:
2055:
2052:
2049:
2045:
2029:
2028:
2016:
2010:
2006:
2002:
1999:
1996:
1993:
1990:
1987:
1982:
1978:
1972:
1967:
1964:
1961:
1957:
1953:
1950:
1947:
1944:
1941:
1938:
1934:
1928:
1925:
1922:
1919:
1916:
1913:
1910:
1906:
1882:
1879:
1876:
1873:
1870:
1849:
1846:
1843:
1840:
1837:
1834:
1831:
1828:
1825:
1822:
1819:
1816:
1813:
1798:
1797:
1786:
1783:
1780:
1777:
1774:
1771:
1768:
1763:
1760:
1757:
1753:
1748:
1745:
1742:
1739:
1736:
1733:
1730:
1727:
1724:
1699:
1696:
1693:
1689:
1666:
1662:
1658:
1655:
1652:
1649:
1646:
1643:
1640:
1635:
1632:
1629:
1626:
1623:
1619:
1607:
1606:
1592:
1589:
1586:
1583:
1580:
1577:
1570:
1566:
1562:
1559:
1556:
1553:
1550:
1547:
1542:
1538:
1532:
1527:
1524:
1521:
1517:
1510:
1507:
1504:
1501:
1498:
1495:
1492:
1469:
1466:
1463:
1460:
1457:
1454:
1451:
1431:
1428:
1425:
1422:
1419:
1416:
1405:Load balancing
1401:
1398:
1397:
1396:
1385:
1382:
1379:
1376:
1373:
1368:
1364:
1360:
1355:
1351:
1345:
1342:
1339:
1336:
1333:
1330:
1327:
1323:
1319:
1316:
1311:
1307:
1303:
1300:
1297:
1292:
1288:
1282:
1279:
1276:
1273:
1270:
1267:
1264:
1260:
1255:
1252:
1249:
1246:
1243:
1240:
1237:
1234:
1231:
1228:
1225:
1208:
1207:
1196:
1193:
1190:
1185:
1181:
1177:
1174:
1171:
1166:
1162:
1156:
1153:
1150:
1147:
1144:
1141:
1138:
1134:
1130:
1127:
1124:
1121:
1116:
1112:
1108:
1103:
1099:
1093:
1090:
1087:
1084:
1081:
1078:
1075:
1071:
1066:
1063:
1060:
1057:
1054:
1051:
1048:
1045:
1042:
1039:
1036:
1019:
1018:
1005:
1001:
997:
992:
988:
984:
981:
976:
973:
970:
967:
962:
959:
956:
953:
950:
947:
944:
939:
935:
929:
926:
923:
920:
917:
914:
911:
907:
903:
900:
897:
894:
891:
888:
883:
879:
873:
870:
867:
864:
861:
858:
855:
851:
846:
843:
840:
837:
834:
831:
828:
825:
822:
819:
816:
793:
779:
778:
767:
764:
761:
758:
755:
752:
749:
744:
740:
736:
733:
730:
727:
724:
721:
716:
712:
706:
701:
698:
695:
691:
686:
683:
680:
677:
674:
671:
668:
665:
662:
633:
630:
627:
624:
621:
618:
615:
612:
609:
606:
603:
598:
594:
572:
569:
566:
563:
560:
557:
554:
551:
548:
545:
542:
537:
533:
511:
508:
505:
502:
499:
478:
457:
454:
451:
448:
445:
440:
436:
412:
408:
386:
355:
351:
327:
323:
301:
296:
292:
288:
283:
279:
275:
270:
266:
262:
259:
254:
250:
226:
222:
218:
215:
212:
207:
203:
199:
194:
190:
169:
148:
145:
142:
139:
136:
133:
112:
109:
106:
103:
100:
97:
94:
74:
71:
68:
65:
62:
59:
43:
40:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
2452:
2441:
2438:
2436:
2433:
2432:
2430:
2423:
2415:
2410:
2407:
2402:
2400:0-89871-513-X
2396:
2392:
2388:
2384:
2377:
2374:
2369:
2363:
2355:
2349:
2345:
2344:
2339:
2335:
2331:
2327:
2321:
2318:
2313:
2309:
2305:
2301:
2297:
2290:
2286:
2282:
2278:
2271:
2268:
2263:
2259:
2255:
2248:
2245:
2240:
2233:
2230:
2224:
2220:
2216:
2214:
2210:
2209:
2205:
2203:
2197:
2195:
2192:
2190:
2186:
2181:
2179:
2175:
2167:
2165:
2162:
2158:
2156:
2152:
2148:
2141:
2139:
2137:
2121:
2114:and one sink
2101:
2093:
2085:
2083:
2068:
2064:
2058:
2053:
2050:
2047:
2043:
2034:
2014:
2008:
2004:
2000:
1994:
1991:
1988:
1980:
1976:
1970:
1965:
1962:
1959:
1955:
1948:
1945:
1942:
1936:
1932:
1926:
1923:
1917:
1914:
1911:
1904:
1896:
1895:
1894:
1877:
1874:
1871:
1844:
1841:
1838:
1832:
1829:
1823:
1820:
1817:
1811:
1803:
1781:
1778:
1775:
1769:
1766:
1761:
1758:
1755:
1751:
1746:
1743:
1740:
1734:
1731:
1728:
1715:
1714:
1713:
1697:
1694:
1691:
1687:
1664:
1653:
1650:
1647:
1641:
1633:
1630:
1627:
1624:
1621:
1617:
1587:
1584:
1581:
1575:
1568:
1564:
1560:
1554:
1551:
1548:
1540:
1536:
1530:
1525:
1522:
1519:
1515:
1508:
1502:
1499:
1496:
1490:
1483:
1482:
1481:
1467:
1464:
1458:
1455:
1452:
1442:of all links
1426:
1423:
1420:
1414:
1406:
1399:
1383:
1380:
1374:
1371:
1366:
1362:
1353:
1349:
1343:
1340:
1334:
1331:
1328:
1321:
1317:
1309:
1305:
1301:
1298:
1290:
1286:
1280:
1277:
1271:
1268:
1265:
1258:
1253:
1247:
1244:
1241:
1238:
1235:
1229:
1226:
1216:
1215:
1214:
1212:
1194:
1191:
1183:
1179:
1175:
1172:
1164:
1160:
1154:
1151:
1145:
1142:
1139:
1132:
1128:
1122:
1119:
1114:
1110:
1101:
1097:
1091:
1088:
1082:
1079:
1076:
1069:
1064:
1058:
1055:
1052:
1049:
1046:
1040:
1037:
1027:
1026:
1025:
1023:
1003:
999:
995:
990:
986:
982:
979:
960:
957:
951:
948:
945:
937:
933:
927:
924:
918:
915:
912:
905:
901:
895:
892:
889:
881:
877:
871:
868:
862:
859:
856:
849:
844:
838:
835:
832:
829:
826:
820:
817:
807:
806:
805:
791:
783:
762:
759:
756:
750:
747:
742:
738:
734:
728:
725:
722:
714:
710:
704:
699:
696:
693:
689:
684:
681:
678:
672:
669:
666:
653:
652:
651:
649:
645:
628:
625:
622:
616:
610:
607:
604:
596:
592:
567:
564:
561:
555:
549:
546:
543:
535:
531:
506:
503:
500:
476:
452:
449:
446:
438:
434:
410:
406:
384:
376:of commodity
375:
371:
353:
349:
325:
321:
294:
290:
286:
281:
277:
273:
268:
264:
257:
252:
248:
239:, defined by
224:
220:
216:
213:
210:
205:
201:
197:
192:
188:
167:
143:
140:
137:
131:
123:has capacity
110:
107:
101:
98:
95:
85:, where edge
69:
66:
63:
57:
49:
41:
39:
37:
33:
19:
2421:
2409:
2386:
2376:
2342:
2320:
2295:
2280:
2276:
2270:
2253:
2247:
2238:
2232:
2201:
2198:Applications
2193:
2182:
2171:
2159:
2145:
2089:
2032:
2030:
1801:
1799:
1608:
1404:
1403:
1210:
1209:
1021:
1020:
781:
780:
647:
646:
373:
369:
180:commodities
159:. There are
48:flow network
45:
31:
29:
2416:sigcomm.org
2389:. pp.
2174:NP-complete
489:along edge
2429:Categories
2225:References
42:Definition
2362:cite book
2168:Solutions
2149:(RWA) in
2044:∑
2001:⋅
1956:∑
1924:∈
1905:∑
1830:⋅
1767:≥
1741:∈
1723:∀
1631:∈
1618:∑
1561:⋅
1516:∑
1465:∈
1341:∈
1322:∑
1318:−
1278:∈
1259:∑
1242:…
1230:∈
1224:∀
1152:∈
1133:∑
1129:−
1089:∈
1070:∑
1053:…
1041:∈
1035:∀
983:≠
925:∈
906:∑
902:−
869:∈
850:∑
833:…
821:∈
815:∀
748:≤
735:⋅
690:∑
679:∈
661:∀
617:∈
556:∈
214:…
108:∈
2312:18449466
2262:26416771
1712:, where
522:, where
312:, where
46:Given a
2391:166–173
2031:In the
1800:In the
368:is the
2397:
2350:
2336:, and
2310:
2260:
397:, and
370:source
2308:S2CID
2258:S2CID
2142:Usage
34:is a
2395:ISBN
2368:link
2348:ISBN
374:sink
372:and
340:and
30:The
2300:doi
2285:doi
2153:of
2431::
2393:.
2385:.
2364:}}
2360:{{
2332:,
2328:,
2306:.
2279:.
2191:.
2403:.
2370:)
2356:.
2314:.
2302::
2291:.
2287::
2281:5
2264:.
2122:t
2102:s
2069:i
2065:d
2059:k
2054:1
2051:=
2048:i
2015:)
2009:i
2005:d
1998:)
1995:v
1992:,
1989:u
1986:(
1981:i
1977:f
1971:k
1966:1
1963:=
1960:i
1952:)
1949:v
1946:,
1943:u
1940:(
1937:a
1933:(
1927:E
1921:)
1918:v
1915:,
1912:u
1909:(
1881:)
1878:v
1875:,
1872:u
1869:(
1848:)
1845:v
1842:,
1839:u
1836:(
1833:f
1827:)
1824:v
1821:,
1818:u
1815:(
1812:a
1785:)
1782:v
1779:,
1776:u
1773:(
1770:U
1762:x
1759:a
1756:m
1752:U
1747::
1744:E
1738:)
1735:v
1732:,
1729:u
1726:(
1698:x
1695:a
1692:m
1688:U
1665:2
1661:)
1657:)
1654:v
1651:,
1648:u
1645:(
1642:U
1639:(
1634:V
1628:v
1625:,
1622:u
1591:)
1588:v
1585:,
1582:u
1579:(
1576:c
1569:i
1565:d
1558:)
1555:v
1552:,
1549:u
1546:(
1541:i
1537:f
1531:k
1526:1
1523:=
1520:i
1509:=
1506:)
1503:v
1500:,
1497:u
1494:(
1491:U
1468:E
1462:)
1459:v
1456:,
1453:u
1450:(
1430:)
1427:v
1424:,
1421:u
1418:(
1415:U
1384:1
1381:=
1378:)
1375:w
1372:,
1367:i
1363:t
1359:(
1354:i
1350:f
1344:E
1338:)
1335:u
1332:,
1329:w
1326:(
1315:)
1310:i
1306:t
1302:,
1299:w
1296:(
1291:i
1287:f
1281:E
1275:)
1272:w
1269:,
1266:u
1263:(
1254::
1251:}
1248:k
1245:,
1239:,
1236:1
1233:{
1227:i
1195:1
1192:=
1189:)
1184:i
1180:s
1176:,
1173:w
1170:(
1165:i
1161:f
1155:E
1149:)
1146:u
1143:,
1140:w
1137:(
1126:)
1123:w
1120:,
1115:i
1111:s
1107:(
1102:i
1098:f
1092:E
1086:)
1083:w
1080:,
1077:u
1074:(
1065::
1062:}
1059:k
1056:,
1050:,
1047:1
1044:{
1038:i
1004:i
1000:t
996:,
991:i
987:s
980:u
975:n
972:e
969:h
966:w
961:0
958:=
955:)
952:u
949:,
946:w
943:(
938:i
934:f
928:E
922:)
919:u
916:,
913:w
910:(
899:)
896:w
893:,
890:u
887:(
882:i
878:f
872:E
866:)
863:w
860:,
857:u
854:(
845::
842:}
839:k
836:,
830:,
827:1
824:{
818:i
792:u
766:)
763:v
760:,
757:u
754:(
751:c
743:i
739:d
732:)
729:v
726:,
723:u
720:(
715:i
711:f
705:k
700:1
697:=
694:i
685::
682:E
676:)
673:v
670:,
667:u
664:(
632:}
629:1
626:,
623:0
620:{
614:)
611:v
608:,
605:u
602:(
597:i
593:f
571:]
568:1
565:,
562:0
559:[
553:)
550:v
547:,
544:u
541:(
536:i
532:f
510:)
507:v
504:,
501:u
498:(
477:i
456:)
453:v
450:,
447:u
444:(
439:i
435:f
411:i
407:d
385:i
354:i
350:t
326:i
322:s
300:)
295:i
291:d
287:,
282:i
278:t
274:,
269:i
265:s
261:(
258:=
253:i
249:K
225:k
221:K
217:,
211:,
206:2
202:K
198:,
193:1
189:K
168:k
147:)
144:v
141:,
138:u
135:(
132:c
111:E
105:)
102:v
99:,
96:u
93:(
73:)
70:E
67:,
64:V
61:(
58:G
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.