{"entities":{"Q4458873":{"pageid":6488472,"ns":120,"title":"Item:Q4458873","lastrevid":48251668,"modified":"2026-01-04T03:08:44Z","type":"item","id":"Q4458873","labels":{"en":{"language":"en","value":"Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2055948"}},"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":"Q4458873$C8A413BF-28D9-41D4-9014-A1DEB2D09B32","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"161d69c8a375e9a68eda937817ba02611bff1307","datavalue":{"value":{"text":"Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4458873$002F4E46-AFBC-4DB2-967C-C867D5883504","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"00ca191428d39c9af22bd557c9668b7f3a0734b1","datavalue":{"value":"1079.68108","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4458873$08FF1F21-0DFE-4E65-AB8C-1EC10B53CF57","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4a3e82e052d7550330c1dfaa30d12539479bc057","datavalue":{"value":"10.1016/S0196-6774(03)00046-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4458873$BF7786C1-2997-4829-A5D5-C5E55D9116B1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cd9fbb394b28077228a63075a7a7dd0d7669b6d6","datavalue":{"value":{"entity-type":"item","numeric-id":495671,"id":"Q495671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4458873$2F212EA9-2D68-4BF7-A29F-783505F70FDB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"9bcfebe9d23b7752651008b0d843e08ec7c57a37","datavalue":{"value":{"entity-type":"item","numeric-id":2709787,"id":"Q2709787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4458873$5AB2C949-C097-4BAF-AE17-7D96D7005AC4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"947fc07e6e3c9508b7adeaf87fe542c1ae2d0058","datavalue":{"value":{"time":"+2004-03-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4458873$3C33F802-570B-4A0A-83A1-17906D9D11DB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4458873$E7671052-ED39-4481-9A9A-A88EA996385C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4458873$7DF40B66-B61B-40C4-93AF-BED6B5369B5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4458873$736567C8-6AAF-4A9A-9BEC-23F9DE37BE9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4458873$4E9114CD-5F33-4B57-BEE2-80196DCBEA92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4458873$19E265A0-DF21-4DDB-9343-F3B08CE96011","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9b8628f5f15585156ff812682d6a71f376f01dc5","datavalue":{"value":"2055948","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4458873$A6C7607C-B413-4212-AB7C-8DAAEE689530","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"46d149109f50ea8b4091da3da75f5f3e196ce20d","datavalue":{"value":"Bellman-Ford algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q4458873$E0B6B1C5-7C5F-4976-97C9-6769C8AF19CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e45935b0d4454547cd62017e646bcb37bfeae128","datavalue":{"value":"Pallottino's incremental graph algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q4458873$9634559F-532C-4166-8CE7-992E70A60AE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eed25e11fa14da5191bc8da171e199e2884b8ed5","datavalue":{"value":"threshold approach","type":"string"},"datatype":"string"},"type":"statement","id":"Q4458873$491C9F11-20DF-44F3-AD26-02B4B6FA7834","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4d2edbebb161e74866b2ab0c8c31eb23204e86e","datavalue":{"value":"topological ordering SSSP algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q4458873$228FD35A-2F40-49DF-B106-51B6F659426F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"33d3a521d61dab8010b86add90b9b1d5c67944c1","datavalue":{"value":"approximate Bucket implementation","type":"string"},"datatype":"string"},"type":"statement","id":"Q4458873$19DC2351-0267-4D4D-84A1-9E25135E8D5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0189ff4c17b2a3d70cc2a97abc6ce16bf8655c11","datavalue":{"value":"\\(\\Delta\\)-stepping algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q4458873$B98E142A-0DD4-4114-87F3-73830C53DE2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6714e6ee79a947c8d750141daa6c3c1d592f1089","datavalue":{"value":"graphs with random edge weights","type":"string"},"datatype":"string"},"type":"statement","id":"Q4458873$8B9E19B8-6177-4270-9E6E-6BDE3424330D","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":"Q4458873$BAFF5009-AB00-4BFF-A6FD-FF9EC631F8F3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b62bbc34137d92306c2dca862c9c2835b3a08966","datavalue":{"value":"https://doi.org/10.1016/s0196-6774(03)00046-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q4458873$20B20622-283F-4E1A-8AB2-08AF05473E61","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"de2a165bde46ba55aaa640728a086ce3e199032d","datavalue":{"value":"W2118169763","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4458873$DA9834F4-B14A-4ACF-99AC-0A0B60B6C2A6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e59dca878a030016d920f00275b88a89b9fc217c","datavalue":{"value":{"entity-type":"item","numeric-id":2999348,"id":"Q2999348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"124c0cbb9a3332aa9e7bf3f04e024ec126a07fd2","datavalue":{"value":{"amount":"+0.9159319400787354","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":"Q4458873$6A82030A-1CD2-46F9-9BB5-2821E6E3815B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9a7cbe4258461f253e85edcf8efecd7eb029c99","datavalue":{"value":{"entity-type":"item","numeric-id":2768384,"id":"Q2768384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c26beff07c57aa627062d82be4fadac257dd3025","datavalue":{"value":{"amount":"+0.9043896198272704","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":"Q4458873$F3990DB1-C2AC-47BF-8427-7BBE457A48B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1503f6f299d835407b4e09a96cb45a37eb891502","datavalue":{"value":{"entity-type":"item","numeric-id":2432528,"id":"Q2432528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f153a97e1098add2a493502178cf90978d83c135","datavalue":{"value":{"amount":"+0.8417655825614929","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":"Q4458873$4918406E-3663-4DED-8DAB-78801167D327","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"339e108822f43338b635c7e0e465f0620e9a4a22","datavalue":{"value":{"entity-type":"item","numeric-id":5309714,"id":"Q5309714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e5b194946430e6351bfedb719eb53affbfc2844","datavalue":{"value":{"amount":"+0.8300458788871765","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":"Q4458873$709C5873-9CB2-4025-8CCA-D56753AD84B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6914abe67ad3e4f0ed5dd620a05d53062326a7a1","datavalue":{"value":{"entity-type":"item","numeric-id":4943352,"id":"Q4943352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f05aa59f6fae715ff20d98834bbffd5cd3f4709","datavalue":{"value":{"amount":"+0.8219677209854126","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":"Q4458873$04177999-D3D1-4141-B948-07AFEFA4BFA4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4458873","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4458873"}}}}}