{"entities":{"Q1178222":{"pageid":1188971,"ns":120,"title":"Item:Q1178222","lastrevid":77969111,"modified":"2026-05-06T10:28:37Z","type":"item","id":"Q1178222","labels":{"en":{"language":"en","value":"Processor-efficient implementation of a maximum flow algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 23336"}},"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":"Q1178222$3757F433-B818-4A8F-A2CA-C9551FD21F22","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f4bcadb65a7895b2b892638872bbc68ef9b28e17","datavalue":{"value":{"text":"Processor-efficient implementation of a maximum flow algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1178222$D75B0429-6FD1-480B-B55E-0B02306F7C38","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"794827b2c0b0ed0a8f3870c63404841454982a2c","datavalue":{"value":"0754.90024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178222$6DA1567C-8770-4C57-9937-8FB54A1B9B6F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bc1f7c2ff6e23c66506a6dd713f7ac41a580318b","datavalue":{"value":"10.1016/0020-0190(91)90097-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178222$0359D641-EECC-4139-B667-64A0396F62C6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"292ee0ed60d229834f4ba04d9e68598fca7e73c5","datavalue":{"value":{"entity-type":"item","numeric-id":536068,"id":"Q536068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178222$BF540DB8-E581-49F1-8DB9-F5CFEFC87EB1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178222$A9FA0CAF-635F-4F64-B1CE-AEB2D11E9726","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1178222$38DB7020-6ED3-4938-9BE4-BDF65117FEAC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d706ebfd646f50f4219ad679494de3501f24e3ee","datavalue":{"value":"The push-relabel method was developed by the author and \\textit{R. E. Tarjan} [J. Assoc. Comput. Mach. 35, No. 4, 921-940 (1988; Zbl 0661.90031)]. The Maximum Distance Discharge (MDD) algorithm is another variation of the generic push-relabel method.   In this paper the author describes two parallel implementations of the MDD algorithm. Both implementations use \\(p=O(\\sqrt m)\\) processors. The first implementation runs in \\(O(n^ 2\\log(2m/n+p)(\\sqrt m/p))\\) time using \\(O(m+n \\log n)\\) memory. The second one uses \\(O(m+n)\\) amount of memory and runs in \\(O(n^ 2\\log n(\\sqrt m/p))\\) time (\\(n\\) and \\(m\\) denote the number of vertices and the number of arcs in the input network). Both implementations achieve near-optimal speedup for up to a linear number of processors.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178222$3ED8292F-A79B-4F02-9290-A171852716DD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178222$2F0D4D5A-F217-48D8-8C38-4FAC86D05325","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178222$697F87D9-C6FC-4360-898F-9D2A64DED705","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178222$BE20DE55-2A6D-4763-9266-6874E9E6D261","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178222$A9499DF2-8DF7-419B-A191-6AD382E4B097","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178222$7558AB0F-0F40-475D-A25C-BB7BD684782D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a7edc01538ef78e7e423d9c49f622de0faa5a14","datavalue":{"value":"65Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178222$D896EB0F-D3E7-4473-A4BF-482D5204BDEF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"af30d08ed3c22f5d672d6fa56ec13850f1352817","datavalue":{"value":"23336","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178222$C0EF62F9-6147-4A72-BF53-5E16254CAE64","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"230e52be1850c8fd355b8931302abdc64643c943","datavalue":{"value":"push-relable method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178222$8AA1FD20-734F-4478-B044-9AFB2BDEB403","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6cc00fc5da9f754a101ec4177be59f5f3897c983","datavalue":{"value":"Maximum Distance Discharge","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178222$9973F6FE-D0B7-4594-92C8-7E129B47EF6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d9e67d56bed7984f9f62b29a09f15e1f76e2848","datavalue":{"value":"parallel implementations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178222$A763C9D6-44CF-4E7C-B212-4F180447BEB5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2054ab6afcff86345461ab192c34bfbef6c7b38d","datavalue":{"value":{"entity-type":"item","numeric-id":261055,"id":"Q261055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178222$4792DDCA-9C47-406A-86D6-877BA5A5A75C","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":"Q1178222$B5F31E60-1C53-4409-B101-2BD708CB2502","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"730d64c8c4932bcfa34915310c3f39420a535351","datavalue":{"value":"https://doi.org/10.1016/0020-0190(91)90097-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1178222$443E1F17-B727-4D5F-A70E-8035CF844DE3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"457b70989906d20de29bbfa8fc600c9d044e60a1","datavalue":{"value":"W2025830455","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178222$DFEA6138-BBB8-4511-B681-71ADCD796E60","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"44dd9822dafe2e334b2b0ad62fd4d159688b8ea3","datavalue":{"value":{"entity-type":"item","numeric-id":3033534,"id":"Q3033534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178222$3FC80722-C483-4362-8F0E-BD7ACE325BBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4077de5ad21c6b78a25ec43c56119974484a370","datavalue":{"value":{"entity-type":"item","numeric-id":4401551,"id":"Q4401551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178222$2D922F2C-B775-4A0B-91FF-5F569EBCA3A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"998c605d14189cad9bad0b168c53842adb028962","datavalue":{"value":{"entity-type":"item","numeric-id":3034814,"id":"Q3034814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178222$96E10F66-1BB3-486C-ACC9-10D9FB244478","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cb1ec0d7ce822fb5941419bafd4a3f4e7cd71cd","datavalue":{"value":{"entity-type":"item","numeric-id":3753489,"id":"Q3753489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178222$BD1EA0ED-18FD-416D-9B21-C7B20FCE68A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cb2ca458acea0e3632727170dcd237e7765fa59","datavalue":{"value":{"entity-type":"item","numeric-id":5514188,"id":"Q5514188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178222$A3A342BF-5874-4EBE-947D-04EC59E2F5A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2628ffb9e59aa19553582ac944ed7dc8d827a3a","datavalue":{"value":{"entity-type":"item","numeric-id":5402548,"id":"Q5402548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178222$487A1529-1F1B-4B83-90BD-E53F5CC66D59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f9f7fa55796e4289729d35a451bba230d60cf4e","datavalue":{"value":{"entity-type":"item","numeric-id":3352816,"id":"Q3352816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178222$D8C4D6B7-1DF5-43C0-A136-4F6B518A8D2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c858b89b9774cab823f151be95554a91f314d3ef","datavalue":{"value":{"entity-type":"item","numeric-id":1165000,"id":"Q1165000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178222$4822E6DF-918D-4DF5-A699-5E06448FD1C3","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":"Q1178222$D1BFB321-3A74-43AC-92ED-70D81A7CAF88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"508894c78bd2770d073dbe57a0316a7e71f6bc30","datavalue":{"value":{"entity-type":"item","numeric-id":3890136,"id":"Q3890136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178222$F44C9988-36DC-48D8-8778-8D1B9C9D4255","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6be860c0ba286363a5f3801cd9493726dc65ab2","datavalue":{"value":{"entity-type":"item","numeric-id":3670587,"id":"Q3670587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178222$5B0195BC-0F12-4B18-8FD6-863EE949D4A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ae333fe863c45379735532833d5e0fa841f6a89","datavalue":{"value":{"entity-type":"item","numeric-id":3922148,"id":"Q3922148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178222$1E52D75D-46A8-4E6E-8CC8-E6800EF6A240","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":"Q1178222$C515C2CA-6699-4A20-B476-B235BCAB4B30","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ecb50b8816f988af3bd528be36c01d76af9c79a","datavalue":{"value":{"entity-type":"item","numeric-id":4283437,"id":"Q4283437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13af4d9dd03c535edef31dac78611f664f05d904","datavalue":{"value":{"amount":"+0.8327100276947021","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":"Q1178222$FCDB8FA5-369B-4A02-88B0-68D3A1A22CE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ed0c395e2f0c6317362a762087833b4a9ef5ddb","datavalue":{"value":{"entity-type":"item","numeric-id":5101413,"id":"Q5101413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b9fb5c368f543d4a57a1f8ed42df26485869ead","datavalue":{"value":{"amount":"+0.8254209756851196","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":"Q1178222$A12BF259-3CE8-4AE2-AF7D-88FE79B1CB6D","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":"6caac332361f3c7de25273a2dacb953074c9ef5e","datavalue":{"value":{"amount":"+0.8253920078277588","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":"Q1178222$E7F43FD6-473D-4208-A369-0B1302D2943C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"549199fbabde6d7cd8f3e7d329247cbb41f00a1d","datavalue":{"value":{"entity-type":"item","numeric-id":3452773,"id":"Q3452773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"860ce57bbb5f2e2005bb724022205dff866cad79","datavalue":{"value":{"amount":"+0.8244467973709106","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":"Q1178222$A18FEBC2-AE60-493B-BA48-056DD7C5F3E4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Processor-efficient implementation of a maximum flow algorithm","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Processor-efficient_implementation_of_a_maximum_flow_algorithm"}}}}}