{"entities":{"Q795064":{"pageid":796912,"ns":120,"title":"Item:Q795064","lastrevid":48717127,"modified":"2026-01-05T17:07:39Z","type":"item","id":"Q795064","labels":{"en":{"language":"en","value":"A simple version of Karzanov's blocking flow algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3861217"}},"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":"Q795064$AD1BF8E4-746B-4ABA-B5F9-7079659274A5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cd9b799a4db911aed0d35bf082dfc904ea414f0a","datavalue":{"value":{"text":"A simple version of Karzanov's blocking flow algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q795064$FDAB1C18-10B2-48EF-B377-A43347A29912","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f4b2f4f0be5e58afbd4849c926435aca915976a1","datavalue":{"value":"0542.05057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795064$59F74652-FC2C-4AC0-849B-2DF990B4DADF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ae0f12e765c5ae1498aa00b7fcc3706aa762f32d","datavalue":{"value":"10.1016/0167-6377(84)90076-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795064$B3FC734B-4AE4-4D30-80B1-567B2A131223","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"065c91f208b67eb2296cd8ea5272c33efd202f25","datavalue":{"value":{"entity-type":"item","numeric-id":598808,"id":"Q598808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795064$4FA4E747-FE76-4491-988E-9B2B2FBB77DE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795064$753FA1A4-19BF-4753-B479-49A94CC2F8B2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q795064$3FA8AA31-4AF6-470D-91CD-06B2AA59BEAA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6521c03f522e16ab24b4e1ff40abbf201e1b39f8","datavalue":{"value":"A network is a directed graph G with two distinguished vertices, a source s and a sink t, and a positive capacity c(v,w) on every edge [v,w]. A flow is blocking if there is a saturated edge on every path from s to t. \\textit{E. A. Dinits} [Sov. Math., Dokl. 11, 1277-1280 (1970); translation from Dokl. Akad. Nauk SSSR 194, 754-757 (1970; Zbl 0219.90046)] has shown that the classic maximum flow problem on a graph of n vertices and m edges can be reduced to a sequence of, at most n-1 so- called ''blocking flow'' problems on acyclic graphs. For dense graphs, the best time bound known for the blocking flow problem is \\(O(n^ 2)\\) [\\textit{A. V. Karzanov}, Sov. Math. Dokl. 15(1974), 434-437 (1975; Zbl 0303.90014); \\textit{V. M. Malhotra, M. P. Kumar} and \\textit{S. N. Maheshwari}, Inf. Process. Lett. 7, 277-278 (1978; Zbl 0391.90041)]. In this paper the author presents a version of Karzanov's algorithm that is easy to implement.","type":"string"},"datatype":"string"},"type":"statement","id":"Q795064$60670E4A-0C76-469F-9AE9-766E88B14345","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795064$30CB5C52-2792-4CE8-BA68-52AEBEB7E818","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9ed1e3c6cced595a05b8ae19055521b22405b78a","datavalue":{"value":"68W99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795064$F2924E22-D974-4796-BB1C-15B818B462BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795064$4DB25C72-C2BB-4EF4-B7DD-BF48C348344F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"70449e9eda852c49517ccd94c3d7dd5cb3b4def6","datavalue":{"value":"3861217","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795064$73466184-E509-428E-92CE-A8A3C384D651","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a38b11968d7cb86be0842b661cd5bdd713115f5","datavalue":{"value":"graph algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q795064$AECEAE17-11AB-4F36-BC10-B5D8F425FA9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89a532a4ba2e4e35fc77b9e8291742b44cf8b352","datavalue":{"value":"maximum flow problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q795064$57A7E50A-FE52-4B12-8351-E2EFCF249203","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c5a8b5716bc29dee4849a02abb2efc7b4cabc4b7","datavalue":{"value":{"entity-type":"item","numeric-id":328466,"id":"Q328466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795064$3228D15A-D3A9-403B-AE9C-EC9503ABC65D","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":"Q795064$69B845A3-2F63-46D5-84E5-136CD28B2B2B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5a9085447ceb4d12da6abfe5226216a3796bda93","datavalue":{"value":"https://doi.org/10.1016/0167-6377(84)90076-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q795064$E06BA908-4629-4D3B-AEC8-CDF19B4F38DC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5cdcced071981eabaebae5b7357e2f907de31716","datavalue":{"value":"W1991295190","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q795064$F3806EAD-D348-4770-BB45-EB891DB38274","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"854bf29386092635a477e0881f3f0c76f5ed2664","datavalue":{"value":{"entity-type":"item","numeric-id":5624995,"id":"Q5624995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795064$0A0BF05F-7C57-45C9-9C45-74818B84C300","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cb6d330b0ba17ea9706ff485bd2cc7e5caf6771","datavalue":{"value":{"entity-type":"item","numeric-id":3883524,"id":"Q3883524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795064$E6E8A28A-0EAC-4123-B939-31C0F68FA1F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8a169b0b8e2e347f5b3ef4a7ec8efb7c46dbe89","datavalue":{"value":{"entity-type":"item","numeric-id":1151034,"id":"Q1151034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795064$40AAB80E-F2F3-4C4C-A2A2-EAAC0D26E7C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cdd63cfd94110db141d7befeab2484a3068a6d0","datavalue":{"value":{"entity-type":"item","numeric-id":1147636,"id":"Q1147636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795064$721679C1-4248-47AD-939B-E1C6916D1DC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bec7e3ed20b3cac9dff88ebdf5372d37a1366a36","datavalue":{"value":{"entity-type":"item","numeric-id":4058442,"id":"Q4058442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795064$F186C0B2-702A-45C8-85BE-D65EE081F8B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795064$BD3BD460-0B58-46E3-85C9-1AE37AAED1F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795064$E74B6632-BED5-4C33-BB92-CC6F7E82A329","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f19ad20105c30936c93f5697cec437ce6d4a0cf","datavalue":{"value":{"entity-type":"item","numeric-id":1251587,"id":"Q1251587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795064$92A541A4-294C-4621-A436-DFCE4D6DADA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26589b0348552e2fca9722608c763f82407366f7","datavalue":{"value":{"entity-type":"item","numeric-id":3942729,"id":"Q3942729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795064$F4FDD588-82BA-46D4-9EB6-DD3108C6A846","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad66e712de02ff1b7a4cfdc9520b6373ff759106","datavalue":{"value":{"entity-type":"item","numeric-id":4050114,"id":"Q4050114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q795064$58726C5B-4B10-4CDA-870D-BA3DB0324413","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b13d004bd4aa4a1331d86b629dbf6b11b17fbb7f","datavalue":{"value":{"entity-type":"item","numeric-id":1197076,"id":"Q1197076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49152e985d10d4bbeffaf033c77648a9f8ff49a6","datavalue":{"value":{"amount":"+0.8623648881912231","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":"Q795064$E3C31D7E-AD31-4A4E-BF50-1459986F0AC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2b6c36bc5c27f2fc183f31166f78dd2f477145b","datavalue":{"value":{"entity-type":"item","numeric-id":4038695,"id":"Q4038695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6fd61193e4d1d429a48303edcb18978d7b921ad3","datavalue":{"value":{"amount":"+0.8621674180030823","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":"Q795064$644CADCC-EEFE-429E-A6A8-820460D92D61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24997ba5cb5b8b1f0285397ad582a03579fb0410","datavalue":{"value":{"entity-type":"item","numeric-id":4538163,"id":"Q4538163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d096e68f875fd65cbdb4e4eee6ff606f691ffcb","datavalue":{"value":{"amount":"+0.839748740196228","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":"Q795064$F6219528-4A7A-4051-9C0B-95451ACD2ED0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85ecce52667b43f1f266695c7770300ce62c2258","datavalue":{"value":{"entity-type":"item","numeric-id":3812009,"id":"Q3812009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c74f3e9299b8d45f6388bb99a347cd63f5b4f28","datavalue":{"value":{"amount":"+0.8315352201461792","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":"Q795064$ADE5DFC4-C30A-432B-A9C5-C322D445D1B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"370dad60581113b55257751ff8516e291f06de3b","datavalue":{"value":{"entity-type":"item","numeric-id":5691288,"id":"Q5691288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8869de8f5c07dee2adea7bcdf6a8b5ef0b088c7","datavalue":{"value":{"amount":"+0.8268407583236694","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":"Q795064$0CB620C1-4AC2-4698-8633-5F8D49EDECA8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:795064","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:795064"}}}}}