{"entities":{"Q1272178":{"pageid":1282928,"ns":120,"title":"Item:Q1272178","lastrevid":70043778,"modified":"2026-04-13T12:03:38Z","type":"item","id":"Q1272178","labels":{"en":{"language":"en","value":"The optimal path-matching problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1226323"}},"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":"Q1272178$BFF3417B-4884-4B1F-8EAF-4902F389464B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0930814260e4cdcafe20e3b1af9699f30a05d803","datavalue":{"value":{"text":"The optimal path-matching problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1272178$EA2283A6-3BCA-4824-A580-2CB1135F2721","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2374f33ef6d2cb5693cd4079c01735920c979241","datavalue":{"value":"0902.05056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272178$33860777-0642-4BC0-8F7B-1344CDFC73E5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"df6feb4a4150dbab93b9c19ceb66869df889d116","datavalue":{"value":"10.1007/BF01215915","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272178$F85A8272-4129-4CD2-8048-8935683218BD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272178$729E4396-F75B-421C-9188-AEA2A54D3907","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"53fb7273221ce117f6a427df8be22cfe791bdb36","datavalue":{"value":{"time":"+1998-11-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1272178$35EA4805-1E02-4DC1-A362-C4C1E83F3273","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d07e147e6d4b7f6c9a66ba9d0d915311a3c0b8db","datavalue":{"value":"Let \\(T_1\\), \\(T_2\\) be two disjoint stable sets in the vertex set \\(V\\) of a graph \\(G\\) and let \\(V-(T_1 \\cup T_2)\\) be \\(R\\). If \\(M_1, M_2\\) are matroids on \\(T_1\\) and on \\(T_2\\), respectively, with the common rank \\(r\\) then a basic path-matching is defined as a collection of \\(r\\) vertex disjoint paths, all of whose internal vertices are in \\(R\\), linking a basis of \\(M_1\\) to a basis of \\(M_2\\), together with a perfect matching of the vertices of \\(R\\) not in any of the paths. This concept is a common generalization of the perfect matching (put \\(R=V\\)) and the common basis of two matroids (put \\(R=\\varnothing\\) and let \\(G\\) be a perfect matching joining copies \\(T_1, T_2\\) of a set \\(T\\)). The authors give polynomial-time solvability, min-max theorems, totally dual integral polyhedral description, strongly polynomial separation algorithms for the convex hull of matchable sets of a graph, and a polynomial-time algorithm to compute the rank of a certain matrix of indeterminates.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1272178$D6108298-2471-4554-9142-C53AB3F6E652","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272178$FCFEA306-824E-4A0C-8DD7-36FFC01801D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272178$DFECE09B-ABA1-481B-93C6-C755483440DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272178$272B9885-FF3A-40C4-A059-458DB885BA17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272178$4F292801-E11F-419F-AF9A-6B0343BD4BB2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2cb621064645332eb6bc4e2fa70b3dc28b38f35f","datavalue":{"value":"1226323","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272178$8ED8F909-561E-4A0D-81AA-3FA77F4DABFA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1303bfe2dfb4941e0ac2b8848e4b3b2a65d1456e","datavalue":{"value":"path-matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1272178$8DA28B27-02DE-4402-9606-65BA0744D58A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e172629663780e971698d7d841046893adba3be5","datavalue":{"value":"matroid","type":"string"},"datatype":"string"},"type":"statement","id":"Q1272178$80DB8D8C-B4F4-45DC-A069-8EFA37793D3B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b60812a9d78b78ae0e61e7a5446d7f2166948b7c","datavalue":{"value":{"entity-type":"item","numeric-id":949789,"id":"Q949789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272178$F81ACE25-C4B8-475B-9B5F-A396CB9F3483","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"060b2dd2e5afe7e5e3537b304c388e955dd07da7","datavalue":{"value":{"entity-type":"item","numeric-id":1300878,"id":"Q1300878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272178$5395D872-A039-46C5-9810-E36D11D79A6C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3a2423d4080d6028a3a8be7e0d0098fe6e3cd478","datavalue":{"value":{"entity-type":"item","numeric-id":226827,"id":"Q226827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272178$E27D8C80-5746-4FFA-9E3D-04D0BEF7B863","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":"Q1272178$F3EC5738-81A7-44D3-B2C9-0E2432509DC2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bc52c634408cea781c9a89772dd9e142cfaba78","datavalue":{"value":{"entity-type":"item","numeric-id":757431,"id":"Q757431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272178$57146FD5-41ED-45F3-A615-99241E739673","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a40f0b6fed8d98fd797a5788f5a6efb24816c99","datavalue":{"value":{"entity-type":"item","numeric-id":1334957,"id":"Q1334957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272178$FC1F8C50-3629-4D65-9F6F-0CF8CC3256A1","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":"Q1272178$E2D4A901-2FFB-4B24-AB11-28B8DB3A6BD5","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":"Q1272178$E5CD57F1-24EC-478D-9C3A-896951274C64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a2ccaa8b67605d1442f748d22b53e4b3e37cf3a","datavalue":{"value":{"entity-type":"item","numeric-id":5564386,"id":"Q5564386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272178$4DD5DC55-AE81-41CF-9BB6-BC2C66FBCCE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb97aa0ae022d4dc38b27f53ae16228cc4072891","datavalue":{"value":{"entity-type":"item","numeric-id":5684698,"id":"Q5684698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272178$D1DDF327-13C0-48AC-BAC5-AFA532F11390","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"145268d761c65c4413252c4f38f08de69481f3c9","datavalue":{"value":{"entity-type":"item","numeric-id":5516086,"id":"Q5516086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272178$EEDE4E9A-3F6E-4A82-B051-76B2B0ACDE7F","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":"Q1272178$436D0A6A-B5A4-4A99-BE7E-369E8E025E3D","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":"Q1272178$A3C046A9-737A-43C0-8A99-BD3A158AB03C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf5cfb2f2955eee0e25d3ce7f764cd1d9e2f0d45","datavalue":{"value":{"entity-type":"item","numeric-id":1050377,"id":"Q1050377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272178$3F0F1625-8796-42AE-A485-30226F41304B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56c6c299e15ddeb001671e573dc9a5439e5a86a0","datavalue":{"value":{"entity-type":"item","numeric-id":3818127,"id":"Q3818127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272178$208E6452-08BC-467A-A1C6-E0D60C888443","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfba955c32dc153431f5c99ab1d6a49daa930c11","datavalue":{"value":{"entity-type":"item","numeric-id":5785127,"id":"Q5785127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1272178$8E7319B7-689E-4A67-8B58-7E0162D49A30","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0edb4d3872e350d2dec5b7929f28c6290f541f3a","datavalue":{"value":"https://doi.org/10.1007/bf01215915","type":"string"},"datatype":"url"},"type":"statement","id":"Q1272178$4A477102-C052-4DE1-BD6F-320D4D8EF6B5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d97ab432d070d453e070cc44d7865777d3b63cfb","datavalue":{"value":"W3160322950","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1272178$803542D8-553C-4D0F-8D62-5F0C26028415","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff07498e29d21d6d4bb87b57c5d743ad355e7f99","datavalue":{"value":{"entity-type":"item","numeric-id":1849530,"id":"Q1849530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb743bb75ce07b9e26587788346035ede26fb923","datavalue":{"value":{"amount":"+0.7895933389663696","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":"Q1272178$51B3CF99-9757-4044-ABBD-47B8572F0E35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa2426d7060c2d0a0d7e5315339fec997c4b67f8","datavalue":{"value":{"entity-type":"item","numeric-id":4737513,"id":"Q4737513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6ede8b1b9b2134d7ed499811b85162d78312786","datavalue":{"value":{"amount":"+0.7866172790527344","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":"Q1272178$5620A744-6A03-46BA-B9EC-20179CC6BBA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd4d12c2c699df9e32e56fccdaca9f596c614268","datavalue":{"value":{"entity-type":"item","numeric-id":760436,"id":"Q760436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb0dfcb362e501bdd6b703ab6a9f35c9b5e1e0f3","datavalue":{"value":{"amount":"+0.7860998511314392","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":"Q1272178$CA10AB96-D745-4824-8E15-33889F324357","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7ccab423933f0b45abe065436483ce71d259684","datavalue":{"value":{"entity-type":"item","numeric-id":4711754,"id":"Q4711754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1cbedeaedc4fe7bea9193a56e12ab36af422c76","datavalue":{"value":{"amount":"+0.7825452089309692","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":"Q1272178$89CC0D30-DA3E-4FEB-8A70-B5019FBAC251","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a36784ee282c900c332375cbd3bf787b071ecb9b","datavalue":{"value":{"entity-type":"item","numeric-id":4393273,"id":"Q4393273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1bc072a815981435d4ec1ce37ac99943ea76313","datavalue":{"value":{"amount":"+0.7811005711555481","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":"Q1272178$DED1AC30-26C7-477A-B8F5-A65ABBD8C521","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The optimal path-matching problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_optimal_path-matching_problem"}}}}}