{"entities":{"Q1119019":{"pageid":1129768,"ns":120,"title":"Item:Q1119019","lastrevid":66781086,"modified":"2026-04-12T12:49:19Z","type":"item","id":"Q1119019","labels":{"en":{"language":"en","value":"The parallel complexity of finding a blocking flow in a 3-layer network"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4096778"}},"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":"Q1119019$C888E18C-CAB2-4CAB-81C2-4D69046CEB70","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"77f7f5fb1db6f5f18c3a397956bd5d331545b07e","datavalue":{"value":{"text":"The parallel complexity of finding a blocking flow in a 3-layer network","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1119019$4322EA5D-2D09-44F1-ADFD-434D9A75798A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"27babb632b05d109292fa63acb0c70eeacb54901","datavalue":{"value":"0669.68031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119019$F4C88F9F-BA2C-49E4-9D86-33988F39D9B7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d6ed5a2a7939e11c2d85ab944eb17ffe23be0647","datavalue":{"value":"10.1016/0020-0190(89)90225-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119019$6578BDD1-E6BC-4C9D-946C-B31A45F7DCF1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bde608e44ab7dcf42ab89449fee3a91928536bb2","datavalue":{"value":{"entity-type":"item","numeric-id":775237,"id":"Q775237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119019$690C475A-F539-41AD-96BC-2FCB60558DBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f3e27675af97cbeffb3f1389b25a0aa71626fc15","datavalue":{"value":{"entity-type":"item","numeric-id":294661,"id":"Q294661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119019$7F23AB37-BF71-487C-A6D9-FB0AEE8F5346","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":"Q1119019$D45CBF27-BE83-4FDC-ABF5-905F4C92C975","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1119019$0B8C99E5-42EA-47E7-9FE4-00BEBE4187B5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"96a79e2ab1085c4e8f3cfde279059a301bb3ab43","datavalue":{"value":"A flow in a network with a source s and a sink t is a blocking flow if every path from s to t contains a saturated edge. The authors show that the problem of finding the lex-first blocking flow in an acyclic network is log-space complete for P even if the network is restricted to be a 3- layer network. Inspite of this the authors demonstrate that there is a random NC algorithm for finding an arbitrary blocking flow in a 3-layer network.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119019$A3AC75B4-BC51-4D2E-B5D5-05529C2B1E6B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119019$D3B0F685-0F56-477E-BE70-F8BB317ABA9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"517ace4a4f9c45a5475b4a8927a567447dbdb293","datavalue":{"value":"68N99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119019$6596DA55-FFCD-40C7-B98A-E89A41314C49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119019$22A59369-7BC1-468F-812D-B961D7DBDB19","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"246ab3379d3edfa02d55feadf6ffe00083e72037","datavalue":{"value":"4096778","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119019$4559090B-030E-43E2-934B-B98B44AC2BA0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a63f5fdf3038af45049408a9914d671beb783a5b","datavalue":{"value":"parallel complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119019$2F3F2C75-D46D-4046-B9D7-3280FD643417","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"76fe3a0905906c5fcb5480a00fee1a48172a65ae","datavalue":{"value":"blocking flows","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119019$74496B0D-A017-4ECC-A3FB-A32CBB495918","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7236cc8cb081daa05c110f63d7a7e64cabbf9869","datavalue":{"value":"P-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119019$C5F4EDEC-50BB-48F1-B7E9-E53FC5019A87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ef52b71851ba99d5b1c1972696c680a77ec2b807","datavalue":{"value":"random NC","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119019$699B81F6-4169-496E-BE95-7BA4F2EA9E14","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1ba4a6e46d39a41518db65f4f97cbfd2a0693778","datavalue":{"value":{"entity-type":"item","numeric-id":238069,"id":"Q238069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119019$71DDAE1F-0B81-4427-AE2B-738F52BAEA08","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":"Q1119019$C2FA7D10-A6DA-469A-9D72-920E38BA2620","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"42110c1ff3fe506c276a2ff0884c08fb19713ae2","datavalue":{"value":"https://doi.org/10.1016/0020-0190(89)90225-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1119019$1CF3583A-9AB1-409C-88EB-8D8A61123AD8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"de865384059203470e2ea056d13430e9d8ee898c","datavalue":{"value":"W1981085297","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119019$A77B9CF1-B005-46B7-8CD2-3636C0405ADC","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":"Q1119019$195C9114-96CF-4948-B827-AF976F65FD3A","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":"Q1119019$F633926C-3FC7-460D-BF82-46E8BE6E5262","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119019$69800628-C3E4-48FA-9DB5-9EB383AEA975","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":"Q1119019$706CF833-2679-44FC-B020-884650288AAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc6e689ca9104617943bd76b284824e0c9ceb6bd","datavalue":{"value":{"entity-type":"item","numeric-id":3707420,"id":"Q3707420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119019$D3BED9F7-A0E5-41DC-B537-C2CCF4F23BA9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e9577019cd89dc892337ae065203a32dcb753ac","datavalue":{"value":{"entity-type":"item","numeric-id":1263969,"id":"Q1263969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8568a041fea83f0e336eb5d90e1daf98fb1c2557","datavalue":{"value":{"amount":"+0.8456399440765381","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":"Q1119019$1FC7EA31-CF02-45E2-9A38-200119092E6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04a8ace202e2c8af9b2620b057afd04518f5733a","datavalue":{"value":{"entity-type":"item","numeric-id":3026702,"id":"Q3026702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01507168b453a6d6d3ae06f18f4e00cbb63f5091","datavalue":{"value":{"amount":"+0.8067935109138489","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":"Q1119019$E099126C-29F0-4181-8E02-C769DBC51795","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee3bbdd3e92138e0bde80a8d7a1a720f48a39cfc","datavalue":{"value":{"entity-type":"item","numeric-id":4020359,"id":"Q4020359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db898e455133cdfd65ddf90262531f38cefbcae5","datavalue":{"value":{"amount":"+0.805142879486084","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":"Q1119019$CE0B79B8-05BB-47D1-886D-BAC17715377D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f7f0efb8ef127dc1c6a930f2632f21453f59ace","datavalue":{"value":{"entity-type":"item","numeric-id":4228439,"id":"Q4228439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04f75dc85258d26e84c2b2bbcf4e3a6d77f81420","datavalue":{"value":{"amount":"+0.8047739267349243","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":"Q1119019$5DEFFD77-EA13-4975-8BD0-1B638727DC8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"587e66a7d5cc2ac41a0bed32673a089e485caa84","datavalue":{"value":{"entity-type":"item","numeric-id":795064,"id":"Q795064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72c60decf7bcdbc1983ab5d6abf791759f7be49e","datavalue":{"value":{"amount":"+0.7699972987174988","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":"Q1119019$DAA1E316-9402-40DE-8AB1-F6178665D6C5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The parallel complexity of finding a blocking flow in a 3-layer network","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_parallel_complexity_of_finding_a_blocking_flow_in_a_3-layer_network"}}}}}