{"entities":{"Q2795749":{"pageid":2806487,"ns":120,"title":"Item:Q2795749","lastrevid":83508776,"modified":"2026-05-07T08:33:53Z","type":"item","id":"Q2795749","labels":{"en":{"language":"en","value":"Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6559383"}},"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":"Q2795749$C9A518FE-E0A1-4471-BC8D-2FDB9243A18E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6ad53211eea4d6e1108c2b5049701298d4375aa8","datavalue":{"value":{"text":"Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2795749$06654160-52CB-4796-9C9A-738D27254193","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5cdc1a600d5947b26941d8995375e139c15562c1","datavalue":{"value":"1332.05129","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2795749$8BAD036B-4832-480F-817D-1E2F255425E4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"72f8a6bcff0e3bdeb38180330f9900536ff29753","datavalue":{"value":{"entity-type":"item","numeric-id":2795748,"id":"Q2795748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795749$0A8B6CCA-8354-42DC-80D5-0B137F1A2AEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5d8df372c51304bf32d3341c08ca3a4e71110302","datavalue":{"value":{"entity-type":"item","numeric-id":335971,"id":"Q335971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795749$31DF3F51-0783-4781-8FFF-599C9F132E75","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"545d359c3736dad746c8015ce9f1a04448d43829","datavalue":{"value":{"time":"+2016-03-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2795749$32F7C275-3752-41BA-9474-06F53E722722","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bb98e2769e92e62f2d9f3800d3a4a0d73a72a19e","datavalue":{"value":"https://arxiv.org/abs/1401.0119","type":"string"},"datatype":"url"},"type":"statement","id":"Q2795749$58F157D1-5D72-4B68-BD19-C44D70382F02","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2795749$55F133EC-34E5-4086-B3D0-C5A3DD973F47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2795749$0C8A5A9E-5C21-474A-AC98-CF77D51A4A0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2795749$411CB8E4-46AF-4AC8-A64E-D020931E85F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2795749$D45A9A54-590E-4236-89B2-962F50D0BCFA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ccc62204c6219cd78f393b058b9f197b81fbe72e","datavalue":{"value":"6559383","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2795749$E73926D9-649F-49C9-870B-D2B6F30E2EB7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2795749$9AB99BB8-5E2C-403F-BFA9-01DEF748DA8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2bbd79578ef21cf413bc76e1bf22ef62335e3f83","datavalue":{"value":"auction algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2795749$25D733AE-4691-48F7-89A9-1B6F8516CD16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f23d425232c773c86aa6640db9b490349f3502ce","datavalue":{"value":"pushrelabel algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2795749$8DBE090D-164F-42D6-92DC-784C06A387AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6f0998bc14a299cbe9f34c62118ee77e9260f34","datavalue":{"value":"bipartite matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2795749$60C080E8-8E9B-442C-9061-79DDCACD4413","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4f51776dadcb1bfead92cdaa8c678dc729e342b","datavalue":{"value":"random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2795749$41F05DA9-5418-47F8-9D14-DBE6C526751E","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":"Q2795749$B726A52B-56BC-486C-9CA2-5238F44CF413","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5ef48705502bc6b278826c79ec7fe36c7e5aed00","datavalue":{"value":"W2153617527","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2795749$02F74415-0F04-41A4-AB10-0716676B7449","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"112ba43ee1f2f350559549b8a8f34993366e7e97","datavalue":{"value":{"entity-type":"item","numeric-id":2432523,"id":"Q2432523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795749$E57167B7-61DF-4C1C-B6D2-94C0551F338D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f61c5d68d33f8ea7723f3ac70afbbc88052e3402","datavalue":{"value":{"entity-type":"item","numeric-id":3258697,"id":"Q3258697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795749$238426E9-1E3C-4262-8778-AC5EAB85C1D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"035717286d7981d31d1ab38131284f2cbc687151","datavalue":{"value":{"entity-type":"item","numeric-id":1803649,"id":"Q1803649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795749$DDC71C55-ABAE-4D27-9BA8-D80A6C23F3F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48bece980fd189507a359fe57514e055a51e9ff9","datavalue":{"value":{"entity-type":"item","numeric-id":3578203,"id":"Q3578203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795749$3363B673-C562-4CDF-AA72-95C69AFE27DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5573f294786b8d9e665c2ccc529a0940f12209b","datavalue":{"value":{"entity-type":"item","numeric-id":5463380,"id":"Q5463380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795749$68F71910-6C4F-40E7-A443-667BB2DED991","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"800c670555a3aa8e0884c256e1569ab5ebd57aec","datavalue":{"value":{"entity-type":"item","numeric-id":5603846,"id":"Q5603846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795749$62523BB0-FFAA-4263-AB13-2F66ABC29354","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca23d16669e9710350295c498db6e6b753b332bb","datavalue":{"value":{"entity-type":"item","numeric-id":1914072,"id":"Q1914072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795749$9CD86FF9-145F-49A2-B020-2AC8A9A65147","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77c925fe735c46759427f41d717bbf94e5f6fe53","datavalue":{"value":{"entity-type":"item","numeric-id":3812009,"id":"Q3812009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795749$8F713D13-9F5B-47AB-9209-8F1E9C0333A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"187e1fb158e6b4695b1eefc466a8e0535eaf95e7","datavalue":{"value":{"entity-type":"item","numeric-id":5682014,"id":"Q5682014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795749$D974C2A4-A403-46F9-80D4-2A7463746006","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"578954a8ceca39888f7914a7b02b99f9851e5da4","datavalue":{"value":{"entity-type":"item","numeric-id":4327634,"id":"Q4327634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795749$A9939C10-38AB-4A30-9426-6F0CF4F17FE4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5e23be7265f77ddba990c47784a1a77b6cae6225","datavalue":{"value":"10.1002/RSA.20578","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2795749$22EBACDB-57F0-4CB9-9C9A-171C52BF532F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4ba69b2e7a1c5c8b270de9b61e45e78f0021324","datavalue":{"value":{"entity-type":"item","numeric-id":6086023,"id":"Q6086023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11077610b6f06c72075c4119c75923562101c22a","datavalue":{"value":{"amount":"+0.88361996","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":"Q2795749$5AAEFBD5-074B-489B-8406-578C047214BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b2dc7dc67c38d5cf3d4bb60dfacc01308be51a7","datavalue":{"value":{"entity-type":"item","numeric-id":4376193,"id":"Q4376193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be00f087f34d8d81e871e5c13cfaf9ac2a451e12","datavalue":{"value":{"amount":"+0.8651111","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":"Q2795749$89F3386A-5619-46C6-9DA9-A1C3352C8E44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5482acca6961a3c8dbd1e5e59c9819e0d1b0decd","datavalue":{"value":{"entity-type":"item","numeric-id":2849348,"id":"Q2849348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15c821b94758e55ae859c8b1bdd3c7d3922f0287","datavalue":{"value":{"amount":"+0.8640899","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":"Q2795749$9BEE716B-2A81-4249-AAE8-C36C026E74D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e70d51283a6af3114ef432b1bbc218176f42402f","datavalue":{"value":{"entity-type":"item","numeric-id":1614868,"id":"Q1614868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"edf803b839ff8d9714cbb6bdea2d50cad8699237","datavalue":{"value":{"amount":"+0.8571532","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":"Q2795749$012E7244-32BF-4EDB-81F6-F5CA57D3CE00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d55b85e251d5caed59903cbc9339389e4813bf5","datavalue":{"value":{"entity-type":"item","numeric-id":2684964,"id":"Q2684964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fdfcf85130c69c679839e5fc14f18f13757b460","datavalue":{"value":{"amount":"+0.8570424","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":"Q2795749$4DF5187F-BE49-409B-A3B0-C7D895FEF77B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78a19ae45e04b110dd494dc29220ca2430d27556","datavalue":{"value":{"entity-type":"item","numeric-id":5084502,"id":"Q5084502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6736dca75382577868da5da32116bfee49ac3fc9","datavalue":{"value":{"amount":"+0.8563376","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":"Q2795749$DDADCB21-F5E7-4AEF-A92F-BEF77581542E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe4ab4934c68fa333dcf6f4fc5e5376ceed5cff4","datavalue":{"value":{"entity-type":"item","numeric-id":3169079,"id":"Q3169079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d7c8491763b47d793b7ea4f6be8e8319c1ff28c","datavalue":{"value":{"amount":"+0.8558717","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":"Q2795749$B4AE3EEF-626D-4978-9478-182B9E47C0A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b19778f71d0bd62d4c95d332c593437b972acbe7","datavalue":{"value":{"entity-type":"item","numeric-id":3581408,"id":"Q3581408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d7c8491763b47d793b7ea4f6be8e8319c1ff28c","datavalue":{"value":{"amount":"+0.8558717","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":"Q2795749$4EF96F69-D8A9-40BE-AF40-B1205B59276B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c330eb5b86437b568c323d3b8eaeb7ab381b7a0","datavalue":{"value":{"entity-type":"item","numeric-id":3521916,"id":"Q3521916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a539db0a0c557d432048fb0f237b48a2671ac355","datavalue":{"value":{"amount":"+0.8551605","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":"Q2795749$27A6D8AB-4C27-46C8-B0F7-38B3BEE77FAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62cf9725fb2ca84a4e800f4c2f2b12e92d5deda2","datavalue":{"value":{"entity-type":"item","numeric-id":3578203,"id":"Q3578203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a539db0a0c557d432048fb0f237b48a2671ac355","datavalue":{"value":{"amount":"+0.8551605","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":"Q2795749$91AB047A-D0B1-49C8-ABF2-E76C738F4816","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"607ae7f7d11ced7a8909533172911c64cec6dcc4","datavalue":{"value":{"entity-type":"item","numeric-id":6486797,"id":"Q6486797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2795749$6730CFEC-9E2C-46C1-AF90-AEB0C4A7DA15","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Expected_time_complexity_of_the_auction_algorithm_and_the_push_relabel_algorithm_for_maximum_bipartite_matching_on_random_graphs"}}}}}