{"entities":{"Q1194345":{"pageid":1205094,"ns":120,"title":"Item:Q1194345","lastrevid":69863247,"modified":"2026-04-13T10:50:52Z","type":"item","id":"Q1194345","labels":{"en":{"language":"en","value":"Maximum concurrent flows and minimum cuts"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 64259"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194345$5CBC68A6-25CD-446E-A31E-0E215C0B08FD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"103083707b9eb0f43c250484ce8f43cff61034a3","datavalue":{"value":{"text":"Maximum concurrent flows and minimum cuts","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1194345$34A54CA9-38C0-47AB-8995-BF1AB3B3CD11","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1dcc2840adc823135bca612b53b69e77fc5a7261","datavalue":{"value":"0762.90024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1194345$A2D40A8A-9A1A-4F81-8FC9-AEA90098DD5E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0fcbdd06798d0f395a79ffd27e7b9736601e88fe","datavalue":{"value":"10.1007/BF01758845","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1194345$A75A29FA-C1C4-46C7-804E-B8611D223D44","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f5b17683dd2eedd3f1d821a1087aa218b2b31d17","datavalue":{"value":{"entity-type":"item","numeric-id":1160451,"id":"Q1160451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194345$2CAC8711-6B81-4364-957E-AE08A465DC47","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194345$2D2F7DE5-84A0-4D6D-8259-4A2AF05054FA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5fd62271fe98c7ff9916cafed51cf35315eeeb31","datavalue":{"value":{"time":"+1992-09-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1194345$3CC709A8-04BA-4474-AB53-7F8DD4F6C7C1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7f8a8fdfece5a30618f1a95450030f78459e4c22","datavalue":{"value":"Let \\(f(X,\\overline X)\\) be any symmetric function representing the cost of cuts \\((X,\\overline X)\\) in a network. The authors show the \\(n-1\\) minimum cost cuts are always sufficient to separate all pairs of nodes, and they propose an algorithm to find the set of these essential cuts with \\(n-1\\) oracle calls [improving the result of \\textit{R. Hassin}, Math. Oper. Res. 13, No. 4, 535-542 (1988; Zbl 0667.90034)]. The authors also consider \\(k\\)-way partitions, and, using linear programming techniques, prove the following result (independently obtained with combinatorial arguments by \\textit{F. Shahrokhi} and \\textit{D. W. Matula} [``The maximum concurrent flow problem'', Tech. Rep., New Mexico Tech. (1986)]): If the saturated arcs in a multicommodity flow problem form a \\(k\\)-way partition, \\(k\\leq 4\\), then the \\(k\\)-way partition contains a two-way partition, which is the minimum weight sparsest cut.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1194345$5885FA12-7B66-40E0-9879-EBFCCC2E7FA3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1194345$81DEBAC9-0F2B-4186-8ACD-60A8BF804FE8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c90462bd2d67401e55d4ea5daffa6d1a098773e0","datavalue":{"value":"64259","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1194345$FB800DBB-6594-4704-978A-5DA0485707DF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ebba9829db9169759419efb62d9c7b827da96ffd","datavalue":{"value":"minimum cost cuts","type":"string"},"datatype":"string"},"type":"statement","id":"Q1194345$8D8563A5-2A04-4EE4-B6CD-CEA6C0BFAFE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8bdb5c233b962ae44142587eaa9aa9d0a9583825","datavalue":{"value":"\\(k\\)-way partitions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1194345$D096E26D-B761-457D-9EBC-E207D0DDB0EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c51cd2418e1a453fca7a510eacf3309373b3a2f8","datavalue":{"value":"multicommodity flow","type":"string"},"datatype":"string"},"type":"statement","id":"Q1194345$6EED061B-9C27-4567-9F6D-02A863D13FC6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6b6816c3de7983b793bf4c42808a1cb69f396cb6","datavalue":{"value":{"entity-type":"item","numeric-id":342501,"id":"Q342501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194345$8CC1D382-D754-433D-92D9-D0FED9CFF73A","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194345$AB90903D-4923-4B12-985D-B10A40E29B19","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e4bd04b587c0758390f2e0ced121ecf83881a76","datavalue":{"value":{"entity-type":"item","numeric-id":3323698,"id":"Q3323698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194345$A87AD89C-1576-4943-ACAB-88E1527C248B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9df03d940bbd4c025d80e4f6d96f2a49bffb4fd","datavalue":{"value":{"entity-type":"item","numeric-id":3237973,"id":"Q3237973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194345$856B251A-7F0A-49D3-97E4-298F14ED7533","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"058a5d0355017c631c2ff0b408eb3f7a837be9b2","datavalue":{"value":{"entity-type":"item","numeric-id":2778592,"id":"Q2778592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194345$470E22DD-0138-4183-8AD7-9A5C4DAA2365","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1744afac4c45f065c4a9c50861775137377ee1b0","datavalue":{"value":{"entity-type":"item","numeric-id":3849459,"id":"Q3849459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194345$B000944E-9DF1-42FC-9277-78AAF0CF3F43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"107ff0bb6ad0a8ba066f522260b8ee73c0a513e6","datavalue":{"value":{"entity-type":"item","numeric-id":1085773,"id":"Q1085773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194345$CC9251BA-E1FA-4FBF-B4A2-7FAFCDE9A06D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db40a3df91e73e367d6849dc18f0af001f226654","datavalue":{"value":{"entity-type":"item","numeric-id":3820346,"id":"Q3820346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194345$8CE8DA13-6965-402A-AE2A-93C15693C45F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c571b640c1516f4ca2b62caa77bbdebe8bf825d0","datavalue":{"value":{"entity-type":"item","numeric-id":5736116,"id":"Q5736116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194345$B0C6984E-74A0-404B-8A75-9E80681CCFFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4072c92c1cacce424af36eb2f319fe40241de9fd","datavalue":{"value":{"entity-type":"item","numeric-id":3885549,"id":"Q3885549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194345$A09CE192-2A5A-4323-A26E-5CC915DDE762","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a44f31abbdd4dc84e5f661896a7812e44411ddf","datavalue":{"value":{"entity-type":"item","numeric-id":4100093,"id":"Q4100093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194345$D6CF114F-FFC4-4A7F-A2C9-5C0371E49E71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02221e1c0a69913c7a96c3912f027efbe9cb7d68","datavalue":{"value":{"entity-type":"item","numeric-id":1080357,"id":"Q1080357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194345$5E249DCA-7493-4B95-AA97-2F65759354DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58b75e823d7d97463bea3f1b237ecc88aaa499fb","datavalue":{"value":{"entity-type":"item","numeric-id":3474283,"id":"Q3474283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194345$4E3C127F-2C8A-4FB3-9674-A174B1367B85","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a1676870365e5e73eb6a0f878e3934b63e464704","datavalue":{"value":"https://doi.org/10.1007/bf01758845","type":"string"},"datatype":"url"},"type":"statement","id":"Q1194345$06FA6338-3465-4675-83D9-9A2ECD4A4729","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3a1dd2496c3ef590a2febc0426ea994010812b6b","datavalue":{"value":"W2001646664","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1194345$7D198D52-CBAB-4D09-B62E-ECDC05A3CC38","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5d9f654bb074d2056e56a16775613b99f9152f8","datavalue":{"value":{"entity-type":"item","numeric-id":2806718,"id":"Q2806718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9159e33e27e94e54186e12ae6ea4b52c76278882","datavalue":{"value":{"amount":"+0.8195443153381348","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1194345$49E4E77D-4824-4BBF-A908-029A7EAD9A0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49ac8ed30502b2d5a77cd647aa798e83b48127c8","datavalue":{"value":{"entity-type":"item","numeric-id":4877516,"id":"Q4877516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a858d56f16c92eabfd8896ec6c716900f3a3fc47","datavalue":{"value":{"amount":"+0.8079189658164978","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1194345$92EE551C-884C-4C00-9FE0-9818652EEDFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"044fafada47f9adcc52bdf19c7ab5afae86c20fa","datavalue":{"value":{"entity-type":"item","numeric-id":4645919,"id":"Q4645919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ebc82e830f4491989fd4e6354f856c5da2389698","datavalue":{"value":{"amount":"+0.8073256015777588","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1194345$9E08E282-C026-4FAF-AAAF-4F87729D5170","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0741cc734b788e5c52e709a07e0c9a57a44df3b4","datavalue":{"value":{"entity-type":"item","numeric-id":2706189,"id":"Q2706189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e48ce2308b19f89444bd1fb416bc97a3cdae8e2d","datavalue":{"value":{"amount":"+0.8034251928329468","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1194345$F0E6DDEC-D4E7-48B6-89DB-40156AD787CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63ffed824247df3a0a2f4e9dae328b7bcb8e4348","datavalue":{"value":{"entity-type":"item","numeric-id":4371680,"id":"Q4371680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e48ce2308b19f89444bd1fb416bc97a3cdae8e2d","datavalue":{"value":{"amount":"+0.8034251928329468","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1194345$CDFCCAD7-E295-4B4D-AF5F-FE080AA77B2D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Maximum concurrent flows and minimum cuts","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Maximum_concurrent_flows_and_minimum_cuts"}}}}}