{"entities":{"Q1063004":{"pageid":1073756,"ns":120,"title":"Item:Q1063004","lastrevid":66063465,"modified":"2026-04-12T07:17:24Z","type":"item","id":"Q1063004","labels":{"en":{"language":"en","value":"Worst-case choice for the stable marriage problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3916316"}},"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":"Q1063004$263249E8-D983-4021-A03D-51148C745CA3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"66c26c4bc0060883b68076111e9eb4b3f826ea22","datavalue":{"value":{"text":"Worst-case choice for the stable marriage problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1063004$4AECC1EB-D809-4F3D-9E86-A52B8F27D775","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"47d57d291e8f317039b89417aa34660f8a83245d","datavalue":{"value":"0574.05039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063004$BEF26FB9-0BC6-456E-B545-40A0A08928F5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2e180ac22d1655718dc38df88d7e41e2bbc36061","datavalue":{"value":"10.1016/0020-0190(85)90104-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063004$D375816D-2BAD-47F7-81D8-CC2178FF7B5B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7a60a38320311da18eda10821922742954865726","datavalue":{"value":{"entity-type":"item","numeric-id":394492,"id":"Q394492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063004$C88E2BD6-9F12-4EAF-A8B8-69B157C2B14C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9c6edca5bf1daef00082b7b01041eecf3822e0fa","datavalue":{"value":{"entity-type":"item","numeric-id":1063003,"id":"Q1063003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063004$82839405-16B4-444D-BC21-328BAB5D8E4A","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":"Q1063004$8A372619-AD48-47D0-AB67-F235617F9535","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1063004$575AC9EE-5C31-4A58-97CD-648BB229CC83","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f5131c2714959df41d347013611092ba4a71bf53","datavalue":{"value":"We present a worst-case choice for the stable marriage problem which takes the maximum number of stages for \\textit{D. Gale} and \\textit{L. S. Shapely}'s algorithm [Amer. Math. Monthly 69, 9-15 (1962; Zbl 0109.244)]. We also analyze a coroutine solution recently suggested by \\textit{L. Allison} [Inf. Process. Lett. 16, 61-65 (1983; Zbl 0513.68064)] as well as a parallel algorithm for this problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063004$4D78C770-8537-4D66-993E-50836985D5D6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063004$73778FB1-435C-4024-8D95-5C5F1B80BFC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063004$F6613903-B200-4B6C-B2A3-6CAD74542330","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063004$161CA2A5-571A-4EC9-B1AD-5FD29FA39835","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"785d600ca0599a596f86d53bb2316fbfa8f139dc","datavalue":{"value":"3916316","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063004$39503C61-3AF9-4791-BFB3-8828F3F14A21","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c24164d5a5de4abe12ee02a8db396f78b7899ad","datavalue":{"value":"worst-case choice","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063004$6ADC6360-F28D-4C57-9D2D-4255ABA25F82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"83a57ecf4aa27cc4dcc5c4ab35386a309ef35a50","datavalue":{"value":"stable marriage problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063004$0C2A3CAD-E0FE-4505-9822-2D0824B06876","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0967c5f93d36d6aa18ee008d77ee288965d952b9","datavalue":{"value":"parallel algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063004$FAC5BF3A-29DD-4D30-A115-533187906790","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":"Q1063004$4F5A9044-2FBA-4FB9-881A-57743EDD767D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"924b15835c7761d2a54589bbbe1ff410460aff9f","datavalue":{"value":"https://doi.org/10.1016/0020-0190(85)90104-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1063004$A1326BF4-AAD3-4773-ACAF-07538395D068","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8bddb11c62b12b30693bff0f53f771195e12295b","datavalue":{"value":"W2076296171","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063004$0DD19B52-1F77-4561-BB05-BAA2186A8F58","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e425b82fcff5dfff43d559bfed61952675696682","datavalue":{"value":{"entity-type":"item","numeric-id":1050775,"id":"Q1050775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063004$F872C9E7-6B9E-4F87-B77F-E15CBA9D4A7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd41a3d3ffce78a856861213ff6553c14d782cc0","datavalue":{"value":{"entity-type":"item","numeric-id":5904119,"id":"Q5904119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063004$3BB62FAB-3D88-46DF-83BE-E0A3BAD086EF","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":"Q1063004$08C825D2-0D91-45CD-BBF9-760D650F23C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6996fd58e10b601426f1eacabf524405918a4c5f","datavalue":{"value":{"entity-type":"item","numeric-id":5631116,"id":"Q5631116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063004$54E64EB7-0639-4F01-B3C9-9B1B2E03430F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5827b33f6040e2365ba104b2c460c40532349bb","datavalue":{"value":{"entity-type":"item","numeric-id":3311639,"id":"Q3311639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063004$A4DEBCE6-10CD-41B4-BE47-2CE52BB4AAC4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f08b5ca62e90bbedd17daddce48beea61f548fc","datavalue":{"value":{"entity-type":"item","numeric-id":798000,"id":"Q798000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51e8ffcbe76b652df4e5777e0d29af838cce83c4","datavalue":{"value":{"amount":"+0.8796975016593933","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":"Q1063004$64AD69CD-CDB8-408A-AC3C-433D589B61C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ceeb499eccaa356a1407fe5104c00191187d02dd","datavalue":{"value":{"entity-type":"item","numeric-id":3474282,"id":"Q3474282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56246e14bccae8f3eb0a591e6abe27c8267d19da","datavalue":{"value":{"amount":"+0.8417736291885376","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":"Q1063004$7BC4741B-FC0E-4620-B5B2-16824C761046","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d42889383e4b2338a62a58505a0fa868a2cdc879","datavalue":{"value":{"entity-type":"item","numeric-id":3703906,"id":"Q3703906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb9f7b2bb1daeeae083ddcbb9d754a2fc5550af8","datavalue":{"value":{"amount":"+0.8308749198913574","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":"Q1063004$CBC2C71E-EA09-4E6E-ABC1-CA474642EFE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e28ff97d01dccca1b5ea5955e705ce36ad151552","datavalue":{"value":{"entity-type":"item","numeric-id":1086592,"id":"Q1086592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0be7bc282d58d3580901a2705dabceb46d24a56a","datavalue":{"value":{"amount":"+0.8307075500488281","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":"Q1063004$9387A912-3C4B-40BB-9F85-65592091F799","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51caa4e263fb1be5a80f3ad337f2a678e76922ba","datavalue":{"value":{"entity-type":"item","numeric-id":2278950,"id":"Q2278950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f6fdb57c524c3195c252d07bbc3dbde50947943","datavalue":{"value":{"amount":"+0.8276357054710388","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":"Q1063004$EF3DA87F-FE25-4E87-8788-FD5C6BC4B165","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Worst-case choice for the stable marriage problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Worst-case_choice_for_the_stable_marriage_problem"}}}}}