{"entities":{"Q1813836":{"pageid":1824578,"ns":120,"title":"Item:Q1813836","lastrevid":73017096,"modified":"2026-04-14T09:24:57Z","type":"item","id":"Q1813836","labels":{"en":{"language":"en","value":"Solving the linear matroid parity problem as a sequence of matroid intersection problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5238"}},"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":"Q1813836$8D9486B8-2FF2-4017-B38B-5328C94985A9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3dad684bf17bb42afcc22165253941e565b92b08","datavalue":{"value":{"text":"Solving the linear matroid parity problem as a sequence of matroid intersection problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1813836$F6F29336-5830-476F-9669-CA062EAC71FB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8f04cf19858e5e9db461305409204f74d4a5223d","datavalue":{"value":"0813.90097","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813836$82468C37-7137-4D5F-A03A-5934E32C014A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f40981ba8641981d13ba4888eb4fb19e2ede06de","datavalue":{"value":"10.1007/BF01580854","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813836$87DC7C75-1248-4568-93B8-A91280BE0A0A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"66a05d3cec73c611e907f1d401669479dd6ceb7b","datavalue":{"value":{"entity-type":"item","numeric-id":229627,"id":"Q229627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813836$39C24DBD-46F9-4F63-A79A-EC170152668D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d68969eb59bc55d635a84d469ebb463e264e24ae","datavalue":{"value":{"entity-type":"item","numeric-id":195158,"id":"Q195158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813836$F95A9729-6F8C-4A45-B947-C2447F99BFC2","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":"Q1813836$42EAC315-A320-49EF-A7CA-4176843CA6AB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d3f790682a6be4cc1f3210e15eebe1d6cc5ffbc2","datavalue":{"value":{"time":"+1992-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1813836$2EC314CC-9BAD-4566-94D7-011EB9AD057A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f15c35882d119cf428066f4759f9d998df4357d9","datavalue":{"value":"The authors present an \\(O(r^ 4 n)\\) algorithm for the following linear matroid parity problem. Let \\(A\\) be an \\(r\\times 2n\\) matrix over a field \\(F\\) with columns partitioned into pairs \\(A(1),\\dots, A(n)\\). Find a collection \\(A(i_ 1),\\dots, A(i_ k)\\) of maximal cardinality \\(k\\) consisting of linearly independent columns. This problem is imbedded into a wider class of optimization problems where \\(\\text{card }A(i_ j)\\) is not necessarily equal to 2 and then is replaced by a sequence of so- called ``easy parity problems'' each of which can be solved as a matroid intersection problem. By certain duality results it follows that one can indeed obtain an optimal solution of the initial problem. Some connections with graphic matching problems are considered.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1813836$F957C6CD-3C61-4B5C-B8A1-26D51BD66AA0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813836$08023F01-F8A3-4D0D-BD32-085B03E2E9F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813836$08BA510C-897D-4B92-94FD-3370F5700DEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813836$EFD5146F-D0C2-4E6A-8BC4-AF8B3ED57853","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813836$AE92C9B7-574F-4805-92E7-3984D127CA09","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"09d6d748448a5001791c7ab7b839918d2ac5b5b7","datavalue":{"value":"5238","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813836$6EC77370-F1C5-4C27-B8F0-29FAD71C4A4C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f7848d3309f079fa2f4d5aa56e8ceb401b3c3a2","datavalue":{"value":"linear matroid parity problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1813836$2938FCE6-7D86-4CC5-B40F-80C59DCDB696","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b9e92a1f5ab59d80845abab9abf2fee47c6f36db","datavalue":{"value":"duality results","type":"string"},"datatype":"string"},"type":"statement","id":"Q1813836$DCA64B51-9C78-4850-8601-23F96168FB61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"191ebb3f80abd7df59c2226c73a399fb51fd8fb4","datavalue":{"value":"graphic matching problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1813836$F6ECA5C9-1B33-4742-A67D-EBDDE25FA86C","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":"Q1813836$31663C58-A1E6-497A-998A-EA5BD198C9DD","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"ccc6125135c361af1f78050e3129f0f0a3c2abcb","datavalue":{"value":"Q59592682","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813836$13329C02-958B-45CC-A376-1D4FC2137767","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d518e67a4296de187aa0ca3a2e328808f7d7c7c","datavalue":{"value":{"entity-type":"item","numeric-id":3205014,"id":"Q3205014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813836$3851370B-64FC-4E45-B0F1-73D308FE6578","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93d5787c5b7f19b3f942741d18dc5538998ef73e","datavalue":{"value":{"entity-type":"item","numeric-id":1057288,"id":"Q1057288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813836$0132A743-6615-488F-A5FD-40D50FC4FA0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"441cf76dd02642769e1ea27ecd4aa59c9a85f2d7","datavalue":{"value":{"entity-type":"item","numeric-id":3905324,"id":"Q3905324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813836$7541CE84-84E8-4BC3-9CD2-D7D389806F63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5976b379f44a3a060e7fb3fa16ee81a23819c861","datavalue":{"value":{"entity-type":"item","numeric-id":790834,"id":"Q790834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813836$F702E95E-07A7-4B09-94B4-782D4F83CA65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c39738cea79e11456d6583aec1786d79af209b23","datavalue":{"value":{"entity-type":"item","numeric-id":5341586,"id":"Q5341586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813836$520EC16A-CE14-4616-B0F6-149D1B1E88A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bd8b848f40aaa3f56b8b15df38fbe662aeb1afa","datavalue":{"value":{"entity-type":"item","numeric-id":5516087,"id":"Q5516087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813836$7ED49A67-19CA-42A9-BD13-7CCBCE363EC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4042a6a8925d33e7ac25ffe3a11c3e8654542cc4","datavalue":{"value":{"entity-type":"item","numeric-id":5668601,"id":"Q5668601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813836$1D834618-6FB9-4556-B5B3-C68E06377986","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5af28b9a9a2726877574bce10970dc72b6773750","datavalue":{"value":{"entity-type":"item","numeric-id":5605625,"id":"Q5605625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813836$A0BF790D-7868-48A4-9D52-3719C0F94C44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18c4ba9b7263d128526de6df98df44cbd3a64b10","datavalue":{"value":{"entity-type":"item","numeric-id":1087880,"id":"Q1087880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813836$11ECA860-4295-4D08-9EB0-C1C76621931E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29334cbfed323135d41d245a3ecf67c8d4aa6b93","datavalue":{"value":{"entity-type":"item","numeric-id":3922478,"id":"Q3922478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813836$1D22D373-10BB-4AEF-ADAF-A22EC5E1AE49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1744afac4c45f065c4a9c50861775137377ee1b0","datavalue":{"value":{"entity-type":"item","numeric-id":3849459,"id":"Q3849459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813836$B673F2A7-4B90-464B-A687-DF61E4A938F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3da65c2bc53b3627b9a78b1c41fe14cd29fa936c","datavalue":{"value":{"entity-type":"item","numeric-id":3936197,"id":"Q3936197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813836$432A80F3-74D8-4038-8CE9-FDB1D5B6E2B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58143d24050a576e333cd0e40ebc76a8ad05ee23","datavalue":{"value":{"entity-type":"item","numeric-id":4077061,"id":"Q4077061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813836$D4FAA4D9-FCE2-4BC9-BB7C-7842B6CBA62C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08736496fad7f1ee1630e83b4f57fe1861c09098","datavalue":{"value":{"entity-type":"item","numeric-id":3048571,"id":"Q3048571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813836$DA130319-85AA-4693-A391-4EEFBD1EFDDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6fde6e612a5013658b825ab6c09aafe1f6a1b2f","datavalue":{"value":{"entity-type":"item","numeric-id":1144584,"id":"Q1144584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813836$7C9B2933-A980-4E80-9C69-D0C84BF095BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65dcc08eea8512960dba1ff2b2c89898f6aa9876","datavalue":{"value":{"entity-type":"item","numeric-id":3896158,"id":"Q3896158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813836$9A2053AC-D2CD-477E-A63C-92BD656D63C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fde926b627194404f1d7f20be887beda0c073f1","datavalue":{"value":{"entity-type":"item","numeric-id":1813836,"id":"Q1813836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813836$B40901EF-B788-4297-A989-B70F4BB9A7DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0050e04cd523c25072c5f0f9c9964b473a93b40d","datavalue":{"value":{"entity-type":"item","numeric-id":4080661,"id":"Q4080661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813836$2AB67E17-D63D-4CEE-A44B-9AF766FDFD71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90ed4bb74897967e21e507cbd01412480f226a43","datavalue":{"value":{"entity-type":"item","numeric-id":1199466,"id":"Q1199466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813836$919BA352-44AC-4A6C-B14B-127339100953","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"41f86ec124133199a2424e9ff4404a757ac353bd","datavalue":{"value":"https://doi.org/10.1007/bf01580854","type":"string"},"datatype":"url"},"type":"statement","id":"Q1813836$B34B40E9-439F-4B71-9457-F41E53817059","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"531b54db0c1a3a12006923b459087e5da090b610","datavalue":{"value":"W2154896222","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813836$4255B4C2-C1ED-43F3-AF91-FCCBB722AF53","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"038e00b9b1dc7dcd90c83db6fe538589b98b5af3","datavalue":{"value":"journals/mp/OrlinV90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813836$00326499-A9D6-4E90-9218-5A9682A57149","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e988b87e3afc6ab455fb20b87addbd4c24d6d446","datavalue":{"value":{"entity-type":"item","numeric-id":3503851,"id":"Q3503851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c0e352bee1ca5ec8e66b1994c9abe66b2b989c3","datavalue":{"value":{"amount":"+0.9002832770347595","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":"Q1813836$96E944BD-59EE-4729-B4EB-9C351815D798","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6ea6aa46c7b6950af4a6c5fe0b5ea244494e27e","datavalue":{"value":{"entity-type":"item","numeric-id":5149751,"id":"Q5149751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9552f9fe6f335f054519f0b2a60e3b4369eb1bd","datavalue":{"value":{"amount":"+0.8765142560005188","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":"Q1813836$48F664F2-3ED2-4FB4-8307-6875851FDBF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"851ba66d5ab7aa122999ae774cddec0cb924ffd1","datavalue":{"value":{"entity-type":"item","numeric-id":1087880,"id":"Q1087880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3f1dc76d088e9ef396071d8070e45809cae4fbe","datavalue":{"value":{"amount":"+0.8764846324920654","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":"Q1813836$6B986C9A-6556-47E5-8FA8-B474F8F1F7FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f75bcb504de5a1c215d8e1c1086f96817947c86b","datavalue":{"value":{"entity-type":"item","numeric-id":4977977,"id":"Q4977977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6ebddc05e43f8df7439c42de28378b6d713d5e6","datavalue":{"value":{"amount":"+0.8751252293586731","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":"Q1813836$5AB77FB4-D8D3-4518-B9C7-D25053D3B28C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a10b314753117eece9d6a4dd5fc511c87a2dbf7d","datavalue":{"value":{"entity-type":"item","numeric-id":2799476,"id":"Q2799476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12151571b3439d40f8e2c56fccaa0493c3531568","datavalue":{"value":{"amount":"+0.8739516139030457","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":"Q1813836$3C0DDDBD-9AF3-40A1-B531-27087E2A1644","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Solving the linear matroid parity problem as a sequence of matroid intersection problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Solving_the_linear_matroid_parity_problem_as_a_sequence_of_matroid_intersection_problems"}}}}}