{"entities":{"Q1060018":{"pageid":1061866,"ns":120,"title":"Item:Q1060018","lastrevid":48821077,"modified":"2026-01-05T22:43:19Z","type":"item","id":"Q1060018","labels":{"en":{"language":"en","value":"An adaptive and cost-optimal parallel algorithm for minimum spanning trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3905860"}},"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":"Q1060018$0ED906C4-6FEE-4525-8DE1-98D34AD4D1AD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f9bd3f91bcc069ccb00a99ac07944f72ccbb1ae4","datavalue":{"value":{"text":"An adaptive and cost-optimal parallel algorithm for minimum spanning trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1060018$E8755FB6-1FBC-486E-8669-1D998649EC7A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4118c1dcc6f0d212833bf8f37298a65841ebcf11","datavalue":{"value":"0567.68041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060018$3741D230-3471-4D4E-97BB-9AF892B2A35D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1f1af06087ff3ceed50b0114cf15fcf91951f154","datavalue":{"value":"10.1007/BF02240073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060018$E88D8736-6182-49C0-B92D-B3380D80DF14","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b79ece58f33b59758a066cb6b9ee149bab3a2c9a","datavalue":{"value":{"entity-type":"item","numeric-id":167642,"id":"Q167642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060018$BCE4AF73-195F-407A-A3F5-8B8592F2B577","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1060018$750DFD63-B8D4-4649-B0E2-11B0CB5E22C5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7943953ac4b057fcee40558f77978f49f7941338","datavalue":{"value":"A parallel algorithm is described for computing the minimum spanning tree of an undirected, connected and weighted graph with n vertices. We assume a shared-memory single-instruction-stream, multiple-data-stream model of computation which does not allow read or write conflicts. The algorithm is adaptive in the sense that it uses \\(n^{1-e}\\) processors and runs in \\(O(n^{1+e})\\) time where e lies between 0 and 1 and depends on the number of available processors. In view of the obvious \\(\\Omega (n^ 2)\\) lower bound on the number of operations required to compute a minimum spanning tree, the algorithm is also cost-optimal.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060018$BE399C4C-9FB6-43D1-86B9-DBFCB5931092","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060018$D8CDD48D-CFDE-450E-B579-90AAE20FE8BF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"63a4e44a16ce0441de00adb14c7cbcbb4c66ceec","datavalue":{"value":"3905860","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060018$5CD805CA-500E-4F0F-AD00-1A90FE5901DE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e20622a5eb4a2db272edd9b9bde0632e18dee1f8","datavalue":{"value":"SIMD","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060018$B71024D1-38EC-42D6-A35E-B5D39D8CD94A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5074803ae9ac4260c9b030e2a7b9cab61eeebe46","datavalue":{"value":{"entity-type":"item","numeric-id":202146,"id":"Q202146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060018$7B5F6024-F78D-42D3-9794-26EBC065904A","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":"Q1060018$37E04EB2-3D36-450A-97A2-C9BCD240C7AB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c52b21e2b050930655d553363cf317d38372f3f","datavalue":{"value":{"entity-type":"item","numeric-id":3885184,"id":"Q3885184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060018$22D51A79-A19A-4715-8BBD-29F9DF466BEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ace200ebfc728bc45c1a6016dd155ed4bb7ff697","datavalue":{"value":{"entity-type":"item","numeric-id":5663902,"id":"Q5663902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060018$1A3B40E1-E5CC-446E-B2C4-B058F749EA47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a77240d8edc9497a339f96af8fb98d73487d2ddc","datavalue":{"value":{"entity-type":"item","numeric-id":3875355,"id":"Q3875355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060018$000495A1-E04C-48A3-8884-9F0A5A85EAD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b3dce3552dfbea64412441f1ced1f652d688fa0","datavalue":{"value":{"entity-type":"item","numeric-id":3932299,"id":"Q3932299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060018$CBCBED40-1312-4737-8741-AB617D402BBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd6ecca6b221a68c42607dd450ab7e9cb51b1138","datavalue":{"value":{"entity-type":"item","numeric-id":3945594,"id":"Q3945594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060018$5CB727AC-2CCA-4EBC-BD28-5C1E5B7790DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0e2b21447bd550a91f40b036c9a61259570513e","datavalue":{"value":{"entity-type":"item","numeric-id":3327727,"id":"Q3327727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060018$5DFD364A-48AC-4C62-9DAF-3787B23DE008","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"769cf6c7ee115ce4ebdbc44071512764e92350d4","datavalue":{"value":{"entity-type":"item","numeric-id":1171382,"id":"Q1171382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060018$F8BDB363-CA52-46CF-BCDE-CD0891F02051","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90822171efa1c7d26300416328cb969809d66a24","datavalue":{"value":{"entity-type":"item","numeric-id":1162158,"id":"Q1162158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060018$F83DEB24-8083-4259-9843-B3462839BAC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f365970946e86922b00e0810da7cd88c9269b10","datavalue":{"value":{"entity-type":"item","numeric-id":1186789,"id":"Q1186789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060018$D2A5DC70-6B37-4E8D-B34C-B2908F0AB31B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22cd4c0fc1f5a8f42092f317e184d08f13e82f9d","datavalue":{"value":{"entity-type":"item","numeric-id":3964023,"id":"Q3964023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060018$453775AE-2350-4BC8-B372-0CB0ABB98464","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e424f1c4ff7c6f161b20d25abc72aff42c0b5cc","datavalue":{"value":{"entity-type":"item","numeric-id":3763585,"id":"Q3763585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060018$6D4D1ECA-E9EC-42C5-9881-34CE8AB8CC18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a080daec45808badc5a3495fde9980f7d31c797b","datavalue":{"value":{"entity-type":"item","numeric-id":3660901,"id":"Q3660901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060018$1F848C8A-A9EF-4176-B866-0074F17111B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc6e2ab036340211124f0e0b42b404cab5811eb2","datavalue":{"value":{"entity-type":"item","numeric-id":3766876,"id":"Q3766876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060018$0E9D1C08-A4A6-4420-8B3A-3DB58D0185FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f51826f25d95525fd11a7363d44c95522afa1732","datavalue":{"value":{"entity-type":"item","numeric-id":3683547,"id":"Q3683547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060018$1C1FE6ED-FC0A-4426-96EA-D4D11F0CDA2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9790436eb027ae5afe13ffddcbbca35912442b7b","datavalue":{"value":{"entity-type":"item","numeric-id":4162670,"id":"Q4162670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060018$373B1814-D83D-4994-8468-8CF757BCA3C3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d6c448c13071d5347a74efdec5b9bd992e8859b","datavalue":{"value":{"entity-type":"item","numeric-id":4857538,"id":"Q4857538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12e59add4cf9fbdd9984b820bcce30d3e4676a48","datavalue":{"value":{"amount":"+0.9039731621742249","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":"Q1060018$220F0A15-60DA-4647-B099-F31FC3BE1675","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c7fb229c02dcac14e076189f91508730e92fdbc","datavalue":{"value":{"entity-type":"item","numeric-id":3725547,"id":"Q3725547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea0863f2ead75606914838e25a0b095d89e6fe63","datavalue":{"value":{"amount":"+0.902489960193634","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":"Q1060018$114A766B-2CAA-4725-83B0-67C4FFECA2DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45a69713a937baaa9aef496b0aa3b6c7d0f6cb11","datavalue":{"value":{"entity-type":"item","numeric-id":4531359,"id":"Q4531359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"814ebe457dd45275481a302e705c106876e1018e","datavalue":{"value":{"amount":"+0.8894029259681702","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":"Q1060018$3DA8C717-D2AE-4FA7-8455-5D43233B7AC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"509c5c38dcc81ce2b94edeb836a25043b4fa6c42","datavalue":{"value":{"entity-type":"item","numeric-id":1209346,"id":"Q1209346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81f8c582118279d47d444dd6a239959b048a8349","datavalue":{"value":{"amount":"+0.8851969838142395","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":"Q1060018$712FB97D-7605-47DB-9A0D-09A58918C36F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ff132711f5884fe1640f8d75fb9aa73fea77c20","datavalue":{"value":{"entity-type":"item","numeric-id":3688127,"id":"Q3688127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2568049ce05163d7a5ab666fd169af879e699a9","datavalue":{"value":{"amount":"+0.8844348788261414","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":"Q1060018$C502D5A9-6B46-419D-96CF-C072EEFAA14B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1060018","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1060018"}}}}}