{"entities":{"Q1119951":{"pageid":1130700,"ns":120,"title":"Item:Q1119951","lastrevid":69690822,"modified":"2026-04-13T08:44:45Z","type":"item","id":"Q1119951","labels":{"en":{"language":"en","value":"Polyhedra related to undirected multicommodity flows"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4099376"}},"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":"Q1119951$C7EBAB32-38FE-4778-B15C-AE80C683711F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f5ff6a539f212df162f0654f51cd23840dd677f1","datavalue":{"value":{"text":"Polyhedra related to undirected multicommodity flows","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1119951$69C16768-7A3E-4E1C-AE5F-328F3CA5CA50","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d8f8ca889ec0362daeb02affd4aa8a84b1246d4b","datavalue":{"value":"0672.05077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119951$27E0EDEE-847F-4ED4-BBFD-35754C1D1491","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"de9d9d91be489b2e4a0c302fd37153a7187d3d35","datavalue":{"value":"10.1016/0024-3795(89)90468-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119951$09945A32-EB92-4EAD-A754-BF11EE355930","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8de031de05325b44570d0c47c3ec8813873d565c","datavalue":{"value":{"entity-type":"item","numeric-id":92813,"id":"Q92813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119951$4CC519CF-83B3-468B-B6BA-5E77C9DE2504","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1119951$0C9BF663-76F8-421C-A238-D1DE9387BAE9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"56c51d0ca463b9ab7b9d4c9d42cbd1df63b91d54","datavalue":{"value":"The author associates with the two undirected graphs \\(G=(VG,EG)\\) and \\(H=(VH,EH)\\) (\\(VH\\subset VG)\\) an unbounded polyhedron \\(P(H,G)\\), refered as a dual flow polyhedron. For the graph \\(H\\) is defined an integer index \\(\\nu\\) (H) as the least positive integer \\(k\\) such that each dual problem (in the linear programming sense) to a maximum undirected multicommodity flow problem with the ``commodity graph'' \\(H\\) has an optimal solution that is \\(1/k\\)-integral \\((\\nu (H)=\\infty\\) is such \\(k\\) does not exist). This numerical characteristic \\(\\nu(H)\\) of the graph \\(H\\) is also expressed in the terms of the dual flow polyhedron \\(P(G,H)\\), as the least positive integer \\(k\\) such that each vertex of \\(P(G,H)\\) is \\(1/k\\)-integral for any \\(G\\) with \\(VH\\subset VG\\). In the paper, one shows that \\(\\nu(H)\\) can be only 1, 2, 4 or \\(\\infty\\). Some properties regarding extreme rays of certain cones related to the dual flow polyhedron are also obtained.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119951$1D0F4A31-C18C-431B-9AC8-CC46592D27FE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9224c061da78670cd51103388d6e8594567f03bd","datavalue":{"value":{"entity-type":"item","numeric-id":593488,"id":"Q593488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119951$81F2CB2C-3B18-462C-B51F-2B8424415E65","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119951$55800874-A306-4ACD-AB74-A905E3EB9B21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119951$76BBE038-D0E0-456D-B2C1-C34A3E21EC4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119951$05E391FC-FB7E-4D49-9A39-C170DC677E28","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e93e129aa34bcc534a9e15e17a93cebe40d9fd95","datavalue":{"value":"4099376","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119951$B7D9FD9B-EAF9-4AA4-9411-8F4AD46E260F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"349fe8b51d5e5a4d743195e115d98cccb53f925f","datavalue":{"value":"undirected graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119951$41EE176B-471C-46B4-AEE3-4B76AE7C9B7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c51cd2418e1a453fca7a510eacf3309373b3a2f8","datavalue":{"value":"multicommodity flow","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119951$D9442FE6-394D-4D8B-8374-7777FF08392C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7fee866d495e055626a4973cd9ba1d391166beb5","datavalue":{"value":"flow polyhedron","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119951$20FDF45F-A62D-47CD-B87D-18CE429B500E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"14fc360ec3034cf7b4974dd2757eb533d1dfaac7","datavalue":{"value":{"entity-type":"item","numeric-id":423889,"id":"Q423889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119951$53AA365D-CD19-4C1D-A6CB-5A55FA53EB3C","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":"Q1119951$66C60BF2-2166-4C80-A2C1-0E5DD8BA67FA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2e2b90ac5d6e129e9b796ef34c8006dcc3dbc850","datavalue":{"value":"https://doi.org/10.1016/0024-3795(89)90468-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1119951$88C5523C-A203-4469-97FD-435F2CE71BD2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"93ddf0a1e0dcb999b83fecb6083023038cdd9622","datavalue":{"value":"W2093030792","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119951$9E85AE9D-B831-4E32-AD43-B7774A9028BC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d023d84012aa79a4d7052bfa00099bb341d3b65a","datavalue":{"value":{"entity-type":"item","numeric-id":3921264,"id":"Q3921264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119951$5C110061-C4BA-4815-831C-D1F52F89D26A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"831dfbc4b1904a2992c4e73f973bc64e76a89438","datavalue":{"value":{"entity-type":"item","numeric-id":4124571,"id":"Q4124571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119951$980B11C0-8C12-4D37-A08D-10FF9EC526A4","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":"Q1119951$A20D690F-6B35-4F11-BD36-53124EC221D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cb2ca458acea0e3632727170dcd237e7765fa59","datavalue":{"value":{"entity-type":"item","numeric-id":5514188,"id":"Q5514188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119951$1C84BA86-6280-45D2-8CD6-CDD1BC9B11A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53e93f3e4d6e9828b6844029e6725d07275ebd57","datavalue":{"value":{"entity-type":"item","numeric-id":5620998,"id":"Q5620998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119951$0D67EE18-510A-4B4F-ABC4-AB0112B39277","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c571b640c1516f4ca2b62caa77bbdebe8bf825d0","datavalue":{"value":{"entity-type":"item","numeric-id":5736116,"id":"Q5736116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119951$4403A054-59E9-4F26-99E2-30A98C1E680D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cea38d4e6028654c1ca2f588cb248138019a5cf0","datavalue":{"value":{"entity-type":"item","numeric-id":3718457,"id":"Q3718457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119951$5889A37C-972F-420E-AA29-64875B3462CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b03461ee25ea8af49c4bef8544dc371d11ade7d","datavalue":{"value":{"entity-type":"item","numeric-id":581412,"id":"Q581412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119951$2B6F2FDF-5A49-4374-B4D7-32A431FCBA78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94d2a2c8b0085121d5b94f1a2ae67970509c7427","datavalue":{"value":{"entity-type":"item","numeric-id":3979310,"id":"Q3979310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119951$D863A5FC-6CC8-4A39-BE98-D51CF6B2FC4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59525b86f8dbf7588d62cc1cdd559eb591111374","datavalue":{"value":{"entity-type":"item","numeric-id":3856789,"id":"Q3856789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119951$FBDACD06-09F6-4FE2-A2B2-952B47F0C8F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02221e1c0a69913c7a96c3912f027efbe9cb7d68","datavalue":{"value":{"entity-type":"item","numeric-id":1080357,"id":"Q1080357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119951$98A9AAD9-469C-4EB9-90D5-1E05230BB2A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6dfa3f920ab16949a508ca8ac1782b38c4a9235","datavalue":{"value":{"entity-type":"item","numeric-id":4106238,"id":"Q4106238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119951$7B1FB475-CAA0-45D1-8F9C-DE72B1EB55D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e173cfa95c953e77461a4540ccbaacc3f214870","datavalue":{"value":{"entity-type":"item","numeric-id":1236549,"id":"Q1236549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119951$EE850ACB-C188-4680-BEF4-AF063AD5CDBC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0443f581b2c8de360ef63c7373b447b480407efa","datavalue":{"value":{"entity-type":"item","numeric-id":3722231,"id":"Q3722231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d0149817a52a74b525abc62f96366e272c52c0d","datavalue":{"value":{"amount":"+0.8414744734764099","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":"Q1119951$7AB48446-A5AE-4F08-B1FF-D2A151814A55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8d7c7e0a3f4e03d775a61598600bea86fb48b70","datavalue":{"value":{"entity-type":"item","numeric-id":5938940,"id":"Q5938940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c579a92799a531d13fb0f0fb24aa12de02d40dc","datavalue":{"value":{"amount":"+0.8339238166809082","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":"Q1119951$1F07341B-7157-4929-9A79-821C8FA5DFCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75dc15c6ee31a05b6c07c5e61c7869c5913977e0","datavalue":{"value":{"entity-type":"item","numeric-id":3471824,"id":"Q3471824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3143c020913386d46c1e0ce985f51d2bf5835edf","datavalue":{"value":{"amount":"+0.8060271739959717","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":"Q1119951$107E19BC-4446-4785-8A95-3703E8641019","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8b30d307ac08210c2f13dfd8a4027a498c10fb9","datavalue":{"value":{"entity-type":"item","numeric-id":1337137,"id":"Q1337137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1cb3cf814f3065c8c893bd821d076c4566b591a","datavalue":{"value":{"amount":"+0.7928549647331238","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":"Q1119951$C2E56B65-3E1A-43D5-B2B6-13C4B2BDB6C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd1ab24d3dcaf223bdc1737ca1027936a51d1c16","datavalue":{"value":{"entity-type":"item","numeric-id":4305228,"id":"Q4305228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8fe760a0d23406df08c645b10ce8dac1f324de4","datavalue":{"value":{"amount":"+0.7908180952072144","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":"Q1119951$879B3BD3-0E0E-403F-BB9D-65FF67A23271","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Polyhedra related to undirected multicommodity flows","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Polyhedra_related_to_undirected_multicommodity_flows"}}}}}