{"entities":{"Q1089347":{"pageid":1100099,"ns":120,"title":"Item:Q1089347","lastrevid":49064221,"modified":"2026-01-06T13:20:21Z","type":"item","id":"Q1089347","labels":{"en":{"language":"en","value":"Decomposition and optimization over cycles in binary matroids"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4004202"}},"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":"Q1089347$1510B9FE-FFA0-45EA-A461-01163F0757F8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8f3b0431e37b3f10e6ee8b394121b58e91882181","datavalue":{"value":{"text":"Decomposition and optimization over cycles in binary matroids","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1089347$7F607008-8500-479F-B5AE-813DC5741D4D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"194b4e5e51e6ce64369d1ba1ded0eb0b38a707f3","datavalue":{"value":"0619.05017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089347$AA7ACF75-ABBB-4086-B012-741135DDA2CE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"720ec376003131c234a08e24cb3576d464b1d42b","datavalue":{"value":"10.1016/0095-8956(89)90052-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089347$7ED7BE34-DE35-42A4-93DE-91E4E29EB907","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089347$118961CE-D325-4E2C-83BB-E8E880553107","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":"Q1089347$3131AEF3-8D11-4D19-88F7-32A6D2F9650C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e8c310a66967dd935b36a6402ea4897a19f32362","datavalue":{"value":"For \\(k=2\\) and 3, we define several k-sums of binary matroids and of polytopes arising from cycles of binary matroids. We then establish relationships between these k-sums, and use these results to give a direct proof that a certain LP-relaxation of the cycle polytope is the polytope itself if and only if M does not have certain minors. The latter theorem was proved earlier by Barahona and Gr\u00f6tschel via Seymour's deep theorem characterizing the matroids with the sum of circuits property. We also exploit the relationships between matroid and polytope k-sums to construct polynomial time algorithms for the solution of the maximum weight cycle problem for some classes of binary matroids, and for the solution of the separation problem of the LP-relaxation mentioned above.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089347$84E0B1DA-BA32-410B-9413-F16349ED9EA0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089347$2809DA1F-0D91-472C-94D9-74356F935AF9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"63c87fc0c6af54edf5c9a145d18b6432460a7f86","datavalue":{"value":"4004202","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089347$FC18B69C-30D4-406D-93BD-D00B2F8F2FB6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dcf267cbc3e04fdcfc3d3761f7ad8ebdabe8c51","datavalue":{"value":"cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089347$31EC7B0C-13F2-4451-B8CE-61ECDB2F9DAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b5f7b05178a8c240df527c2a2a0381e9b08b821","datavalue":{"value":"binary matroids","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089347$F00E5257-4D6C-4038-8DC1-53CA04F24671","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"86fcf45d936f4bf2023581e45aa8701bea035b70","datavalue":{"value":"polytope k-sums","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089347$0495A449-9AFE-464F-A49C-89B7C381942F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089347$496D2289-1306-41AA-91B0-551890B4097F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc043404c376f0e03d5905bb5b50a29b5bbcaeab","datavalue":{"value":"maximum weight cycle problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089347$FBA041A2-8ECC-4844-B856-D44656F5B2AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b7c0e17209dc198bb180923e84319681bc34018","datavalue":{"value":"LP-relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089347$243F1CEB-89B0-4887-84BB-198B07661E5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ae6ae643d8151e8ac1260226e3b479503ec81a8","datavalue":{"value":"matroid k-sums","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089347$2BD420DD-A10C-4C5C-BCE9-4EB025E046F3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c79d63a974620aa9dd22e3cdec2e56a2714b61d9","datavalue":{"value":{"entity-type":"item","numeric-id":202055,"id":"Q202055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089347$2E8772E5-8616-4D87-AB8C-BA38513B0AD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bcefb4747bbb5a6ab761f4e4fe82c408184c2849","datavalue":{"value":{"entity-type":"item","numeric-id":1386418,"id":"Q1386418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089347$A96F6B03-6650-4ED8-A907-02F76EC97277","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":"Q1089347$63DB78AD-DD0A-48B6-B1F1-8DA6F6D1BB4D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"175916359d5356dd13dd1efc4a7517f1e19ef4c3","datavalue":{"value":{"entity-type":"item","numeric-id":593988,"id":"Q593988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089347$E6850CC6-949B-4EFA-B172-E10736B778A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3be975c66d7175c7bcf1d2da2353e25f3e227505","datavalue":{"value":{"entity-type":"item","numeric-id":1078187,"id":"Q1078187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089347$9DB5E5D0-6CCC-4786-9580-CC74162D8CFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3579586fb626b1c5c75ff4f3e160e0618a115d2b","datavalue":{"value":{"entity-type":"item","numeric-id":3790963,"id":"Q3790963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089347$EC5629ED-CEC6-45FE-8845-B9C2E3A06F2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"871b0b619dcdcfea503ebb95e9e10caab2448bd3","datavalue":{"value":{"entity-type":"item","numeric-id":4726054,"id":"Q4726054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089347$8ABA31AB-81C4-451F-9F90-61D5BFC4A94C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5689fa65385b2c188bfb367432ebbda01751a974","datavalue":{"value":{"entity-type":"item","numeric-id":3800056,"id":"Q3800056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089347$C122DB91-4F0D-4602-B2E2-50FF2DC024EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c211e55116d68a1af38ddb2786888a3b5b61452","datavalue":{"value":{"entity-type":"item","numeric-id":3773723,"id":"Q3773723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089347$48702940-F56E-45A0-B100-59331C01EB1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4b70304ff30a1256f46103099164d048b244266","datavalue":{"value":{"entity-type":"item","numeric-id":4766817,"id":"Q4766817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089347$CE652998-8622-493E-A66A-43B063E6F90F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f12e6198b78831ce91556d24190a3c986ef0555c","datavalue":{"value":{"entity-type":"item","numeric-id":1142044,"id":"Q1142044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089347$DD3BF373-D719-4ED8-B65C-1AC46A1C8842","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089347$99B5118E-0EF2-4EA1-B6F5-FDB587F79733","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":"Q1089347$2E035C37-B01F-4609-A241-5A785467D6D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"849849a8734e624cdd488bd27603bced49d0bfd9","datavalue":{"value":{"entity-type":"item","numeric-id":4083698,"id":"Q4083698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089347$80C6D1E2-823B-4B0A-8C39-A0E25EFF46A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ff469158b0917cd489eec9d6ddfd641a6e6e677","datavalue":{"value":{"entity-type":"item","numeric-id":5659589,"id":"Q5659589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089347$838B888A-2A47-4C38-80DC-768AC3F0A6AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4fa5c0efe0c39997534bb44636c6730a4e42c655","datavalue":{"value":{"entity-type":"item","numeric-id":3965907,"id":"Q3965907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089347$A4877371-F816-447E-99AC-AC2B87E11430","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62d035f421ab9bd8eaa29b517b29669cf50cb87e","datavalue":{"value":{"entity-type":"item","numeric-id":1144028,"id":"Q1144028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089347$03C70EBF-1E43-4B67-9718-E262D359E15E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d93131d3cdff5a369acc96e6fde7360525e3cc8","datavalue":{"value":{"entity-type":"item","numeric-id":1161527,"id":"Q1161527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089347$41C99020-F1C8-4BA4-9451-8D55ECA25D35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d237445f955b64141b9b786a4b5ef01d494bebe","datavalue":{"value":{"entity-type":"item","numeric-id":2266019,"id":"Q2266019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089347$2E5DAEF9-2366-45FE-ACAF-7795F202FD4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5895c31c7676da31d32ada4f046c4900e2df10c2","datavalue":{"value":{"entity-type":"item","numeric-id":801076,"id":"Q801076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089347$F9A97CA7-BA99-44D4-844D-BA0CEDFF1B92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1973bddc90e2d162d77e68ae147af490f772483","datavalue":{"value":{"entity-type":"item","numeric-id":2639863,"id":"Q2639863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089347$4E083A48-EF81-4D45-8C7D-B3BC3FC9FCDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16ee6ba21410efd14ddd2a024a73c0ed4e5a2745","datavalue":{"value":{"entity-type":"item","numeric-id":4111952,"id":"Q4111952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089347$D4C22ADB-A686-45A4-ACEA-D369556A5DC7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f383971394e920f387a4ffc7e5a77a859de1c169","datavalue":{"value":"https://doi.org/10.1016/0095-8956(89)90052-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1089347$17CDD9F9-3ABB-4240-85F6-9E008540C646","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"37a99b425303a2845f9803b4d124a38d9df5340f","datavalue":{"value":"W2088799722","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089347$BFAA1EB0-FB7C-4088-BA50-3B6C99F412E2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9b53f13121e52d4e12c09371ee058850215beda","datavalue":{"value":{"entity-type":"item","numeric-id":1824625,"id":"Q1824625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98f90a7b1b7d4d29271ddbfac56f06f93809d2d7","datavalue":{"value":{"amount":"+0.8039618730545044","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":"Q1089347$6E461719-0524-47D8-BBE0-20580A82E825","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"810d750c59b0f50095cc1e2d93a7244b9073d2c1","datavalue":{"value":{"entity-type":"item","numeric-id":1078187,"id":"Q1078187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"170885a5708774964eb38f219d268e0565d79bf3","datavalue":{"value":{"amount":"+0.7971835136413574","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":"Q1089347$EF0507F0-FB2F-42AA-8192-79B1B41D7424","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0388f5cfd6b34862b980a4a516f969d3274cb470","datavalue":{"value":{"entity-type":"item","numeric-id":801076,"id":"Q801076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a08dd4a6017d5cc40624c439c12a04b32ba6533f","datavalue":{"value":{"amount":"+0.7697901129722595","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":"Q1089347$90F7E481-F680-4670-AB3F-54A197C20F24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d63ccfccfeed1ffaefdaf5803f6fa4daad8dd753","datavalue":{"value":{"entity-type":"item","numeric-id":4726018,"id":"Q4726018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80a8dfeef3db99ff5437bfb9cddc4ca334dbf090","datavalue":{"value":{"amount":"+0.7673039436340332","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":"Q1089347$2E30A2FF-BC44-4CD6-BBF8-264D1E3616A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af52a525acff5664e2d4e1c73e7e207355f49fd1","datavalue":{"value":{"entity-type":"item","numeric-id":1063610,"id":"Q1063610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7c27e6a35b800c47c8d5fe3165b0a0e13cec599","datavalue":{"value":{"amount":"+0.7629423141479492","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":"Q1089347$ED697C0D-BD3D-4B27-8D23-E9C893B9EA98","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1089347","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1089347"}}}}}