{"entities":{"Q1186789":{"pageid":1197538,"ns":120,"title":"Item:Q1186789","lastrevid":69848145,"modified":"2026-04-13T10:45:00Z","type":"item","id":"Q1186789","labels":{"en":{"language":"en","value":"Expected parallel time and sequential space complexity of graph and digraph problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 37164"}},"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":"Q1186789$B1C4DEEA-4899-4947-9A76-66F679672DEC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a6af2abd3e6727a7434b523548e17af25f4c2425","datavalue":{"value":{"text":"Expected parallel time and sequential space complexity of graph and digraph problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1186789$89D60394-D6D7-49AB-9143-D7872E919F25","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cde3f559ed38f290ca79c02e8e3470fcd533ccff","datavalue":{"value":"0749.68059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186789$B2C419CF-7583-45F2-B247-E6E3249D5723","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2badaf3b583553929cfa0cd2f965cbdf4c0fcc66","datavalue":{"value":"10.1007/BF01758779","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186789$9A99B96F-1825-4FAF-B573-771087B72B52","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":"Q1186789$9ECD715B-01ED-412C-838C-BBE591EEB82D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1186789$68019DF9-E7B8-457D-9843-91C99D2C9563","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2dbf3e74cb69af71274d68d0053cdc7279601bc9","datavalue":{"value":"This paper determines upper bounds on the expected time complexity for a variety of parallel algorithms for undirected and directed random graph problems. For connectivity, biconnectivity, transitive closure, minimum spanning trees, and all pairs minimum cost paths, we prove the expected time to be \\(O(\\log\\log n)\\) for the CRCW PRAM (this parallel RAM machine allows resolution of write conflicts) and \\(O(\\log n\\cdot\\log\\log n)\\) for the CREW PRAM (which allows simultaneous reads but not simultaneous writes). We also show that the problem of graphs isomorphism has expected parallel time \\(O(\\log\\log n)\\) for the CRCW PRAM and \\(O(\\log n)\\) for the CREW PRAM. Most of these results follow because of upper bounds on the mean depth of a graph, for more general graphs than was known before.   For undirected connectivity especially, we present a new probabilistic algorithm which runs on a randomized input and has an expected running time of \\(O(\\log\\log n)\\) on the CRCW PRAM, with \\(O(n)\\) expected number of processors only.   Our results also improve known upper bounds on the expected space required for sequential graph algorithms. For example, we show that the problem of finding connected components, transitive closure, minimum spanning trees, and minimum cost paths have expected sequential space \\(O(\\log n\\cdot\\log\\log n)\\) on a deterministic Turing Machine. We use a simulation of the CRCW PRAM to get these expected sequential space bounds.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186789$E07FAC19-A260-4802-AB00-BB088A44E713","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0dfbdb0929ddc22bcd5bd1c182b95d3875d4d630","datavalue":{"value":{"entity-type":"item","numeric-id":1164054,"id":"Q1164054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$F516B90B-A225-4633-A49E-6B513304CC6A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186789$86C39190-AEB3-4F8E-AFE5-3FC19F89432C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186789$A0B65D22-FB43-4087-AA31-2F66E9867158","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186789$30A413B4-96AF-48C6-BF9D-70346A778AF1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ce65f1082a3eb4ca0075d6914ff769729c67cddf","datavalue":{"value":"37164","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186789$CF76ED62-8C34-490B-8961-5BA6531A8EB1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b054bbd1ef16f604df0f61144322893e5b9a2a9","datavalue":{"value":"upper bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186789$FA3639A4-A24F-4011-9DA8-327BC94335A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"feef9ff0da63e4ac0b766e05f8fdf7002bcf8fc3","datavalue":{"value":"undirected and directed random graph problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186789$89AEAD05-EDF3-48A8-97A1-FCBE0BAF00D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0460a0356485c287af14e0288dac62f7c6b389e4","datavalue":{"value":"CRCW PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186789$8027CD8C-BBC6-4775-82D1-1745DC28085B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34f1528cd9548b088936bf54fdf77b3eb118e9bc","datavalue":{"value":"CREW PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186789$4D4D309B-18DC-4B22-AE3C-88A654CAC54A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3cdf21d0e331a47790f86a0203b4b15950c2a72f","datavalue":{"value":{"entity-type":"item","numeric-id":537850,"id":"Q537850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$066B4C88-E61F-4745-A961-5F76F94B2923","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d8112a4884ac488e222bb031fe5d75202a7b6dcb","datavalue":{"value":{"entity-type":"item","numeric-id":389952,"id":"Q389952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$650FD914-06F3-467C-B6FE-5EE9E522F9E2","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":"Q1186789$8DBBF53A-6B31-47E6-8C49-AD8BE87F4489","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"83c6293f25e8bc7e1747aa6978fc2fd52b5104b6","datavalue":{"value":{"entity-type":"item","numeric-id":1141153,"id":"Q1141153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$FC7CB1E3-4090-4055-AFC8-26BA3B409BA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1bb63192136286ee2b68ee1b226f2d4a02b4b9e","datavalue":{"value":{"entity-type":"item","numeric-id":3901544,"id":"Q3901544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$4B33FAAC-E81A-4EDC-BD20-0EC9B648F9AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48df165ba0da15b435264f2c0b648e0924d63a83","datavalue":{"value":{"entity-type":"item","numeric-id":3344024,"id":"Q3344024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$D5384816-8A85-4680-B6D1-28B06FE3038E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72bdc200c096a90cb093d01083b69c58672a0aa3","datavalue":{"value":{"entity-type":"item","numeric-id":3682518,"id":"Q3682518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$AF955708-0E9C-41DA-A9D4-DDF30DA0B1F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2bd35d34c8cb4660ca6ae9b0c6b460814b14576","datavalue":{"value":{"entity-type":"item","numeric-id":1082818,"id":"Q1082818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$3E797080-AABA-4280-88F7-B9B3A251445E","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":"Q1186789$D45BB0C5-368D-4302-BCCD-493DE9BB3837","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":"Q1186789$B033EDCE-1B43-4DB0-AEC3-A734251AC19E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cb1ec0d7ce822fb5941419bafd4a3f4e7cd71cd","datavalue":{"value":{"entity-type":"item","numeric-id":3753489,"id":"Q3753489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$1C983EDE-5E95-4238-A28E-F207DA751915","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a006907d50546bdc051c28c96b89ad928a5269a5","datavalue":{"value":{"entity-type":"item","numeric-id":1158753,"id":"Q1158753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$2DD95224-2672-441B-9164-F3636FA31C29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5212efd0654873f19dfdd6241d0cf7ca117e624a","datavalue":{"value":{"entity-type":"item","numeric-id":1825648,"id":"Q1825648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$F33E96F6-296F-47DD-A555-B6AC89AF098B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f6f2fa62f920fb46fbd79ba851e5cbf1f877777","datavalue":{"value":{"entity-type":"item","numeric-id":3922163,"id":"Q3922163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$88BED758-F2C0-4BC6-A85A-ADED93D859C9","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":"Q1186789$336FC2C2-1539-4CCC-B962-770FDF76D3FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9539532d16bcb82516fae2db58a1eb7e9c6ca7b","datavalue":{"value":{"entity-type":"item","numeric-id":5538132,"id":"Q5538132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$7389E956-0FBD-45CF-8B34-28BECD177416","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2628ffb9e59aa19553582ac944ed7dc8d827a3a","datavalue":{"value":{"entity-type":"item","numeric-id":5402548,"id":"Q5402548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$55C21BEB-E9C8-406B-9188-A2A2862B6767","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d53db4e61bfa2d597f0a53da172502701ac0503","datavalue":{"value":{"entity-type":"item","numeric-id":5402545,"id":"Q5402545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$C881F5E5-6309-444A-A5C1-2D2996B2AD8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00708b4078648865d18948bef9499b484690d96c","datavalue":{"value":{"entity-type":"item","numeric-id":3867197,"id":"Q3867197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$BCE26FB4-320A-4FF4-A2B4-C36D12A12F06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"295a70c178855625d44b3d929ce0d3758a1bb37f","datavalue":{"value":{"entity-type":"item","numeric-id":4144785,"id":"Q4144785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$5BD783A5-2E56-4E78-8239-B074EDD7F41B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"212a6eb14edd04072ee7d4c393c80f669541a3cf","datavalue":{"value":{"entity-type":"item","numeric-id":3914449,"id":"Q3914449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$5B28B190-16B2-48E3-9FD2-7371C93B2BE4","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":"Q1186789$4EC4E317-9EC1-46A9-88EE-8A12C4A9B1C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1543a6d9030474a2d21021a96f6fd782e1dd1a4e","datavalue":{"value":{"entity-type":"item","numeric-id":1167537,"id":"Q1167537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$C746471C-2FC3-4A18-B439-880F9AD9CE88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e472e71486639d0030dd63f9880bf07574170e62","datavalue":{"value":{"entity-type":"item","numeric-id":3769977,"id":"Q3769977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$630C1BC3-E0F5-4C63-BE1B-9EB232626526","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d86254fdb6d475affd1a3d53655f03856dd4f249","datavalue":{"value":{"entity-type":"item","numeric-id":3945587,"id":"Q3945587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$529C7E7C-678C-4412-A304-00BF1F1C25CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9920c3ac00d626f59f95283223bd4fb6ae680345","datavalue":{"value":{"entity-type":"item","numeric-id":1152951,"id":"Q1152951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$218C4221-873A-44D4-A105-53F9A669C862","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":"Q1186789$F1291B1A-E72B-420E-876A-2D6B3D1B55A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"736a1d463d18d2f300e2b9600c3f86eae2986ef8","datavalue":{"value":{"entity-type":"item","numeric-id":2537313,"id":"Q2537313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$A3FFB2BE-C255-4CF4-8D28-0A6AC6DEB85C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06b820d7730c4483ffdeaf5f1bb9567aad23b088","datavalue":{"value":{"entity-type":"item","numeric-id":3906428,"id":"Q3906428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$D3B709B9-1CA9-490F-9482-1011662203BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26589b0348552e2fca9722608c763f82407366f7","datavalue":{"value":{"entity-type":"item","numeric-id":3942729,"id":"Q3942729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186789$4AA70A3D-CE07-4B75-9C4B-4C8BC018A795","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b6c7cb46c6c7bf2b331ce84237ed99b1e1332826","datavalue":{"value":"https://doi.org/10.1007/bf01758779","type":"string"},"datatype":"url"},"type":"statement","id":"Q1186789$7A4E2701-F456-4C1D-968D-AC8F6CCA544F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"870c1f22464e6256f8705ad631aef265ace117c0","datavalue":{"value":"W1992595637","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186789$34469A43-2DB6-4EF7-A77C-E1A090B9C1BD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e84ddebf26beae59025f709940a0e8a970507231","datavalue":{"value":{"entity-type":"item","numeric-id":1356881,"id":"Q1356881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0586894b739318d3c1bc66b079654ab4a1bf8855","datavalue":{"value":{"amount":"+0.8205185532569885","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":"Q1186789$9F21E4EE-9324-41D3-9501-F6C364FDB25F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da06713c3c2d5621bddb65c699f41b518adc33af","datavalue":{"value":{"entity-type":"item","numeric-id":4406291,"id":"Q4406291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f886de5bfd3b72b62ab5626e7cc654de19ce2b1","datavalue":{"value":{"amount":"+0.8112529516220093","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":"Q1186789$F4E37FB6-EE92-4A20-B657-088AB27BAA88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"093ed31936388b5223617cb9fada8cbefdd1eb22","datavalue":{"value":{"entity-type":"item","numeric-id":758188,"id":"Q758188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c067a934f50090db42baba862e1b2bb3389a32a","datavalue":{"value":{"amount":"+0.811083972454071","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":"Q1186789$BF451FD5-2FD5-45E3-AB25-B3595D47416C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2df77f981a88e7f067dbb2a0ab9d782e2a8b53a1","datavalue":{"value":{"entity-type":"item","numeric-id":4252292,"id":"Q4252292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b27e14e46d38e840ea65b79f209b767038d5ad1d","datavalue":{"value":{"amount":"+0.8080826997756958","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":"Q1186789$1FDDCC48-E1B6-406C-8F08-25B0B46F907E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67027431139edee79ceb4a70b25a5ae6c6800197","datavalue":{"value":{"entity-type":"item","numeric-id":1825648,"id":"Q1825648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcc6fca82c8788e6fb2487802141d2b42cf5c4a2","datavalue":{"value":{"amount":"+0.8061345815658569","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":"Q1186789$4E84CD69-735E-4E42-92BA-D427ECDBE408","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Expected parallel time and sequential space complexity of graph and digraph problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Expected_parallel_time_and_sequential_space_complexity_of_graph_and_digraph_problems"}}}}}