{"entities":{"Q750277":{"pageid":752126,"ns":120,"title":"Item:Q750277","lastrevid":64094109,"modified":"2026-04-11T17:36:18Z","type":"item","id":"Q750277","labels":{"en":{"language":"en","value":"A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \\(O(n^ 2m)\\) time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4174641"}},"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":"Q750277$A4B503AD-9AFF-460B-B002-3EEDCF65546A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ace8a8580f970e39a28701572c085192e896931a","datavalue":{"value":{"text":"A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \\(O(n^ 2m)\\) time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q750277$59F25F77-5E48-4B2D-A1DB-66253BCD96FD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"974724c1a074a5cb9ab7e2509610523055e85801","datavalue":{"value":"0713.90028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750277$76219DA0-5168-454B-A859-43DD9C299827","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"462e415975997ecc13d16fb553026d205aa9edb0","datavalue":{"value":"10.1007/BF01580869","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750277$1AE2DF37-6160-4A22-B831-EB206EB35783","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"389c681e6859e96625810538dab4d8964ec9e5f5","datavalue":{"value":{"entity-type":"item","numeric-id":233995,"id":"Q233995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750277$76BCB399-8452-4A79-8759-2C2F8A401CA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"aa3401254f743548623fb5b6981634f82edf6bcf","datavalue":{"value":{"entity-type":"item","numeric-id":202777,"id":"Q202777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750277$15A471DA-A955-4AF5-B003-9D61D9EE77AF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750277$1A7EC782-B78B-419A-8E41-763F7D80BAA5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q750277$3F5C672E-A339-4E93-8195-6E9F2A8156F8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dd12c63af91bd31ffc18ae4d41d65b49dec9a4bb","datavalue":{"value":"Given is a network with n nodes and m arcs. The authors describe the first primal simplex algorithm for the maximum flow problem which is strongly polynomial. It relies on the fact that among the variables which might enter a basis one is chosen, whose corresponding arc is closest to the source. In this case a maximum flow will be found after at most \\(n\\cdot m\\) pivots. The authors describe also an \\(O(n^ 2m)\\) implementation of their new method.","type":"string"},"datatype":"string"},"type":"statement","id":"Q750277$5C0E87F0-540D-42EF-8F86-0E548F09C347","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750277$FEB3C8CC-130E-4EC7-88F4-288685DB6448","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750277$5665202C-BBEC-4F4F-B2E2-C3C3E133A790","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d550400b67148ac150a943881fbd05e682ea56f5","datavalue":{"value":"90-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750277$D500AEEF-7CE3-4CCF-94A4-EAA0C8DFBE3E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"33fe482e85c4bb8f875c15cf7ecbba4af1d57036","datavalue":{"value":"4174641","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750277$E94C0F83-97A2-43BB-B2B4-E1C802C4D68E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ecd6c5582a59225376bc67598010edecc5c1ce3b","datavalue":{"value":"primal simplex algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q750277$094CDCA9-0058-4C12-ACA5-3FC9CECB0951","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"954c84afb14842483f6d23a36151013fc6e080af","datavalue":{"value":"strongly polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q750277$B5D117F5-5971-4080-9983-A4A0766DACED","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4a45374906fa7445234d8f571198ca1750e8882a","datavalue":{"value":{"entity-type":"item","numeric-id":170644,"id":"Q170644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750277$29369B72-255D-40D7-87E1-42983222950D","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":"Q750277$7DF26718-2B1A-44A0-8F0D-0F76F79ACE87","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"14410b9b08fd4ead238ef238913db01133614d9a","datavalue":{"value":{"entity-type":"item","numeric-id":3830789,"id":"Q3830789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750277$BBE916B6-9A9A-4E4B-A473-1DA5651B46C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe7c4b3192fc9d49664f31462adad1c716877534","datavalue":{"value":{"entity-type":"item","numeric-id":4123079,"id":"Q4123079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750277$EE6FC640-8AA1-4B40-88C8-E3BCC18FF04C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25b4678d846bc12e283a69a145b0023aa6e21b6f","datavalue":{"value":{"entity-type":"item","numeric-id":5808752,"id":"Q5808752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750277$080583E1-2C83-4D85-A437-C5AE442C7F8E","rank":"normal"},{"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":"Q750277$9FB47626-92D3-4EE8-BFA1-F1CC2D6D5DEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da5b18e5a44e3c67c75b0887be40e31fe6fc87d6","datavalue":{"value":{"entity-type":"item","numeric-id":4080986,"id":"Q4080986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750277$972D1E7E-5E4E-44FF-B07D-F1E29BC52AEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"399e08df4dbfcdbdd10c5c3a4b80bc3b3551f096","datavalue":{"value":{"entity-type":"item","numeric-id":3260928,"id":"Q3260928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750277$C560ED7C-D3E2-47E9-9867-7CBDAE0B7745","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3544ff5c3325f5ac1e5dcd2fd92020bf1b6189fb","datavalue":{"value":{"entity-type":"item","numeric-id":3292914,"id":"Q3292914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750277$DCF52FE7-1AA6-4F9A-B27F-8415056372A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d8c500d5469ac363f5bb9d7765a265f00e2708c","datavalue":{"value":{"entity-type":"item","numeric-id":1176566,"id":"Q1176566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750277$51F86A40-D8C6-4CF2-B6B8-07F06C84DAC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e511efae2023331fbf1248470e005ba94e7b7254","datavalue":{"value":{"entity-type":"item","numeric-id":3474897,"id":"Q3474897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750277$204D9659-9330-415D-86E5-C8534581EEC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a234ed1084f1aac4384acfbe5b5eb87651092355","datavalue":{"value":{"entity-type":"item","numeric-id":3887219,"id":"Q3887219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750277$04E108C8-FFF6-40CE-B95D-1E6E4B29C45B","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":"Q750277$FFC5BE77-03C5-4EDB-9318-A0D6D3CD07E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7b76c498f5c4968b18e0a5cf8a7bb4513c31822","datavalue":{"value":{"entity-type":"item","numeric-id":1838310,"id":"Q1838310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750277$36AA7823-AE1C-46C4-96E5-DA5E4F570376","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ec83f7375fdc5e98a3e0fbd2c809358fa55ac66","datavalue":{"value":{"entity-type":"item","numeric-id":4775712,"id":"Q4775712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q750277$C1772E07-F9B1-42C5-AE3D-8D871AF40553","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0743ee0e1f28a33fdc69c9dc13055067113c10ee","datavalue":{"value":"https://doi.org/10.1007/bf01580869","type":"string"},"datatype":"url"},"type":"statement","id":"Q750277$A407C449-108B-466E-B912-3B33E2D4FAB1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ed42d7259216f71255bc16f5c2dd947a2cdf114c","datavalue":{"value":"W2029479369","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q750277$E51574DC-8B7D-4D46-B38B-899B65005E53","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2f8791ad2cd6ee4178b0e976b4c0ed408e5fa4a","datavalue":{"value":{"entity-type":"item","numeric-id":1180817,"id":"Q1180817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e61f7673e13e8620b542ee3e6ba439f64ebaf29e","datavalue":{"value":{"amount":"+0.8850148320198059","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":"Q750277$647517F5-3A60-4438-AB63-FF8236C6A113","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c17761f54475ab9d3311b82e6292db5e2c7dd406","datavalue":{"value":{"entity-type":"item","numeric-id":1380934,"id":"Q1380934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5fd804e7113770981a49714138fe446441f34e95","datavalue":{"value":{"amount":"+0.883830726146698","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":"Q750277$1F605F5D-7FF7-45E2-B507-9E4FE43E1E5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e1bfd203092efa063cd57585279c6478581a199","datavalue":{"value":{"entity-type":"item","numeric-id":1373745,"id":"Q1373745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86739ca9f12c57bdc3eaad4601ca799340520e49","datavalue":{"value":{"amount":"+0.883216142654419","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":"Q750277$F1DFCEAF-321D-4C90-9411-E0A5B5F432A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"875e9661533ed5cda969fd11a133e9126a1663e9","datavalue":{"value":{"entity-type":"item","numeric-id":1193519,"id":"Q1193519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"038fafe6e2b62f0af5e945bc321ccc8d2ef59d09","datavalue":{"value":{"amount":"+0.8676084280014038","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":"Q750277$ECC2ACD5-5363-447A-8B06-227E0CC1F64C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c72c561bd52abf1431a065268dbdad61ee4b827a","datavalue":{"value":{"entity-type":"item","numeric-id":688924,"id":"Q688924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"324ec7a184f3ed7639231bf497e6ccfee60c317a","datavalue":{"value":{"amount":"+0.8638970255851746","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":"Q750277$5485B5EE-DF20-424C-8B20-D0FA843CBDF4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \\(O(n^ 2m)\\) time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_primal_simplex_algorithm_that_solves_the_maximum_flow_problem_in_at_most_nm_pivots_and_%5C(O(n%5E_2m)%5C)_time"}}}}}