{"entities":{"Q1109690":{"pageid":1120439,"ns":120,"title":"Item:Q1109690","lastrevid":66451125,"modified":"2026-04-12T10:09:56Z","type":"item","id":"Q1109690","labels":{"en":{"language":"en","value":"A polynomial algorithm for b-matchings: An alternative approach"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4070668"}},"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":"Q1109690$92C6CCC9-6DCF-4137-AE98-970E0D739AFF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1370814c10e7fac79338ecf474281f414e6dffaa","datavalue":{"value":{"text":"A polynomial algorithm for b-matchings: An alternative approach","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1109690$900A3D38-3E8C-43E1-92D9-51CB019BFAFC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6679df3faa423c4bb9bc8f5b54e2bab64811282d","datavalue":{"value":"0655.90090","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109690$898F2F93-47FC-48DD-9DC1-B9E5F9A68085","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dff186c505f798f887f7d4efc19e154987532e02","datavalue":{"value":"10.1016/0020-0190(87)90178-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109690$CD1E2FC8-72EF-4D9F-9C1E-A24187EBD41E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109690$B9B21ED9-FF7C-4519-A063-47139704629E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1109690$537E828D-6D00-4F66-AAA6-D06209242F25","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9c3975e7393ee5afda96dd3ff4739abb8130dc85","datavalue":{"value":"A b-matching of a given graph G is an assignment of integer weights to the edges of G so that the sum of the weights on the edges incident with a vertex v is at most \\(b_ v\\) (b denotes the vectors of \\(b_ v's)\\). When \\(b_ v=1\\) for all vertices v in G, then b-matchings are the usual matchings. The b-matching problem asks for a b-matching of maximum cost where the edges of G have been assigned costs and the cost of a b- matching is the sum of the weights times the costs. We do not assume G to be bipartite. We present a polynomial algorithm for the b-matching problem differing from the algorithm of \\textit{W. H. Cunningham} and \\textit{A. B. Marsh} [Math. Program. Study 8, 50-72 (1978; Zbl 0409.90081)]. In fact, the new algorithm is strongly polynomial using the new strongly polynomial minimum cost flow algorithm of \\textit{E. Tardos} [Combinatorica 5, 247-255 (1985; Zbl 0596.90030)] (we actually use the algorithm of \\textit{J. B. Orlin} [``Genuinely polynomial simplex and nonsimplex algorithms for the minimum cost flow problem'', Centrum for Wiskunde en Informatica, Stichting Mathematisch Centrum OS, No.8504 (1985)]) to obtain a half- integral optimal solution. An integral solution (close to being optimal) is obtained from it which is used as input to the b-matching algorithm of \\textit{W. R. Pulleyblank} [``Faces of matching polyhedra'', Ph. D. Thesis, Dept. of Combinatorics and Optimization, Univ. of Waterloo (1973)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109690$39A05356-B318-422C-BC99-61DC204115C4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109690$9C556F8D-7661-4DDA-8582-1E9867FE6A1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109690$2C06A4CE-B180-4671-A414-52510FFD2C57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109690$41392022-FCC2-419A-93E0-310804DE6E12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109690$5C7908EB-5211-47F1-AB2B-9562E479E09D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d1e42369a7913268fae18554d53184f317cb3607","datavalue":{"value":"4070668","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109690$38401524-5EAE-4097-9E51-0C232337FDCD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c6fa1a8e62615a50dd3663d5ae288cec113ac18","datavalue":{"value":"half-integer solution","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109690$E658C509-3330-4F44-96EE-A8CF37C12234","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4508b53fccaaec9fabfeed179363e10e71a80d5d","datavalue":{"value":"b-matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109690$E18D5F99-C846-4A9A-AE12-FEA1C72C33E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc8f077dbbd86a7acf5455280222131d9e1bc1cc","datavalue":{"value":"assignment of integer weights to the edges","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109690$46266D40-6EDF-46CB-8FAA-637B8E559537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109690$CE5C6713-B195-4931-83BE-CA4ADE983307","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9280777d7c4ecc56732124c9c0983aed9722f1b7","datavalue":{"value":"half-integral optimal solution","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109690$33F38C9D-6171-4391-ACE4-DBD956BFEF83","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3c7a09266880b9246b87f74318f3fac418e3fcad","datavalue":{"value":{"entity-type":"item","numeric-id":489296,"id":"Q489296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109690$10E8D337-1225-4E8F-B0CA-2F656518DECB","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":"Q1109690$B2FA899B-184F-44E1-B7DB-9B9C7040EE6D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"02fca5a4dcef1113a1e9d2bdfd08a6e8a1211369","datavalue":{"value":"https://doi.org/10.1016/0020-0190(87)90178-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1109690$E6908EB3-0619-442B-842C-6A48AC3E0619","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2572df8206a722c2bf73681748b540448ab7d56a","datavalue":{"value":"W2005633226","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109690$66DB7717-4AB2-41B8-96F9-D6F1590B1D24","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"158074026b12bcc0c8d303c2782c8ab65c0b799b","datavalue":{"value":{"entity-type":"item","numeric-id":5187322,"id":"Q5187322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109690$3D560C77-0997-42DA-958C-A984CFF93111","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb3f0318f4c2281498883fe698492a41d5ac577d","datavalue":{"value":{"entity-type":"item","numeric-id":4152359,"id":"Q4152359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109690$BF2592EF-E054-404E-86FA-1317F7CA1A72","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":"Q1109690$E1D7BF90-BE62-400A-8C0B-33EA89C32514","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":"Q1109690$1FF36E70-087A-45BD-8594-D4DFE74C3AAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"271059027ec9c0e0491187496cb25dd92d2df81b","datavalue":{"value":{"entity-type":"item","numeric-id":5675543,"id":"Q5675543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109690$60590D5C-0EBA-4498-8D9E-858E0663140A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcd47930f1b3201b92c88c8d229fd91955ad4b55","datavalue":{"value":{"entity-type":"item","numeric-id":5341587,"id":"Q5341587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109690$A07DEBCB-EBFB-4107-9855-349D8AD96F4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c45c86c7f172e023843236094a98399ae49d365","datavalue":{"value":{"entity-type":"item","numeric-id":4165177,"id":"Q4165177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109690$CCDDF56D-C25D-4DA7-AA7B-DF3D274F79D6","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":"Q1109690$BBD29BA1-10FD-4CE6-BDB1-5804E68BCFF1","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":"Q1109690$D9E3323E-A647-48A4-BD5D-D120A6801DC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18896b12fcfc75b1384ddbb4d217a7db3a02e745","datavalue":{"value":{"entity-type":"item","numeric-id":1079110,"id":"Q1079110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109690$AAB08BB9-885F-45F9-81D2-C687D267236F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e20111791a3f2806dd0d430f07d93cfb68029942","datavalue":{"value":{"entity-type":"item","numeric-id":3646847,"id":"Q3646847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e68923ae22cdff5fb41f7ed536ea78db753fcf81","datavalue":{"value":{"amount":"+0.9054787","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1109690$ED38C042-AD61-45A6-948B-C3633E878E37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68c77d86ee099632ca80763a63236328b4da177f","datavalue":{"value":{"entity-type":"item","numeric-id":1069866,"id":"Q1069866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51b1de02a081f4019f28d9bfd69227bd80a1c0b8","datavalue":{"value":{"amount":"+0.8766721","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1109690$A4CC9F79-A6AC-4B51-8E2F-E753412931C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83f30abb21892836fc1f530af91487246a98daab","datavalue":{"value":{"entity-type":"item","numeric-id":4871086,"id":"Q4871086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9c4c5c562cdf6eab019c012a8b5f9bd524ae17d","datavalue":{"value":{"amount":"+0.8747537","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1109690$DF6177F1-35A2-42A0-8FEE-31D106EA6B85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fc8ba180919a8d87e4443c2a90cf6568c6c311a","datavalue":{"value":{"entity-type":"item","numeric-id":4264549,"id":"Q4264549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de2cb78f2df436e107eb6f528531a9f942138cd5","datavalue":{"value":{"amount":"+0.8706839","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1109690$02D480AF-A884-43BB-8328-1176D349444D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d636f286311ff9837de53048f423152ea02b853","datavalue":{"value":{"entity-type":"item","numeric-id":293170,"id":"Q293170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16210836f7526e608883b4bc6c31cbf867b7f0b2","datavalue":{"value":{"amount":"+0.8701199","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1109690$E74A9014-7957-4747-8E1A-51608FAE6E25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"302ed5946d6e0b2655e64b420fc95c2625f69343","datavalue":{"value":{"entity-type":"item","numeric-id":1801015,"id":"Q1801015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7638a0d5dc763a8c1ddae3cea9e53985b387ac81","datavalue":{"value":{"amount":"+0.8677227","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1109690$250122DB-B376-40D2-958D-2097CFCCC654","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"468fa115a523f4e09aa5e797cd443ac5326aa60a","datavalue":{"value":{"entity-type":"item","numeric-id":3186510,"id":"Q3186510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7638a0d5dc763a8c1ddae3cea9e53985b387ac81","datavalue":{"value":{"amount":"+0.8677227","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1109690$5C43CBFA-1CCA-4C94-ADEB-9F2E66EFE80F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3cb36786b4ef330754bdfadf5d2f63ddc7dc347","datavalue":{"value":{"entity-type":"item","numeric-id":4474103,"id":"Q4474103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1999a83f786361052656f397835d28f1b8f31b6e","datavalue":{"value":{"amount":"+0.8658384","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1109690$5F317619-BBE1-4BDC-8B01-8CD6B0CF018F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A polynomial algorithm for b-matchings: An alternative approach","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_polynomial_algorithm_for_b-matchings:_An_alternative_approach"}}}}}