{"entities":{"Q1088884":{"pageid":1099636,"ns":120,"title":"Item:Q1088884","lastrevid":69616662,"modified":"2026-04-13T08:13:45Z","type":"item","id":"Q1088884","labels":{"en":{"language":"en","value":"Greedy concepts for network flow problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4001834"}},"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":"Q1088884$9989573D-FDF9-403C-A1B3-3CD1DABFAF83","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"339864ed942cf24f7fcaf2f126da8842b6464549","datavalue":{"value":{"text":"Greedy concepts for network flow problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1088884$A8B3BF63-BD03-4DC0-AEB1-54F6AD4DF312","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"78ca7fa53b5b56059e5c9b2de096982e1201c8de","datavalue":{"value":"0617.90027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088884$71AF6BD0-0A4E-4FE8-AAE5-3CBB80046547","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"23db88f8a5b198c4fc567d79992c2742ae1e57b8","datavalue":{"value":"10.1016/0166-218X(86)90037-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088884$DA39E5F8-80AE-44EC-8F0C-88E9D5E824C5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5ec527d58d85c3b08d82d96882fc777770b8233d","datavalue":{"value":{"entity-type":"item","numeric-id":1006042,"id":"Q1006042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088884$F756261F-AE15-4832-BA93-9005848E196B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"daf0481954e7802993a7ffb0f5fbcfa71f15bb37","datavalue":{"value":{"entity-type":"item","numeric-id":177705,"id":"Q177705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088884$46193A3C-9522-491B-8447-86D9FCE70B9D","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":"Q1088884$08028715-FAE0-4EDF-827B-054AF352FBD8","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":"Q1088884$3020443C-71EF-43F2-AD62-E74949285CE0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"86520eed08b785d0ae4c0d8944e89ab2d6e2d925","datavalue":{"value":"The problem of finding a cost optimal flow in series-parallel networks can be solved by the greedy algorithm which in this case is identical to the augmenting path method. In this paper the same result is derived by demonstrating that series composition and parallel composition preserves the property that the problem can be solved by the greedy algorithm. This leads to an algorithm which is different from the augmenting path method. Applications of these concepts to tree structures are discussed and it is shown that these structures are polymatroidal in contrast to the series- parallel case.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088884$94528441-E2C4-4C64-B7FB-B4CE2DB9DB6D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088884$B73018FB-2765-4F03-AF42-578B737AD635","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088884$937659C6-DBF9-4E61-A446-2A9FCFD3C473","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bd98384dfab36e8fa6109adeeea44ed6ff7adde7","datavalue":{"value":"4001834","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088884$70805C72-B46B-4A84-AE94-07232C88B575","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dbd9ebef0bfdf5d7e3ec4a51605ee6f51b9bd69a","datavalue":{"value":"cost optimal flow","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088884$DBF426CB-F9DA-414D-8912-B0623AAB18C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a07d94fbf4b3a0d162c73ffac117ffcf0405b1c6","datavalue":{"value":"series-parallel networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088884$CBFD4E19-9259-4D51-9024-109EC6CF905C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e1e7eb452ae4c92c43fa47bb0afb8177365a429","datavalue":{"value":"greedy algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088884$DCAC0588-1A63-4A1D-80E3-9EDB419C3B6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"77946135eb75334e7abd0a1fc8144f3ca00165c6","datavalue":{"value":"augmenting path method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088884$F2CF9220-0A2F-4F82-A9B7-D1254A95092C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59432540d62a3c70baf2197598cd1f96385f4275","datavalue":{"value":"series composition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088884$A9444924-F440-44BC-810F-90E94958D6C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50d81425affb13dcf09985fe807cbb0cd8e68cb4","datavalue":{"value":"parallel composition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088884$6F846FCB-0ABF-46BA-A2D9-A67124035AFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"82d4bb186d2276614267ba379fb7385916e471a8","datavalue":{"value":"tree structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088884$3F5A181D-7DEB-480A-B408-69C5AC1E2D96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9fa9a8401168a5334277ed8cb77b0178c663395","datavalue":{"value":"polymatroidal","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088884$F2CD388E-D2A1-483C-87B6-0D95BE080BC0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2054ab6afcff86345461ab192c34bfbef6c7b38d","datavalue":{"value":{"entity-type":"item","numeric-id":261055,"id":"Q261055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088884$39E4AD9B-0F78-47BE-850E-599710CDE117","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":"Q1088884$79FE7FA8-2DB2-4C4D-A864-B9A164427A8B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f75ccbc4715043ffbe1524dd237b6818c7b5d214","datavalue":{"value":{"entity-type":"item","numeric-id":3718481,"id":"Q3718481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088884$ECEEE5B3-A947-47E8-8A03-AC0E76451C45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3361f2b8d15d5ac5cb472f0c8892ae3996b184c1","datavalue":{"value":{"entity-type":"item","numeric-id":1061597,"id":"Q1061597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088884$255D8F06-02CD-45C7-9147-6967B63DD666","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7aae35d25f4436919abce0bbbbcb749b0fad7196","datavalue":{"value":{"entity-type":"item","numeric-id":3318501,"id":"Q3318501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088884$59C0F417-2107-4F43-B863-CDC4BB9A11A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"191b6b9a04947c29f77ff23d01b37877ddc1c56e","datavalue":{"value":{"entity-type":"item","numeric-id":3332729,"id":"Q3332729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088884$D4ACBA98-97A1-4A7F-80A2-72DB0BBD9DD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a10d9726bd833217e3e0ca3cedd2d986dbf6d0d6","datavalue":{"value":{"entity-type":"item","numeric-id":5331678,"id":"Q5331678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088884$A82EA006-5980-46D8-ACAE-AA797ACBC229","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e4fe03096a0bcb86eda06b2ba02370a5d63dd45","datavalue":{"value":{"entity-type":"item","numeric-id":3737235,"id":"Q3737235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088884$2B33C45E-E4AF-4D24-835B-46B41AF9E91C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4e5a50e1e90aeb19ca4ff2b3971a69ace23d33f","datavalue":{"value":{"entity-type":"item","numeric-id":3682236,"id":"Q3682236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088884$525299E3-EF0D-4913-80C4-C4B3AB0AF7F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4fcfe987d8cbbd43f7b7238b024d7a85de33a069","datavalue":{"value":{"entity-type":"item","numeric-id":3936212,"id":"Q3936212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088884$164210C8-AC03-4620-ADB0-6962C3F90F79","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9ffb84ff62052dfc9ec2ab6d87072630de4715d","datavalue":{"value":{"entity-type":"item","numeric-id":1061597,"id":"Q1061597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48e9070007db720ff59752be6a3e8df4eec95379","datavalue":{"value":{"amount":"+0.880913257598877","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":"Q1088884$B907E748-C623-4BCE-8155-98047E7A978B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b93e7d7937e056bba3fab2ffabadfd64271aeba6","datavalue":{"value":{"entity-type":"item","numeric-id":1107418,"id":"Q1107418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec374fd3b2cd8c1377b001317f837ad3ac459dc1","datavalue":{"value":{"amount":"+0.8753387331962585","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":"Q1088884$AABFD8A6-00F2-4736-AB76-944499945B75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"756a8af5241c0ffb77913fc43bd902ed554d0418","datavalue":{"value":{"entity-type":"item","numeric-id":4275336,"id":"Q4275336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d0d74b3ad30ca7927c884183e89175057f91f92","datavalue":{"value":{"amount":"+0.8216502666473389","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":"Q1088884$D67E220C-5D09-4F5D-A1F1-ED44B78C442D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd46075492677282a04e3f2a2c2f4dbe08547788","datavalue":{"value":{"entity-type":"item","numeric-id":4343043,"id":"Q4343043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3823ee715d68413a0a4fd7fa0854a0b3d3fc9a72","datavalue":{"value":{"amount":"+0.8183395266532898","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":"Q1088884$D0EF77CB-A970-44CA-9786-4058970D64F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb0e43c285a918fdcdb91c9d0928d40eb6421598","datavalue":{"value":{"entity-type":"item","numeric-id":1321658,"id":"Q1321658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4adcb7075676494f7ca1f8e9fc95a89b11a82f9a","datavalue":{"value":{"amount":"+0.814697265625","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":"Q1088884$15E75B7D-BB53-471C-85E5-0271F9792223","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Greedy concepts for network flow problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Greedy_concepts_for_network_flow_problems"}}}}}