{"entities":{"Q848958":{"pageid":850806,"ns":120,"title":"Item:Q848958","lastrevid":64830564,"modified":"2026-04-11T22:30:59Z","type":"item","id":"Q848958","labels":{"en":{"language":"en","value":"Note on the structure of Kruskal's algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5674331"}},"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":"Q848958$86DBE1C5-64A3-454B-9D4D-A8D57F21472B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"148503111d33e2fc34c3d62f7767c477b5622568","datavalue":{"value":{"text":"Note on the structure of Kruskal's algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q848958$73DDCEEB-90A3-4112-B1EE-DEE98F42DBF6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1d16877837446d8d19d0fc0300f0d9258a99df63","datavalue":{"value":"1219.05181","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q848958$C980A5F8-E5B2-43D4-94C2-CA2747E28912","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c807ea8af6bb5b3fc8576321f950dea52050949b","datavalue":{"value":{"entity-type":"item","numeric-id":328789,"id":"Q328789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$4EFD37FA-4FF3-494F-96C7-B7BE01B0EEB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"129feab0782d02d4045d61153253160d85a71ae3","datavalue":{"value":{"entity-type":"item","numeric-id":848957,"id":"Q848957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$327D0B81-46B3-42EA-A35C-B4214B46D01C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"68ee3d60719c97b3f7244d7f2c477985e89e7464","datavalue":{"value":{"entity-type":"item","numeric-id":1242411,"id":"Q1242411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$32D815FC-583C-4F3D-B275-7E22087A8A29","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$18BF375B-8D1F-45A0-9FD2-CF4E8611ECB6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"24e3170ae1d6bebbc96609d601d5472b321e57f1","datavalue":{"value":{"time":"+2010-02-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":"Q848958$A6F16980-1D8A-4247-80DE-AEDD423C5738","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"825223d5404278e2a7af9e8cbc7377b537f2797c","datavalue":{"value":"Let \\(G=(V,E)\\) be a connected edge-weighted graph and let \\((V,F)\\) be its minimal spanning tree constructed by Kruskal's algorithm [\\textit{J.B. Kruskal jun.}, ``On the shortest spanning subtree of a graph and the traveling salesman problem,'' Proc.\\ Am.\\ Math.\\ Soc.\\ 7, 48--50 (1956; Zbl 0070.18404)]. We capture the evolution of the spanning forest from \\((V,\\emptyset)\\) to \\((V,F)\\) by a rooted binary tree \\(R\\) with leaves in \\(V\\) and internal nodes in \\(F\\). Let \\(h(G)\\) denote the height of \\(R\\). In case of Prim's algorithm we would have \\(h(G_n) = n-1\\) for every connected graph \\(G_n\\) on \\(n\\) vertices. In case of Kruskal's algorithm there is a constant \\(c>0\\) such that the probability of \\(h(G_n) \\geq cn\\) tends to \\(1\\) for \\(n\\to\\infty\\), and therefore the expected value of \\(h(G_n)\\) is in \\(\\Theta(n)\\), for three choices of random edge-weights: {\\parindent=6mm \\begin{itemize}\\item[(1)]\\(G_n\\) is a complete graph on \\(n\\) independently uniformly distributed random points in \\([0,1]^d\\) and the edges are weighted by the Euclidean distance,  \\item[(2)]\\(G_n\\) is a complete graph on \\(n\\) vertices and the edge-weights are independently uniformly distributed in \\([0,1]\\),  \\item[(3)]\\(G_n\\) is the Cartesian product of \\(d\\) paths \\(P_k\\), \\(n=k^d\\), and the edge-weights are independently uniformly distributed in \\([0,1]\\).  \\end{itemize}}","type":"string"},"datatype":"string"},"type":"statement","id":"Q848958$7DE57EAD-C7C2-486C-89D1-7FB7509744DE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q848958$71A77DB0-4D63-4901-BA9F-B61B4D7C4806","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q848958$8E9ADDAD-AB8F-45D9-873C-E7C813E362BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q848958$E6BC3E08-1E44-455E-BE47-85EFE0D1C43C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3e5eb4a2746bab0cd450d3f0948c30cdb1e4a9e7","datavalue":{"value":"5674331","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q848958$19E834B9-BB9D-45CC-86E7-5E51E17DB67C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4049b50d1353950567a6666af88ef63b00a1649","datavalue":{"value":"random tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q848958$6EB2532F-BECE-4A62-84BB-5A34BB8FDD0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6078fceba255c2f14830c9cbf81b3ab69e83b898","datavalue":{"value":"minimal spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q848958$73730846-23A2-4E89-B0FE-6DF045D5769A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"392b0efe79e3c2958911c2dc25cf51490681e557","datavalue":{"value":"Kruskal","type":"string"},"datatype":"string"},"type":"statement","id":"Q848958$05008729-B38C-48BB-B1EC-98CE3FD737D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c0378c51c2c332d2e3dbcf4869c0305deb0fb14c","datavalue":{"value":"height","type":"string"},"datatype":"string"},"type":"statement","id":"Q848958$20298F25-2B3C-481C-852E-8126B8D43BE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0446baf9c31d45b16691b35420e6e46c50f286","datavalue":{"value":"random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q848958$EFB7E0D1-312E-4318-892A-BE7BAB979BEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"539be726cb8dfa54cd0c12914c99488c7ea42ea5","datavalue":{"value":"percolation","type":"string"},"datatype":"string"},"type":"statement","id":"Q848958$23AEC9F2-82BA-42D9-A76B-4F338F56F329","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":"Q848958$EAEB85C4-5582-4048-9EB5-697BEE67749B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8f4fcf8faa3f8bd25ae865cd0f634dfa2fd237ff","datavalue":{"value":"https://doi.org/10.1007/s00453-008-9164-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q848958$D7DA0559-5AEF-4A78-87E7-075830B37D05","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2471052cf7f23c1f50d94368218eda7b1abc6633","datavalue":{"value":"W2151957880","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q848958$75F59EAE-AEE2-48BB-9376-8A2DEE443251","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$2157435B-AFFE-45D3-8AA3-2BCE8F9E68CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5547cb4ae04bd688fba38f328a9b9f3b4f398235","datavalue":{"value":{"entity-type":"item","numeric-id":3970906,"id":"Q3970906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$A71873D1-3625-4F41-B15B-B59BCB207FC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dac94b70b5cdd8742244872a0d79b97ee96e0787","datavalue":{"value":{"entity-type":"item","numeric-id":1203349,"id":"Q1203349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$543A4436-1FD7-4B9F-A0E8-AAF7CCA41B8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cdfdff61711f6dd0ddfe48f1c731b0144aaf9fc1","datavalue":{"value":{"entity-type":"item","numeric-id":3142595,"id":"Q3142595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$C848BA95-6955-421E-BC16-C2C2D2D3C3D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54bd5d9916d1a79ebf4c7690c185803351f746e3","datavalue":{"value":{"entity-type":"item","numeric-id":5956069,"id":"Q5956069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$F7F9A158-CE9A-4022-ADDF-3A421F470B39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77d6452e54e5e6983bfa6dba10e55824db2fd929","datavalue":{"value":{"entity-type":"item","numeric-id":5814290,"id":"Q5814290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$C56B1036-0D77-42BA-A652-1643953F911F","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":"Q848958$CBCCF5BB-EFB3-4C0B-908A-A2B61E4F3D1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"edd227013a96dd65d0289b90d93ff4bba0dd80ab","datavalue":{"value":{"entity-type":"item","numeric-id":3286850,"id":"Q3286850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$9E7B991D-C687-4FAE-BDE4-5564B87B6F25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a270b91c4299553b6f90d4713b498e1c7fd02458","datavalue":{"value":{"entity-type":"item","numeric-id":1066149,"id":"Q1066149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$F3D7286A-394E-40C9-8E0D-C5E3F91561BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c3e6f89a822ac7ef2f224844b68898dc79b3963","datavalue":{"value":{"entity-type":"item","numeric-id":3672870,"id":"Q3672870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$365AAECC-3605-4886-8287-8BA2C504156F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e56efe468c570f890c7ff18a704aa4f6ee3b3d94","datavalue":{"value":{"entity-type":"item","numeric-id":1246269,"id":"Q1246269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$E1AF3067-8551-47A1-9C7D-F79ADD12018D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84c35c3c18100f10a76a9ef0d730325b542a65e7","datavalue":{"value":{"entity-type":"item","numeric-id":115238,"id":"Q115238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$506E9AFA-2D96-4B0E-9254-7B7F9A13476A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ba5c8a6e55ce3491766d12750053e07f46bc105","datavalue":{"value":{"entity-type":"item","numeric-id":3122913,"id":"Q3122913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$06301CF8-1C83-493A-979F-B1D86F7BDC8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55c1f63a952be670d503a888c44b3f50105c1ab6","datavalue":{"value":{"entity-type":"item","numeric-id":4895792,"id":"Q4895792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$47071DE8-4198-4037-89E8-7C38CE03E032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92dd142fe4623a410d1c1bfe8e4299ec86df7306","datavalue":{"value":{"entity-type":"item","numeric-id":1364391,"id":"Q1364391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$F89CEC23-A829-43C2-9E2F-7FC0058238A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d44bcd5de31111912cd006a39a7f2e781ecb1a3","datavalue":{"value":{"entity-type":"item","numeric-id":4379729,"id":"Q4379729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$6BEDFC57-6367-4C6A-975E-79417F08E7A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3ec95b26afd4a57756011bc7bf991d5c9b3162f","datavalue":{"value":{"entity-type":"item","numeric-id":1807193,"id":"Q1807193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$94E71086-C54A-4C8D-BD98-A2C6AAA6B91D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df6dbf7db482a7d71e087b003bf63f9628afc6e3","datavalue":{"value":{"entity-type":"item","numeric-id":4427412,"id":"Q4427412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$084BE5C1-E33D-4AA1-83CF-919656EEBED4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42e2e19442f704d99dbc2813172a04f9c9d276d0","datavalue":{"value":{"entity-type":"item","numeric-id":5691080,"id":"Q5691080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$1F588D0A-E225-4D9E-B4F3-B7D3F6AF1F02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bc71322c3f7bb02445408c958a64e30b2729230","datavalue":{"value":{"entity-type":"item","numeric-id":4140369,"id":"Q4140369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$ECB20971-5D83-4F6E-8D2F-EA5DED56C91E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"013b8ebb1a4f40553a486ac958cce7783ccdb831","datavalue":{"value":{"entity-type":"item","numeric-id":1385435,"id":"Q1385435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q848958$7FCAFE11-757D-40B3-93B6-1D0E5C5B5D0F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"28c40bd429f344a88971b9e3e02d48cfd153e576","datavalue":{"value":"10.1007/S00453-008-9164-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q848958$D57593E9-386B-45BE-B428-748130750666","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34c02fff2f8af268274fc950309be7c1195ac1a7","datavalue":{"value":{"entity-type":"item","numeric-id":3122913,"id":"Q3122913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06654268672b9ddae43d002210ac48b55551def9","datavalue":{"value":{"amount":"+0.8979915","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q848958$BDF51A88-351C-420B-93C6-3C6DAAD6E137","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3e19a5f537c307f4608c79d9b496983657caeea","datavalue":{"value":{"entity-type":"item","numeric-id":6074707,"id":"Q6074707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"149a2e9e7414ee00b2f017ca7d003f320b771e96","datavalue":{"value":{"amount":"+0.8830567","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q848958$46A85AD5-1352-4F68-B317-B5E587861F0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e264978fd81eab814e3fbf8857bed1aa2f2bff28","datavalue":{"value":{"entity-type":"item","numeric-id":923108,"id":"Q923108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9682442d7d2da129cde73bed5b3a15dd3e9f3319","datavalue":{"value":{"amount":"+0.87527055","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q848958$0C26B454-BEDF-49AB-A582-B035E5220C8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b68d1edce19e188a9ed0fe829dd48771249dea01","datavalue":{"value":{"entity-type":"item","numeric-id":4858241,"id":"Q4858241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"207cbf7fbf1919f9a762f8a23f082bfb0c88aa2d","datavalue":{"value":{"amount":"+0.8704513","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q848958$01270606-FB24-47DD-B6D9-858E2A57FA7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f1eaf4ac2ae9fed399d762977e7a0745c786d5f","datavalue":{"value":{"entity-type":"item","numeric-id":1066149,"id":"Q1066149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d32c03b353e184c238db9d94d5ef2268a07cb3c","datavalue":{"value":{"amount":"+0.8698079","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q848958$41AC270D-CE30-43F4-B1F4-231970A3E568","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09e536b4c8a51dc023ace9cac7fc7a7b0d0c077d","datavalue":{"value":{"entity-type":"item","numeric-id":5875520,"id":"Q5875520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5388bd5c7a9664bcac8c518d4a466790c158c087","datavalue":{"value":{"amount":"+0.8689387","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q848958$697A93AE-69FA-4E6B-8EB6-177AB80C3F28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64c3f1fc486e01e6ac1ed1371269bfcd5f740129","datavalue":{"value":{"entity-type":"item","numeric-id":1288911,"id":"Q1288911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f92c39016a74dfc76dc68dfc2f5476802fd02d5","datavalue":{"value":{"amount":"+0.86601806","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q848958$A02B1EB8-08B4-4801-AABF-809DAABB3AD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"880ec3065978597c51993e16849b1063e8173bdb","datavalue":{"value":{"entity-type":"item","numeric-id":1578476,"id":"Q1578476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31ae115833402b4452407e3d39cc537a640c94ad","datavalue":{"value":{"amount":"+0.8646958","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q848958$763B5355-0620-4C0B-B505-78910BFC3DD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17d63b8604266d44b53a42deabfdb819c962038c","datavalue":{"value":{"entity-type":"item","numeric-id":3574996,"id":"Q3574996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ccd92928c8b54e73949e9855e199fdb8c6e7f820","datavalue":{"value":{"amount":"+0.8567555","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q848958$C4669FA9-BA16-4AE3-A716-52FAB9513E4E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Note on the structure of Kruskal's algorithm","badges":[]}}}}}