{"entities":{"Q581206":{"pageid":582973,"ns":120,"title":"Item:Q581206","lastrevid":62927439,"modified":"2026-04-11T09:02:02Z","type":"item","id":"Q581206","labels":{"en":{"language":"en","value":"Duality for balanced submodular flows"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4018735"}},"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":"Q581206$1DD50642-27FA-4C08-8D1B-5948BB34D0FB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"48568bf7793d73a09479ec3fda386cefda49876a","datavalue":{"value":{"text":"Duality for balanced submodular flows","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q581206$2C59760D-5300-4ECB-BED2-2D133AC9ADDD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a3a8ee09357e09a0adc2f02851de45e4f4b6c668","datavalue":{"value":"0626.90023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581206$3A02C6D9-3252-4EBA-B68F-4A7337AA51DA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"23d13300c604f086272851aecb2c12e8c1b0d90e","datavalue":{"value":"10.1016/0166-218X(86)90053-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581206$C4A882B6-C0BE-4F8A-83C2-4DAEC1676DA0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581206$95212D72-3EE1-4D2E-B4CB-F9ECE4F660F6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q581206$FC4D396A-9FA7-4628-A4B7-B47B1D83E48A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2a503d68b98e6d895894aec32e7ef995eae5c964","datavalue":{"value":"A (single source-single sink) flow is called balanced if for all arcs e the flow value x(e) does not exceed a given proportion of the total flow from source to sink. After discussing a basic dual approach which works in the general context of totally ordered sets, the author shows that his approach can be used to solve parametric problems which are equivalent to balanced flow problems. The discussion is further generalized by considering general balanced submodular flow problems. In both cases genuinely polynomial complexity bounds are derived for the resulting algorithms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q581206$5DB295F6-CD6D-463D-BD1A-D34F5336DAB8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c24d1a4d9566abc9461048333a6d2676bb28f451","datavalue":{"value":{"entity-type":"item","numeric-id":166234,"id":"Q166234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581206$1A01F46B-1A0E-4C6D-9D44-FCCE5CD4C544","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581206$8A353750-14A2-4C00-8BD8-BCD9B0858F76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581206$2F5D3D98-D60D-41A8-9324-7AF0325BF95D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ba203638bc0be628e0e966a7686b89f063c06821","datavalue":{"value":"4018735","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581206$0E236D7E-D2D7-473D-B130-AE77C29ACF09","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1ecf978a28e5d1baefdbd10dbc4f102a6158a13","datavalue":{"value":"duality","type":"string"},"datatype":"string"},"type":"statement","id":"Q581206$7817C877-3FFE-4056-9763-6EA3279FBF59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4bb9570516cf866c99d6ef0659e4454b9893bdb","datavalue":{"value":"balanced flow problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q581206$43373BFE-7023-4D06-AE6B-1922565E92C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"74b775ea07190833d4a7576ed9ef1bee59f39cb5","datavalue":{"value":"balanced submodular flow","type":"string"},"datatype":"string"},"type":"statement","id":"Q581206$5E9AEE89-68C4-451F-ACA1-4F5699B61C18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c72e9d3dc5ea68f3d834d5c665b334f46744b233","datavalue":{"value":"polynomial complexity bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q581206$DC9117C0-23A5-49DB-8FDB-0FF5407172ED","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b0b4658e4e24ee7b434aecb303e937dd13b98c67","datavalue":{"value":{"entity-type":"item","numeric-id":1018087,"id":"Q1018087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581206$7E4CCA85-0EE2-474E-91E5-96270677A2CB","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":"Q581206$0C51D026-4211-4CEB-AB88-54B88C0D6AF7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b542d20ab2a9aa6927e440a253c116df3d8f0ea3","datavalue":{"value":{"entity-type":"item","numeric-id":4123451,"id":"Q4123451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581206$1DB1C0C9-3654-4915-AA0B-497FED9ECEE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43798c19208231d39c6c4f059a0476d674a2816f","datavalue":{"value":{"entity-type":"item","numeric-id":4149476,"id":"Q4149476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581206$703736EB-5C9D-4AA3-AAF3-D13C115BBD4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6b1dc0d2e548f9cda9832ad27d3c5a8b4dcdc9f","datavalue":{"value":{"entity-type":"item","numeric-id":4739952,"id":"Q4739952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581206$6B72954C-3F24-4126-AC77-F31D40248B46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba07e54f50d0b7053d1d94c933758be0e016cc29","datavalue":{"value":{"entity-type":"item","numeric-id":796541,"id":"Q796541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581206$04D0F3BC-1D81-4B71-935C-AEA1DB67BD8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"202a081da6cf3441a6a0bfdc7c9bb9dff20ffb69","datavalue":{"value":{"entity-type":"item","numeric-id":3337243,"id":"Q3337243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581206$08802612-EC48-4BA3-9760-E87CA255B482","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ca8e2226bc49403f5d34bedd57297744e386790","datavalue":{"value":{"entity-type":"item","numeric-id":1168215,"id":"Q1168215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581206$BBCF6C94-55FE-42D6-A2BD-4AF73BEC23BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14f7dd30ebae9c50fd25f92ac1d4c7d3f4204b9d","datavalue":{"value":{"entity-type":"item","numeric-id":761351,"id":"Q761351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581206$FCA9FFD5-7F6B-4290-96B0-4CA7C2092B46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"685a25ccac67774bd926893fe5762f26c33d7d8c","datavalue":{"value":{"entity-type":"item","numeric-id":4133994,"id":"Q4133994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581206$4FA8BF37-6886-401A-B48F-977D4AAB08E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fb92d0c47be1223623b1854929572465a19ccea","datavalue":{"value":{"entity-type":"item","numeric-id":3861175,"id":"Q3861175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581206$1FB99ACB-E4FA-4B1F-9A1D-7B623470254C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1371d484d381b820119d5c0a1742474804643a40","datavalue":{"value":{"entity-type":"item","numeric-id":3330974,"id":"Q3330974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581206$75A8AC7A-3BDC-473B-8BE9-4AC7B45E689B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f3d72d6f067eeebf02882fdf0a5f1edb3452f80","datavalue":{"value":{"entity-type":"item","numeric-id":1155513,"id":"Q1155513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581206$94324455-B393-427C-B552-974624455852","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6762c01dbf33bbc50339806f83b8e8a3d7df9f9d","datavalue":{"value":{"entity-type":"item","numeric-id":1167658,"id":"Q1167658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581206$83779BA9-9783-4286-B173-27FA2BED2FE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11f5ed9900baee846984c01940514d3a4d521cd1","datavalue":{"value":{"entity-type":"item","numeric-id":3725833,"id":"Q3725833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581206$6672ABEC-726B-41EA-8C60-319D0AB83AFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95b2ade2e971da7d2a7a29c58e5d31f83793905c","datavalue":{"value":{"entity-type":"item","numeric-id":1081535,"id":"Q1081535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581206$2DF0FBAD-2701-4D62-A17F-94977D406A45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c4415e1ea0b5e5c0c91501e4297f168857a127e","datavalue":{"value":{"entity-type":"item","numeric-id":3720309,"id":"Q3720309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581206$9825AD18-28A9-4D8F-8AC5-9AF3A3300CF9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"069043b278e86535ada3f5d7733d582c6b33b6f4","datavalue":{"value":"https://doi.org/10.1016/0166-218x(86)90053-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q581206$40800932-4D37-4B7C-99A7-D04EBB3C04B7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4ccd37b01602ab53d6cb61a6897eeead39b74d54","datavalue":{"value":"W2042718895","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581206$32FCAB35-A088-44E5-BDA6-991CCCE518CB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4dc5b79fd3579607a1ffc8b7ca884124ae190826","datavalue":{"value":{"entity-type":"item","numeric-id":1324690,"id":"Q1324690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32c5655e5d8a7c2628739e70770402ea39d27e72","datavalue":{"value":{"amount":"+0.8879828453063965","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":"Q581206$D841A586-EEE9-4769-BFE1-0FBC03F984D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f024d84bd09b3aae419ce7202956bebe7e6fffe","datavalue":{"value":{"entity-type":"item","numeric-id":5449563,"id":"Q5449563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32c5655e5d8a7c2628739e70770402ea39d27e72","datavalue":{"value":{"amount":"+0.8879828453063965","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":"Q581206$2278BFDB-BFDA-45D0-AACF-B4D1F58A5FDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"920a8890350af65be38ab98c84c503f4515cf434","datavalue":{"value":{"entity-type":"item","numeric-id":1183393,"id":"Q1183393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e257be2924a966ed7fb8af2c6c72bb629e28bb1","datavalue":{"value":{"amount":"+0.835675060749054","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":"Q581206$F08683F3-7CC4-414C-8728-7ADBE7B5D517","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"191f6a79025fe1bda9c30647bd461f6142c6b950","datavalue":{"value":{"entity-type":"item","numeric-id":3818096,"id":"Q3818096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54023b00be28f8f1771bd9a575d1de2bea2de233","datavalue":{"value":{"amount":"+0.8342811465263367","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":"Q581206$AF40D5E4-A16D-48DE-9486-29FE1C96FF1A","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":"5744af32425d77b63d0eb5dc7699900ce8973268","datavalue":{"value":{"amount":"+0.8203187584877014","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":"Q581206$EE238EB2-898B-4F6B-AB0D-186D47511CA0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Duality for balanced submodular flows","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Duality_for_balanced_submodular_flows"}}}}}