{"entities":{"Q1107418":{"pageid":1118167,"ns":120,"title":"Item:Q1107418","lastrevid":69657738,"modified":"2026-04-13T08:30:52Z","type":"item","id":"Q1107418","labels":{"en":{"language":"en","value":"On greedy algorithms for series parallel graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4064734"}},"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":"Q1107418$C18D8733-0757-4E8E-96B8-16B7B42C58E4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ed3586256df8a070a1bf0a66dd65aab3731ffdcc","datavalue":{"value":{"text":"On greedy algorithms for series parallel graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1107418$00C0903F-AD04-41F3-A3AB-0C70E72F781F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"909f77c5388038bbc0fe4da2352c2dee41caebcd","datavalue":{"value":"0652.90040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107418$C3AD6EAC-0960-4CAF-BFB6-A1B5BC83C3FB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"aa1cc76fee8323df88e0b897301ffa148a3bc314","datavalue":{"value":"10.1007/BF01580730","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107418$6ACB5E9B-6862-4F13-B41B-F74D5268F315","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ee4258796aef3438234ce9af2cb267f584374cd3","datavalue":{"value":{"entity-type":"item","numeric-id":172224,"id":"Q172224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107418$40B5E482-6338-4B12-9865-F033AB555F85","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":"Q1107418$F597C812-111B-49AF-A514-62DDD64074E6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1107418$A6880C90-72FE-4512-B652-952C0DA466ED","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"56082357e7bb5f86d7e5a6e451ff41b85e7c6c82","datavalue":{"value":"Let G be a directed multigraph with single source s and sink t, \\({\\mathcal P}\\) the set of all s-t (directed) paths, b: E(G)\\(\\to {\\mathbb{R}}_+\\) an (edge-)capacity function and c: \\({\\mathcal P}\\to {\\mathbb{R}}\\) arbitrary path- costs. The problems, the author is concerned with, are  \\[  \\bar P(v):\\quad \\max \\quad \\sum_{P\\in {\\mathcal P}}c(P)x(P)  \\]  subject to (1.1) x(P)\\(\\geq 0\\) for all \\(P\\in {\\mathcal P}\\), (1.2) \\(\\sum_{e\\in P}x(P)\\leq b(e)\\) for all \\(e\\in E(G)\\), (1.3) \\(\\sum_{P\\in {\\mathcal P}}x(P)=v\\), and respectively, \\b{P}(v): minimize the objective function under (1.1)-(1.3).    The author proves that \\(\\bar P(v)\\) and \\b{P}(v) can be optimally solved by a greedy algorithm, if G is a series parallel graph, c is obtained by the (edge-)values b(e) in the following way: \\(c(P)=\\sum_{e\\in P}b(e)\\) and c obeys some simple algebraic (associative, monotonic) and lattice- theoretic properties.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107418$388719A8-B901-42FC-90CB-F0F7238193BA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107418$33351F0D-A36F-446A-A169-F7C6ADFE5CC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107418$A947044A-0F9D-4AD0-AC90-1567B63060B0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5bc836c8d211bac47ad48905e7b00c845c41723e","datavalue":{"value":"4064734","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107418$F27A2C3E-96F2-4E07-9EBC-CE987E36F1DD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f32d4a1d018dceab52f3ba66e904db90572a4744","datavalue":{"value":"flows in networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107418$F6738EFE-7670-4A87-827C-D64A700999C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cba135ceaab219aa7e7fbb5a7495b632414c149b","datavalue":{"value":"single sink","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107418$4FE993E0-39DF-447C-B897-799F8CE8882E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"795038535c1843a543770d88a0341810d184a5f2","datavalue":{"value":"directed multigraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107418$9FE5C9C2-27B2-4F63-BBD4-ED5D57DD188C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f231000319642461d590d09185d49b65f49ff416","datavalue":{"value":"single source","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107418$E82DED93-5D1C-417D-9C86-F21053000DC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e1e7eb452ae4c92c43fa47bb0afb8177365a429","datavalue":{"value":"greedy algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107418$CB15A218-3782-4373-B1CA-C3684EF15875","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"28a04a7cb62acb07d997278b9f659c67c89e2b89","datavalue":{"value":"series parallel graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107418$7E2D9864-30C3-4BE3-B132-43724DE8446E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"111aa4d205b7adb5a8dca99e52744f61a537d2b5","datavalue":{"value":{"entity-type":"item","numeric-id":647398,"id":"Q647398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107418$9C417308-770B-49AF-91C2-DB495C482055","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":"Q1107418$D0A05654-7815-4AD7-B186-278AF7C106DC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b83184611205ddd07c2058fe0b4319aebfd3d50","datavalue":{"value":{"entity-type":"item","numeric-id":3694985,"id":"Q3694985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107418$8C4D30A4-8D2C-4E9D-BB54-FC3738E435B1","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":"Q1107418$236A3C0A-2FE4-49B9-A6B2-007AC6981A37","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cf08d9eff587bb75f861b21cb6452c7f6abf7f4","datavalue":{"value":{"entity-type":"item","numeric-id":1088884,"id":"Q1088884"},"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":"Q1107418$D94F66CE-3689-4907-8AE3-1191E88E5366","rank":"normal"},{"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":"1b6c7367d35bd8aff6dec738aca60bafe26c30c6","datavalue":{"value":{"amount":"+0.8668043613433838","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":"Q1107418$9B2A6636-F698-4E84-9185-15067C1D54E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a51648e35d51353c93a6cf1b8c11cb39160f5cc","datavalue":{"value":{"entity-type":"item","numeric-id":1110543,"id":"Q1110543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94e08062609101016dacb19083d5c06f01873241","datavalue":{"value":{"amount":"+0.8557611703872681","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":"Q1107418$A54DA7F9-4CC0-4AF9-891C-6B066B61F5A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4910f52c52d379ecfdc0893b04c16823bf6ce317","datavalue":{"value":{"entity-type":"item","numeric-id":3737235,"id":"Q3737235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ad4dffe77adbfd6131e31837b66835b92d24e39","datavalue":{"value":{"amount":"+0.8206355571746826","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":"Q1107418$CEB0AF1E-3E54-4051-82C7-8DBC94C2A1F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e110f3012765bb31e0326aba55ae015dd0590506","datavalue":{"value":{"entity-type":"item","numeric-id":2445843,"id":"Q2445843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d4145763b1d790b758f90be9e865ab520a1b49a","datavalue":{"value":{"amount":"+0.8054859638214111","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":"Q1107418$515A4E2B-70B3-4AF8-B3D1-AAF5B1E6E610","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On greedy algorithms for series parallel graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_greedy_algorithms_for_series_parallel_graphs"}}}}}