{"entities":{"Q4015475":{"pageid":6045267,"ns":120,"title":"Item:Q4015475","lastrevid":55183858,"modified":"2026-02-04T13:17:36Z","type":"item","id":"Q4015475","labels":{"en":{"language":"en","value":"An Exact Sublinear Algorithm for the Max-Flow, Vertex Disjoint Paths and Communication Problems on Random Graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 86256"}},"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":"Q4015475$72D56F69-2F38-49D6-9200-793378A45761","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a6b47de64f8077d6c3270e2e197a274de849a99b","datavalue":{"value":{"text":"An Exact Sublinear Algorithm for the Max-Flow, Vertex Disjoint Paths and Communication Problems on Random Graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4015475$B2472925-F0D6-4A42-BAD5-5B9AEF9ACDB0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d987d70bd658fa73207a67d9506dec45b2db890c","datavalue":{"value":"0769.90033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4015475$710AC658-DDEA-485C-9727-C4BC7E3DB9C9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5b969806e15667b8bb837290cff38032bdae579d","datavalue":{"value":{"entity-type":"item","numeric-id":242829,"id":"Q242829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4015475$5E791847-F520-4721-83FD-C764CC597268","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"da22dd798edb52cb4cd38ece3d93e1b6b18670dd","datavalue":{"value":{"entity-type":"item","numeric-id":71781,"id":"Q71781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4015475$C12DE263-C066-4C5C-8DBC-B2230BB35975","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"dc0412d3fbac752f58b3eee00d07c66c56b741a4","datavalue":{"value":{"time":"+1993-01-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4015475$A6292BBE-0F18-4274-9C89-3A939561254A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0f04c159386ffa0dca53c7806240943adbdfdea4","datavalue":{"value":"90B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4015475$F82CD7FF-3321-4C50-9AB1-E7565D10A6FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e3ec0ebb66ad9a53653ec1e19a7608e786acef46","datavalue":{"value":"90B18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4015475$CCC60DFE-0E75-40F5-9F9E-8D3579BBE576","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a7edc01538ef78e7e423d9c49f622de0faa5a14","datavalue":{"value":"65Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4015475$8CFE9FCF-0406-4F79-8990-90CBF7211611","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d550400b67148ac150a943881fbd05e682ea56f5","datavalue":{"value":"90-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4015475$138ABD13-F071-45C4-90C6-6D4B543F9A22","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"228e41b320df6cc08f02e5ebfcad5cbe5dee96d5","datavalue":{"value":"86256","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4015475$B34A659D-1039-4985-A498-209607A53730","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2832e5ae4fc414c772c86f6023e26d563dd35e6","datavalue":{"value":"randomized algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q4015475$110C1CDF-BB0B-4315-9A10-711C5B249F86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d08500084665cc052dff0a46d3f0ba9a29f3e23a","datavalue":{"value":"maximum-flow maximum-cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q4015475$A5D13D68-CE8A-4495-A3FB-F869AA088C82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"074eadd7859c4d866fc582d3d23500af36193899","datavalue":{"value":"connected random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q4015475$E2B8EDB9-B315-4D1D-883F-28626C64051C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a5f14346e8693c286aedde40199a68adb65839c","datavalue":{"value":"NP-hard communication problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q4015475$03AFFDD6-0D0D-4AC0-894E-BAE11A2DE3A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"184a6fca5c610613ed6375f26a961f2a862d5dc2","datavalue":{"value":"sublogarithmic parallel and distributed implementation","type":"string"},"datatype":"string"},"type":"statement","id":"Q4015475$A9526AE1-DBED-444C-A67F-394FE576D3C7","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":"Q4015475$F1D13BF9-39D3-4C3E-9CEC-627748F392A9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0b3f4f19bf781c35e7b606d445cc49541f5f3ca0","datavalue":{"value":"https://doi.org/10.1287/opre.40.5.923","type":"string"},"datatype":"url"},"type":"statement","id":"Q4015475$FDA84C30-C3DF-441D-9588-01DE8F1372E2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5fae06eadbb523b24ee59be46b705d30ac1d95d7","datavalue":{"value":"W1968084791","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4015475$71193684-E40E-4CEF-A686-898DA8A8CFCD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6cdf4bef17c818c28525cf7c9a4251a66fa69e82","datavalue":{"value":"10.1287/OPRE.40.5.923","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4015475$E33F21A7-EDBE-4205-8ABB-AF47D73E04D0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2742b19c8b58d496b4305245c2057880084baf99","datavalue":{"value":{"entity-type":"item","numeric-id":4875193,"id":"Q4875193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f8fcf926fbadcad94c24564191e1de07bd88a39","datavalue":{"value":{"amount":"+0.90514016","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4015475$564ECD43-355E-4D20-A3FD-7FC8DD4A967D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"585a6bee367a713bc6a68370db5d0f10ed94b1a8","datavalue":{"value":{"entity-type":"item","numeric-id":5383975,"id":"Q5383975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa804686c797bd0fa5353361e14193db0d359e94","datavalue":{"value":{"amount":"+0.89282113","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4015475$41D5F3AE-AABA-4B80-A89D-68697C0BD006","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"891badb2d294a5724d693d0fcc05e0adf23b33e8","datavalue":{"value":{"entity-type":"item","numeric-id":5741792,"id":"Q5741792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ede43c345716e1b37b888322263f9b3c84bc81c","datavalue":{"value":{"amount":"+0.89067084","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4015475$9B3AD45E-442C-4EEF-8A66-4C8981D02BED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90f08771145da64b0476c5ca8199cdd68ada52f6","datavalue":{"value":{"entity-type":"item","numeric-id":5450805,"id":"Q5450805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d036f1392cdf65145abb2c1d9f42c3998d8d5d02","datavalue":{"value":{"amount":"+0.8863474","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4015475$CE460ED3-1D18-4A81-8CAD-7F3419607C05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ceed6a0c4a571754f7fa852943c08446f6f955a","datavalue":{"value":{"entity-type":"item","numeric-id":657914,"id":"Q657914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3565ee9bdf908cbe15a1f36a37397ed0a9afcee9","datavalue":{"value":{"amount":"+0.88164544","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4015475$EDE13E52-4361-4608-99A9-E1DC9A1ACE8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31cf180738873e375a0cecbbb4f3987dda8b9837","datavalue":{"value":{"entity-type":"item","numeric-id":4796194,"id":"Q4796194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a5aa129a0fe8c1acd175416aebd05969e881c5b","datavalue":{"value":{"amount":"+0.8772712","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4015475$FE59EFA7-6910-42C1-9856-5A25ADAC11B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b686ae73c5c4f0f2ea66a20a3faeae7d06c4f23","datavalue":{"value":{"entity-type":"item","numeric-id":3611898,"id":"Q3611898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b0b7a8cb2913518949d6558c15a321ca4d46495","datavalue":{"value":{"amount":"+0.8760935","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4015475$0D78CB41-CB2F-4F97-85BF-C401B54EACA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6573080252e058b5e2791d7134388491ce41233","datavalue":{"value":{"entity-type":"item","numeric-id":1736537,"id":"Q1736537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a15f6ae850eca85abb98ab8976fa9dedf7749432","datavalue":{"value":{"amount":"+0.8752911","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4015475$79ADFE13-4F37-4439-AB66-A789AA81D358","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f11ff9718455c060005b80d51946f47b8a94767","datavalue":{"value":{"entity-type":"item","numeric-id":2638376,"id":"Q2638376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c581571f4d934f8a79bf81298c7ade7f1a9853d","datavalue":{"value":{"amount":"+0.8743036","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4015475$C3521F16-D8CF-4FA5-8E69-7252ECB600BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74311bbf1c5f9f31ba65805c3aa25e5d38760634","datavalue":{"value":{"entity-type":"item","numeric-id":4388872,"id":"Q4388872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00df4eee6a34babd26d9acab491ae3b53e9238a6","datavalue":{"value":{"amount":"+0.8740916","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4015475$C5C0F5E8-BE32-4351-B8C2-B5BB9F24F92B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4015475","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4015475"}}}}}