{"entities":{"Q2288180":{"pageid":2298923,"ns":120,"title":"Item:Q2288180","lastrevid":56738943,"modified":"2026-03-23T10:35:29Z","type":"item","id":"Q2288180","labels":{"en":{"language":"en","value":"An Edmonds-Gallai-type decomposition for the \\(j\\)-restricted \\(k\\)-matching problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7152777"}},"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":"Q2288180$7C35E449-03D7-443C-9E8E-4DEDBDE866D2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4fb7fc9ab0e26c44024b2efcd639570b2ddac4f6","datavalue":{"value":{"text":"An Edmonds-Gallai-type decomposition for the \\(j\\)-restricted \\(k\\)-matching problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2288180$8CC29E51-F8BB-48FA-B031-6A1F67DEECDA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1ac93948d2f86ecf71e7d4dc2c61fc7cf56fbe89","datavalue":{"value":"1439.05191","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2288180$BE4F4C51-4680-4D11-B34B-649A3B096B4E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9bafd4df5fd1ce2c88e3cd389eb5451a188220c3","datavalue":{"value":"10.37236/7837","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2288180$3C376BD7-3150-4936-8381-5AD77D9D5C3D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6142b9e713ad64767392c697fabf8de0da39b266","datavalue":{"value":{"entity-type":"item","numeric-id":189538,"id":"Q189538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288180$3B325318-CD97-4E1F-8C3D-72AB512F9BE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1eefaf233eae8ff00e235a9fc871d569a149bb40","datavalue":{"value":{"entity-type":"item","numeric-id":301118,"id":"Q301118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288180$C3A04D22-09BF-4F0A-AF76-46E593191C55","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288180$6318CC89-2219-4C90-9944-BBE80B1BD27F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8a6a5b5fdeb4bedfada8cbabb8db67346705498a","datavalue":{"value":{"time":"+2020-01-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2288180$87922839-E15A-4F74-8AA7-56693953EB66","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a230d2b61c7ef8cda5d517228ca06bb46c1dd006","datavalue":{"value":"https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i1p15","type":"string"},"datatype":"url"},"type":"statement","id":"Q2288180$5D42FCE8-0DC5-4E93-9A27-C4220B2C8BB3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ed87c82cb58f90bdffba2eff1b0a4b4945b2acc7","datavalue":{"value":"Let \\(G\\) be a simple undirected graph, and \\(j\\) and \\(k\\) be two integers such that \\(j\\geq0\\) and \\(k>0\\). A \\(k\\)-matching of \\(G\\) is a subgraph \\(M\\) of \\(G\\) with no isolated node and degrees at most \\(k\\). A \\(j\\)-restricted \\(k\\)-matching in \\(G\\) is a \\(k\\)-matching whose each connected component has more than \\(j\\) edges. Recently, \\textit{Y. Li} [Math. Oper. Res. 39, No. 3, 930--948 (2014; Zbl 1309.90088)] investigated the maximum non-negative node weighted \\(j\\)-restricted \\(k\\)-matching problem, presented a polynomial-time algorithm and a min-max theorem for \\(0\\leq j<k\\), and verified the NP-hardness of the problem with unit node weights and \\(2\\leq k\\leq j\\). In this article, the authors obtain an Edmonds-Gallai-type decomposition theorem for the \\(j\\)-restricted \\(k\\)-matching problem with \\(0\\leq j<k\\), and pose an alternative proof to the min-max theorem of Li [loc. cit.] using the analogous decomposition for \\(k\\)-piece packings given by \\textit{M. Janata} et al. [ Electron. J. Comb. 12, No. 1, Research paper R8, 21 p. (2005; Zbl 1062.05119)]. These results are important and interesting.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2288180$ABA943D5-F1A0-4BF7-BFCD-5A33A240761F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2288180$9B95D249-8401-4B01-9ACF-B7E3E6329598","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2288180$E8558B7F-7032-4435-A5C1-C54AAF1B22DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2288180$D2A1260B-1D82-4A68-9D84-E78557F3383E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8f120e05f287d33f0e1961bf9cb59f1ef67bec01","datavalue":{"value":"7152777","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2288180$B2B51D7A-0161-4C3B-AFDA-7F9149A06DFF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"86ed74255876e24a0b2f03099efb2006814044da","datavalue":{"value":"\\(k\\)-matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2288180$39B65C02-7AF4-44D3-8F0F-A14F3903CB5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"12fce99dc46bad1c468a0805b2e66e0973fe4dce","datavalue":{"value":"\\(j\\)-restricted \\(k\\)-matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2288180$F5139E62-E142-426E-9C36-A0AE6D0CB6BB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"999fe16790e0a94f054fbae70eaba34b3e52a6fb","datavalue":{"value":{"entity-type":"item","numeric-id":1753363,"id":"Q1753363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288180$97FFED0B-541E-4D9A-B545-707F7035AA54","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":"Q2288180$15AB19B0-25DE-4AC2-A75C-5ADC0991BE16","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"428f93b468b33432489f77ad8b05e3243f5e904c","datavalue":{"value":"W2999246665","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2288180$C5E2EFBB-13A5-4F61-AB10-30CA690FB028","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3826395f74e3a23428a80ecf75f2bac6385da4d","datavalue":{"value":{"entity-type":"item","numeric-id":3258698,"id":"Q3258698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288180$0D5167DF-A05E-4BBE-BE0F-D80FCAA1D5D9","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":"Q2288180$13B34031-3D09-4AE0-8643-2730B7ABA083","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3de7edad0b76fa41f3d5b9d1b0f37d5e44dc7a8a","datavalue":{"value":{"entity-type":"item","numeric-id":1166429,"id":"Q1166429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288180$F6A1D975-937E-481C-A165-4967CAD8EB7C","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":"Q2288180$933EDF99-26A7-434A-A0A4-1B84AFB17E00","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":"Q2288180$D59EB4EC-856A-41E2-9D42-3BFA683D9D6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4d4fb0d146535ef37cc221544e998161ff87740","datavalue":{"value":{"entity-type":"item","numeric-id":5520564,"id":"Q5520564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288180$E7BEF539-FA0B-41B5-A5B2-16AD6BB1DF7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27e093fcbe4441a8d440b367abd1fad244ac99b7","datavalue":{"value":{"entity-type":"item","numeric-id":5508779,"id":"Q5508779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288180$F91D2F60-EF95-4AA0-86D3-2421C9B315A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a468a41e4ed3074db6ce47551148d0ac0f046132","datavalue":{"value":{"entity-type":"item","numeric-id":5486279,"id":"Q5486279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288180$D1929D23-8933-4230-A3BE-A516CCA40AFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b97f750e9c8b6509ac6238c920a51525b82dd93","datavalue":{"value":{"entity-type":"item","numeric-id":1068852,"id":"Q1068852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288180$B597E630-E7BD-466A-BF68-2DDA89A7C896","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da3a773dff4ecd7f633b223d105cd8d91ff17f80","datavalue":{"value":{"entity-type":"item","numeric-id":1773199,"id":"Q1773199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288180$99D35CBB-B449-401E-B396-E1D1C91EBF39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7256850b21cc9f1165b43c6f901496c1cf5c4057","datavalue":{"value":{"entity-type":"item","numeric-id":1400955,"id":"Q1400955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288180$A23B8F49-DB95-4430-8092-70B9ECA4D5AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d28b3ca54d4e82f37382e7b48dee1e95cdc3143","datavalue":{"value":{"entity-type":"item","numeric-id":1827782,"id":"Q1827782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288180$74690150-C3F6-454E-BABE-9BDBD9764291","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b25571aad2a7c259fff8341c1d07d365b0e0e22","datavalue":{"value":{"entity-type":"item","numeric-id":5244876,"id":"Q5244876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288180$B135EC6E-8615-4903-9C31-64175B5652DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f3e2cdfb6fc77f978ebc89ff0887a2b1da2a777","datavalue":{"value":{"entity-type":"item","numeric-id":1109053,"id":"Q1109053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288180$4F2FFAA5-AFEE-4158-B487-7556C565D928","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"35f8e56f169bd883ed1d29513529ad2b6168f1da","datavalue":{"value":"bafkreidppygs4dgj3qcy4djvghg5mbjjrxp3waw6jorqp6xgr7upt6ka6a","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2288180$84FD19AC-418B-4401-A628-DB26EB87C8E4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3cf0a52f0067f16a7e477cfd08fb482648c50d4c","datavalue":{"value":{"entity-type":"item","numeric-id":5244876,"id":"Q5244876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e64897926990ca698c5e8e534be2eff1398ad13d","datavalue":{"value":{"amount":"+0.8832229971885681","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":"Q2288180$F04E2474-ADAF-4C1F-80C2-D8C354E48917","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5cb7def59f9890975c48e40555aeb19ec42a9d76","datavalue":{"value":{"entity-type":"item","numeric-id":4602858,"id":"Q4602858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"daa396140759daa9278138a916124905e83fb665","datavalue":{"value":{"amount":"+0.7860212326049805","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":"Q2288180$FE351A4A-D036-4039-A3FB-9F60769F08F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4859e35be1e9dbb77ef2f330912980a18b2ade21","datavalue":{"value":{"entity-type":"item","numeric-id":1773199,"id":"Q1773199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4b45961268865dc07e425f7b0e45fa347646f92","datavalue":{"value":{"amount":"+0.774753749370575","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":"Q2288180$980652FE-8D38-495E-8461-A2FAE99D9619","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ad908fa06e8518e2a443f5fce7cba6909fcd487","datavalue":{"value":{"entity-type":"item","numeric-id":1010633,"id":"Q1010633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5eb6214294c4ccd61c75f4254d5502ae47e2139","datavalue":{"value":{"amount":"+0.7585735321044922","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":"Q2288180$D654DC6D-0E02-4E7B-9166-8333937AAFFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c2c6594b4506847e1be2aa944629bb076f86a34","datavalue":{"value":{"entity-type":"item","numeric-id":3569807,"id":"Q3569807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be2fd36556007bc07e2fea70d8d436b094f9c65c","datavalue":{"value":{"amount":"+0.7544800043106079","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":"Q2288180$01F095D8-9FF7-4D0B-BB09-C288C43EC6B2","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2288180$F4E8A378-D9A9-4922-B7F5-A621A4EF3420","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2288180","badges":[]}}}}}