{"entities":{"Q581209":{"pageid":582976,"ns":120,"title":"Item:Q581209","lastrevid":62927466,"modified":"2026-04-11T09:02:03Z","type":"item","id":"Q581209","labels":{"en":{"language":"en","value":"Polymatroidal flows with lower bounds"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4018737"}},"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":"Q581209$747EB7F6-6FDE-4572-9D14-DBD367A7AD85","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"185b02647897f08701a7b7547168ec24f910cb23","datavalue":{"value":{"text":"Polymatroidal flows with lower bounds","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q581209$90B07028-4B1B-461B-B09A-CF6BC03B5E11","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7ec788d2f51ef87443ce0186655966e7b17d54e5","datavalue":{"value":"0626.90025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581209$866FDF39-380B-46E9-93CB-6C29D6AF709D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8307660ae70dc7f5fdee02daf4d98fddb850a1b3","datavalue":{"value":"10.1016/0166-218X(86)90050-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581209$0580DAD9-98D4-4148-950E-3F4E237F262D","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":"Q581209$23B955D5-5ACE-4BF6-B1DB-C55DACA46C39","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":"Q581209$9A0C29EA-18C9-4830-A45D-2A28FDC8CA65","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cb984ded54c136613bb399ba9e278482681d31d1","datavalue":{"value":"Ordinary network flow theory has a number of interesting theorems dealing with the maximum flow problem: integer solutions, polynomial bounds, max- flow-min-cut theorem and augmenting path algorithms. These results have previously been extended to polymatroidal networks. These are network flow problems where capacity constraints are imposed on the set of arcs into and out of each node, as opposed to capacity constraints on individual arcs.    This paper examines the extension of the four main results of network flow theory to the case where lower bounds are imposed to the arc sets, in addition to the capacity bounds. First, it is pointed out that for general constraints, the problem of finding a feasible solution is NP- hard, since it is equivalent to the Hamiltonian circuit problem. Then, a subset of bounds, namely those that have the property of being compliant, are defined. For compliant bounds, it is always possible to compensate a flow variation on one arc by a corresponding and opposite flow variation on a single arc adjacent to the node.    From this property, the authors demonstrate the four theorems concerning the maximum flow, and prove an \\(O(m^ 5d)\\) bound for the maximum flow computation, where m is the number of arcs and d the time required to compute a feasible solution.","type":"string"},"datatype":"string"},"type":"statement","id":"Q581209$08D705F3-EE79-4F85-84C0-28EB3502454B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0f04c159386ffa0dca53c7806240943adbdfdea4","datavalue":{"value":"90B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581209$1F48C51B-B27C-49AB-83DE-4DE2FA0385A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581209$EE173BDB-8B5F-4F15-A310-034AB65FBA4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581209$F2E47DC8-923F-415C-8DB3-467D427913A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581209$B5808007-2EC1-4A36-9681-AB157589B57C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a35f6c3a0732c7de025039292472ebdec361a424","datavalue":{"value":"4018737","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q581209$69F785E6-67FD-4291-B4A3-263384FDDE0E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a39ec4307b26d786312cb390856b9060d3bf22c8","datavalue":{"value":"matroids","type":"string"},"datatype":"string"},"type":"statement","id":"Q581209$1ACF08BA-76D4-4B42-9621-3234860BDE39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"327c8ceed3def07bd37ff4c6153133e64ff0aaa1","datavalue":{"value":"maximum flow","type":"string"},"datatype":"string"},"type":"statement","id":"Q581209$92D7358C-A9A7-43C1-ABDB-4DA59704E146","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fce1296a1c8efd68e5cf411b64890eacf7a02a97","datavalue":{"value":"max-flow-min-cut theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q581209$B65F1193-2FC0-439F-A804-E9A30E35E4F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3dca820565c78ebac0669c63d5c87c5c67fd8d8c","datavalue":{"value":"augmenting path algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q581209$51931E80-627D-4C3F-AEF5-3BEEA7023C57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"406c322dca12eec4b6114f07c0c7832f540d292c","datavalue":{"value":"polymatroidal networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q581209$2FF7CFCD-9406-4F8E-A898-4F19FC5A0A85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q581209$F5F2601D-8339-4BCC-ADF4-F7AE17465A73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1dcceedcfff603855facc9892da13b2e1990eeee","datavalue":{"value":"capacity bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q581209$5A0716F1-1E8E-4420-B313-98210FDB2443","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"db5fa62c15c189d130308c531e7f613d47ff7db5","datavalue":{"value":{"entity-type":"item","numeric-id":671938,"id":"Q671938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581209$1759555B-428E-4795-A920-FE602E5D76FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"855d8872a495aa24469c23359eec4865d90d55e0","datavalue":{"value":{"entity-type":"item","numeric-id":1062625,"id":"Q1062625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581209$26CA83E8-EDDA-4392-930D-01C615DDC065","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":"Q581209$63A38682-E15C-49C6-B552-08C30D536ED1","rank":"normal"}],"P223":[{"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":"Q581209$1D60B7CA-EED5-4CB5-9671-C9E527D85AEF","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":"Q581209$E8A8F384-8D65-4D93-AB9D-2770FDF2BD74","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":"Q581209$DB4086BF-D9B7-447A-A59C-97FA27CA2AC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cb6d330b0ba17ea9706ff485bd2cc7e5caf6771","datavalue":{"value":{"entity-type":"item","numeric-id":3883524,"id":"Q3883524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581209$DDE345F1-9E4D-46C9-92B0-314470183E96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a0a4be11c16545fea2d441eabaf3f7e93b3c9b2","datavalue":{"value":{"entity-type":"item","numeric-id":3684133,"id":"Q3684133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581209$222A4D5E-9164-45BA-8080-38ABB7E01145","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":"Q581209$8A79F277-0E76-436F-82F3-571E94A6DF29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f15fa6ceff3a27c1f1f44df961daff1d27e715b8","datavalue":{"value":{"entity-type":"item","numeric-id":3220319,"id":"Q3220319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581209$2CD71B25-CB21-4DA2-8C83-706DD0A50A9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61c3a63acde3c17f73425e2071164cd066ec3019","datavalue":{"value":{"entity-type":"item","numeric-id":3964296,"id":"Q3964296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581209$53CC1AA7-710C-4E37-8BD1-039A53FA9FD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7c28edf26a0c9f06bb2c1f783b35df4dda391f3","datavalue":{"value":{"entity-type":"item","numeric-id":4740302,"id":"Q4740302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581209$8DFFAA12-A9D5-4781-9205-BC16A678574B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d076e0530c9c4c069542d85d513880b754633204","datavalue":{"value":{"entity-type":"item","numeric-id":3734185,"id":"Q3734185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581209$0698B0DE-AFEB-4C8C-9149-91EC9397373A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a1edbc5af05dccc72059e31700f274e294a9792","datavalue":{"value":{"entity-type":"item","numeric-id":3962754,"id":"Q3962754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q581209$2AB4AC34-00F1-474A-86DC-E9DDC782C624","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd93c9f98f5341d3dfba3ad4ee88d8b48de89258","datavalue":{"value":{"entity-type":"item","numeric-id":3796942,"id":"Q3796942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"166c47682c3dd898e55e87084febb5d4423edb58","datavalue":{"value":{"amount":"+0.8606162667274475","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":"Q581209$258FBE77-4206-4CBC-A5EF-10726156F525","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"474f913f5a3a465450321f13713f3d3a276f2667","datavalue":{"value":{"entity-type":"item","numeric-id":4261777,"id":"Q4261777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eba558c4b1f7d2666c2a1ad5abdce4bc54e0ef86","datavalue":{"value":{"amount":"+0.8373961448669434","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":"Q581209$F92BBD67-CCCD-4D3F-9FCD-9001F4D224C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34938be1c88099ccdee287f9f9a3f55b6019f921","datavalue":{"value":{"entity-type":"item","numeric-id":1077321,"id":"Q1077321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dea01a6f4123e6ebf3fa1e80d982ea022a059141","datavalue":{"value":{"amount":"+0.8098502159118652","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":"Q581209$65E6EE0E-7503-4047-8106-FF078FC2D082","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd9102d680da4dab17a49299759de1f9b483e77e","datavalue":{"value":{"entity-type":"item","numeric-id":1304389,"id":"Q1304389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e5667c7faa6cde90128fb9f0e9554e98c675b58","datavalue":{"value":{"amount":"+0.8095763921737671","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":"Q581209$44A5162A-F0A6-4355-A160-A57AC25B1C34","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Polymatroidal flows with lower bounds","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Polymatroidal_flows_with_lower_bounds"}}}}}