{"entities":{"Q1882113":{"pageid":1892855,"ns":120,"title":"Item:Q1882113","lastrevid":69547254,"modified":"2026-04-13T07:45:08Z","type":"item","id":"Q1882113","labels":{"en":{"language":"en","value":"Fast cycle canceling algorithms for minimum cost submodular flow"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2108641"}},"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":"Q1882113$AC814AFE-621F-4740-B0D1-0C8DE405CBF7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3a0de17e90be32e81acf200473375efd86ade470","datavalue":{"value":{"text":"Fast cycle canceling algorithms for minimum cost submodular flow","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1882113$2EEFF6D0-2BEA-4888-9521-F8C133F782E5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b3001b174c9e9d204fbc2047c8eddc21d3dc7cfd","datavalue":{"value":"1099.90052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1882113$5FB1138D-6B6C-4BD9-9FF7-8ED0E0D2AE5D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"17597b30db72c4c5d242850baa1f212800adb33d","datavalue":{"value":{"entity-type":"item","numeric-id":185376,"id":"Q185376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1882113$D1AAFEC7-56EC-4942-BBF5-377207E5FCBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"87f016f079e270fadf057468a751b512c82c5038","datavalue":{"value":{"entity-type":"item","numeric-id":294750,"id":"Q294750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1882113$B4466B94-3C3D-433C-941D-28B760E2C79A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d4655276ddc5fef118de8a7b44f3964ea5b758fe","datavalue":{"value":{"entity-type":"item","numeric-id":170012,"id":"Q170012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1882113$CB87C895-3085-400B-8BE4-559378984A50","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1882113$A588A015-2228-4929-BA0D-F54EE8A62E91","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b7f00f8b51fa8bf5ed60b4ebb320d9c6163c04e8","datavalue":{"value":{"time":"+2004-10-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1882113$EEF0F565-53A0-4AB7-A241-BB132D1A4D57","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"419eec30bc0b5199b5d0c09e25ee6f8bf177a433","datavalue":{"value":"The authors present two new algorithms for the submodular flow problem on a directed graph, introduced by \\textit{J. Edmonds} and \\textit{R. Giles} [Ann. Discrete Math. 1, 185--204 (1977; Zbl 0373.05040)]. The key idea for the first algorithm is to use an assignment subproblem for determining a most negative family of node-disjoint cycles in an auxiliary graph. These cycles are repeatedly cancelled by the algorithm.   The main idea of the second algorithm is to cancel cycles in the subgraph of negative reduced cost arcs until it is acyclic. At this point a change to dual variables that remove at least one node from participating in next negative cycles is made. It is shown that proposed algorithms can be modified so that the running times of both are \\(O(n^6h\\log n)\\), where \\(n\\) is the number of nodes and \\(h\\) is the time for computing an exchange capacity.  Finally, the authors consider an extension of the algorithms to submodular flows with separable convex objectives. This paper, despite some unexplained notations, is well worth reading by anyone interested in flow problems on directed graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1882113$3E6B07D1-0EC4-437A-9E5F-F48D4DC2B662","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1882113$D6F3C250-EC67-4A9D-8D64-FD01BDD9BB2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1882113$9A16409E-4886-4B8D-BE34-D2315CBA7FCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1882113$CD8695E5-5E97-4DE8-816F-BFBAC3E7FE1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ccd1dd4cefa81e8158b9f080486a4eaed61a9ee8","datavalue":{"value":"90C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1882113$61A80EEC-235D-47A4-A3C4-726F7DC5691B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ea66f589ff25c38bb8051d0a5fd5210dcdaa451b","datavalue":{"value":"2108641","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1882113$DB7F7526-285A-417C-BB3D-77A72E5E68C9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5977a236e856bcf2fb8d132123d8957aba2b7fa","datavalue":{"value":"submodular flow problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1882113$5DE0B999-D979-41E8-B13B-CBE52F1497F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5967ced8b8470f9c36b08128cb6f615371ca98e","datavalue":{"value":"directed graps","type":"string"},"datatype":"string"},"type":"statement","id":"Q1882113$7909F2BB-6AB2-496B-8852-18453C9AF5C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1882113$AF65E972-FB28-4FD4-90D6-E3727F2AEAEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ba5629cbfdd95373c868f85b8dc50a11e6245c8","datavalue":{"value":"Zbl 0373.05040","type":"string"},"datatype":"string"},"type":"statement","id":"Q1882113$BCA910BD-7F93-4250-907F-B1D1A2E8EDA0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2b972ef175b4299fdbfc53bb71881ff0c6d5f85c","datavalue":{"value":{"entity-type":"item","numeric-id":587047,"id":"Q587047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1882113$67D86C9A-C5AB-472B-9447-B5AE34C6F4B8","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":"Q1882113$E81A86F0-A06C-4083-A1F3-790EE99D6042","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f1e0169d3c753d002936bc10feaa377b944b73b6","datavalue":{"value":"https://doi.org/10.1007/s00493-003-0030-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1882113$51D3EDD9-2FE2-4323-81DB-AA089DA4D329","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"42fd9b400161682559123a405604dea86d84f4fb","datavalue":{"value":"W1986273263","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1882113$DF82DB7B-C2CE-4404-935A-A700535BD67B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b2f4f69fb105a88a13342407e2173b69929b0855","datavalue":{"value":"10.1007/S00493-003-0030-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1882113$DDEEAE46-8C68-45C8-A137-D6E69BBAEC2A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7fe3b9c56c341172c969ee2cb96230ab35603e9","datavalue":{"value":{"entity-type":"item","numeric-id":4250177,"id":"Q4250177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25ea3b9918bb270df83bf096eff5fd04e49227df","datavalue":{"value":{"amount":"+0.8714494","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1882113$385A04C7-9262-47E1-9650-7A68E06CFE3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02aeee56be6f1fcd2224eab7bd39dae837260181","datavalue":{"value":{"entity-type":"item","numeric-id":3680637,"id":"Q3680637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a8d9efc356d3ad328902f3422b02ce8cd895840","datavalue":{"value":{"amount":"+0.869426","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1882113$B0F635A3-0FBA-473F-BDB5-2F3BB9DF48EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2dbcc5c21bd7ad84dbc759c3cac3900efb50e676","datavalue":{"value":{"entity-type":"item","numeric-id":3220319,"id":"Q3220319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f9fa7ba09a9b3f3a1c2dbdc68758be432ae7d89","datavalue":{"value":{"amount":"+0.86668944","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1882113$C0BCB87F-D2D7-414B-A7B8-CE8A2D1028C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"942c482c786701c19b3913d323cec7162cdc0495","datavalue":{"value":{"entity-type":"item","numeric-id":3220318,"id":"Q3220318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e48190f39022ecaf1a89ffefed2c59acd07f6d1f","datavalue":{"value":{"amount":"+0.8451046","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1882113$E7DCFA10-FEAF-4E04-984A-3D5C458B78ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2be4205c2c1e8e38ee93736494261c2d50abd138","datavalue":{"value":{"entity-type":"item","numeric-id":294751,"id":"Q294751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80513f1ba0c46243acea1db3385b171e23b90e0f","datavalue":{"value":{"amount":"+0.82718253","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1882113$F59FA627-4675-46C1-BBC0-E08D1DC6542C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6edde9e9ccd293437af44c696fce055051272ee","datavalue":{"value":{"entity-type":"item","numeric-id":1125610,"id":"Q1125610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69b19287eba6fce5f7f1456c88f165f139339598","datavalue":{"value":{"amount":"+0.8196354","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1882113$5EFA8C60-1809-4690-95A2-75CCA8BBDBD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"928d923c34fc285409ed8b62a03317e43c6a7be7","datavalue":{"value":{"entity-type":"item","numeric-id":2785397,"id":"Q2785397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01bcfa6a16f0b3a0fe18f7dfc860b897f25339dd","datavalue":{"value":{"amount":"+0.81938607","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1882113$90C9B28A-9797-4DB6-B37B-80B9CA54D3DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"469966da65def6f8e91f852f1217b513ecf71506","datavalue":{"value":{"entity-type":"item","numeric-id":848842,"id":"Q848842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d83ccbabbb9feaa51500909707b8eada68f3cbf","datavalue":{"value":{"amount":"+0.8185982","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1882113$B1362953-35BF-4E80-88E9-BDB3B307BB50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f746dc4e92b531765da20be0989706971e8d6fc7","datavalue":{"value":{"entity-type":"item","numeric-id":1806021,"id":"Q1806021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c73c2210053e22caae0f201e39de54ba75f5e9a8","datavalue":{"value":{"amount":"+0.8177177","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1882113$D9E72D43-CEB0-4692-A0EC-11D37BD1FEC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f12d0148020009e894f49d238716a5842732578","datavalue":{"value":{"entity-type":"item","numeric-id":4263717,"id":"Q4263717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"221bf120698c2db5833b03866bb411bc8393bfac","datavalue":{"value":{"amount":"+0.81750876","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1882113$81A14B0D-3426-4FB4-88FF-4B10C6F03FDF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Fast cycle canceling algorithms for minimum cost submodular flow","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Fast_cycle_canceling_algorithms_for_minimum_cost_submodular_flow"}}}}}