{"entities":{"Q1090343":{"pageid":1101095,"ns":120,"title":"Item:Q1090343","lastrevid":66905703,"modified":"2026-04-12T13:38:35Z","type":"item","id":"Q1090343","labels":{"en":{"language":"en","value":"Algorithms for finding k-best perfect matchings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4006301"}},"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":"Q1090343$06952753-8D32-4D15-AD5A-782C463A9595","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b9e09c617946a4ea2bc6ae030d133ba541a4f463","datavalue":{"value":{"text":"Algorithms for finding k-best perfect matchings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1090343$AF2DC193-6820-4C67-A3CD-4366EB974885","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1c8f4930119fdd72a94aa6ab4b7658e32d050e43","datavalue":{"value":"0621.05026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090343$6B44E889-CA73-4498-A8ED-02B7C1A8FB21","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bdfd047265f10eb57aa0fd5ea2735d198da7aa8f","datavalue":{"value":"10.1016/0166-218X(87)90017-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090343$764F9683-D5DC-4BEE-B660-9901965D0328","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"509b181fc678252908bcdc15d2755e2ec42b7a21","datavalue":{"value":{"entity-type":"item","numeric-id":1090342,"id":"Q1090342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090343$20563E0D-C521-47B9-9606-8D4E15E5A28F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e50be6e020f540bbd257789357e2fcbd9ed3a74e","datavalue":{"value":{"entity-type":"item","numeric-id":166234,"id":"Q166234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090343$2872F9BF-F7F5-40BC-AAB5-5FB758C2A98B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090343$44C37D26-04E7-4789-BEF3-F70DBAE9847D","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":"Q1090343$6CB95CFE-F25F-4BF1-81B0-694CC7C0E7EB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"83b0bb34d854cee970399a565f0efbcb6bfde3e0","datavalue":{"value":"In the K-best perfect matching problem (KM) one wants to find K pairwise different, perfect matchings \\(M_ 1,...,M_ k\\) such that \\(w(M_ 1)\\geq w(M_ 2)\\geq...\\geq w(M_ k)\\geq w(M)\\), \\(\\forall M\\neq M_ 1,M_ 2,...,M_ k\\). The procedure discussed in this paper is based on a binary partitioning of the matching solution space. We survey different algorithms to perform this partitioning. The best complexity bound of the resulting algorithms discussed is \\(O(Kn^ 3)\\), where n is the number of nodes in the graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090343$56A70408-DA07-499F-919C-6D1E66CA40C0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090343$B035FA3C-1A9A-42CB-B5FC-06433BE9287B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090343$427CE533-ED22-44FD-80E5-F84CE4DD118F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090343$B21ED899-A139-440F-BE36-DB687C2D16D2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"921545afa15b3a586d549fb98a1f425a9513d114","datavalue":{"value":"4006301","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090343$D139F2B3-08AF-4F5E-B9A6-1D2D1F6AEDD7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"940136620aa9b2eaffae7f9eab959e6def48513a","datavalue":{"value":"K-best perfect matching problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090343$402072AA-8677-43AB-8709-68B6B70415D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27282df24ff0651e17e01cfcfe37c6d3ccb6c8da","datavalue":{"value":"binary partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090343$0F109F42-CE29-4075-84CF-4D674B42C062","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090343$D2F43CC4-702E-49E8-88E1-99DFC9382BCE","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"1412ceb6c71a23f10e8f7e008bf034264afa1496","datavalue":{"value":{"entity-type":"item","numeric-id":41444,"id":"Q41444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090343$02CAD40E-08DC-458D-AA6B-9E638ACB072F","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":"Q1090343$F065E5A6-6116-49F4-A269-39019B7FA615","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ce0644f85a3c178657cd85ded678599e811e90b","datavalue":{"value":{"entity-type":"item","numeric-id":5665033,"id":"Q5665033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090343$DB21AD28-B3CC-40FA-A38A-28AFD9072269","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d51cc64185b2e669f7f17dc476c769ec0ad4ed5","datavalue":{"value":{"entity-type":"item","numeric-id":4197644,"id":"Q4197644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090343$AF01E07E-B1EC-41CD-97BD-4C5077123D70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64e625f863ff680eb54510148883629ce9f49256","datavalue":{"value":{"entity-type":"item","numeric-id":4079339,"id":"Q4079339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090343$189E3A42-DE88-4BFC-A968-88B1087EA3A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e927c80db8e8c562bb886a822cc6867b7d56d1f","datavalue":{"value":{"entity-type":"item","numeric-id":3931440,"id":"Q3931440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090343$0D261932-393B-4CC1-99DA-B55F5307BA5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b989f45b85fa44137ad22092706b6102fd241bf","datavalue":{"value":{"entity-type":"item","numeric-id":78129,"id":"Q78129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090343$998EC06B-4F70-4192-B138-E7167E3FADF5","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":"Q1090343$FBDBA465-D0A4-44B9-ABDC-B8E8A4642BC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da5b18e5a44e3c67c75b0887be40e31fe6fc87d6","datavalue":{"value":{"entity-type":"item","numeric-id":4080986,"id":"Q4080986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090343$62ED5774-46B8-4D07-B805-3575B9939D53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d4fbbdb525d53e912d0fd9fc57d70ac9cc61edd","datavalue":{"value":{"entity-type":"item","numeric-id":5643805,"id":"Q5643805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090343$CBCDADE4-03A5-43E1-BE93-01DE4C9F7C24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090343$3F589AD4-E6C4-4974-B969-218CC1935998","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e3acfeb6500969d2e934fb86ceff54824a082fa","datavalue":{"value":{"entity-type":"item","numeric-id":5616598,"id":"Q5616598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090343$34C36659-88E2-4BB9-8D43-42157B0FC994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d09c5e4ecd6a0ffbde3dc9394bc1ce65e0d5e140","datavalue":{"value":{"entity-type":"item","numeric-id":3885210,"id":"Q3885210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090343$31DF0481-E00C-4747-9FDD-F2F40C9305EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7c600d09f1ac45352d94a36d4791fa6d9e8c99b","datavalue":{"value":{"entity-type":"item","numeric-id":3922722,"id":"Q3922722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090343$ADD8E9FF-2790-4375-90C4-4258160FA042","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b07691f927af5c6b022bdb0fa09e72e8343db251","datavalue":{"value":{"entity-type":"item","numeric-id":1327213,"id":"Q1327213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d142984b10b24ae704757d9c0b6d972c28a7ca2","datavalue":{"value":{"amount":"+0.8830973505973816","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":"Q1090343$BCE76493-7010-49E5-BBF4-32093F400E44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2bbdf455a3ba3126ade6b38a0a3c1bf419e67319","datavalue":{"value":{"entity-type":"item","numeric-id":3824125,"id":"Q3824125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"835e14903f3b1fcdd4af28a74f60fe0375c41475","datavalue":{"value":{"amount":"+0.8764033913612366","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":"Q1090343$16D3BF93-AA81-425E-BCCA-200828245975","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48c27afcc97ac3c559637ffc59d5984dd7593c70","datavalue":{"value":{"entity-type":"item","numeric-id":4035639,"id":"Q4035639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63b88db6147d43a2308fea815de265eea9cfc106","datavalue":{"value":{"amount":"+0.8530018329620361","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":"Q1090343$DF5E8B38-6BBA-4509-B153-6C2C817F5A18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc013dc307ccd118403eb9ffeb7dd9c3d9326043","datavalue":{"value":{"entity-type":"item","numeric-id":4845365,"id":"Q4845365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63b88db6147d43a2308fea815de265eea9cfc106","datavalue":{"value":{"amount":"+0.8530018329620361","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":"Q1090343$A73696DC-590D-44DA-BDBB-E27B792A04E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dfda8dc8782d363b74f688b83e1544d96813833a","datavalue":{"value":{"entity-type":"item","numeric-id":4967175,"id":"Q4967175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1dbec7abd80ea7d079f8591f1f858d5708a15a38","datavalue":{"value":{"amount":"+0.7959240674972534","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":"Q1090343$5BCC281E-044A-4336-9C9D-245021EC00E0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Algorithms for finding k-best perfect matchings","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Algorithms_for_finding_k-best_perfect_matchings"}}}}}