{"entities":{"Q1086251":{"pageid":1097003,"ns":120,"title":"Item:Q1086251","lastrevid":42865755,"modified":"2025-07-15T13:00:05Z","type":"item","id":"Q1086251","labels":{"en":{"language":"en","value":"The shortest-path problem for graphs with random arc-lengths"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3983204"}},"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":"Q1086251$10F9126E-B611-46FC-885E-8F825E4458B7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b1adc5e1298e0dac69846bc7f5668226a56cf8f6","datavalue":{"value":{"text":"The shortest-path problem for graphs with random arc-lengths","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1086251$AFDF7B8C-0A59-4B1D-9454-6C1E4E83F635","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d2958eafed5954224823ce2fee21735f79815c40","datavalue":{"value":"0608.05047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086251$9FF53B97-5B06-4008-B92F-6DD7CB9DB907","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c4fb9cbf64266e10e7bb743978c4138f12640a57","datavalue":{"value":"10.1016/0166-218X(85)90059-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086251$FE025EDC-16D5-41E0-AEF4-A74ABE71B7C3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086251$5E3B1924-A8C9-441A-A35B-4E61063007FF","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":"Q1086251$564D1E04-949D-4F38-84E1-7EAB391DE5EA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"58d12c153c43236a751cb9a1cb32af80c90059d8","datavalue":{"value":"We consider the problem of finding the shortest distance between all pairs of vertices in a complete digraph on n vertices, whose arc-lengths are non-negative random variables. We describe an algorithm which solves this problem in \\(O(n(m+n \\log n))\\) expected time, where m is the expected number of arcs with finite length. If m is small enough, this represents a small improvement over the bound in \\textit{P. A. Bloniarz} [Techn. Rep. 80-3, Dept. Comput. Sci., SUNY at Albany (August 1980); see also SIAM J. Comput. 12, 588-560 (1983; Zbl 0521.68078)]. We consider also the case when the arc-lengths are random variables which are independently distributed with distribution function F, where \\(F(0)=0\\) and F is differentiable at 0; for this case, we describe an algorithm which runs in \\(O(n^ 2\\log n)\\) expected time.    In our treatment of the shortest-path problem we consider the following problem in combinatorial probability theory. A town contains n people, one of whom knows a rumour. At the first stage he tells someone chosen randomly from the town; at each stage, each person who knows the rumour tell someone else, chosen randomly from the town and independently of all other choices. Let \\(S_ n\\) be the number of stages before the whole town knows the rumour. We show that \\(S_ n/\\log_ 2n\\to 1+\\log_ e2\\) in probability as \\(n\\to \\infty\\), and estimate the probabilities of large deviations in \\(S_ n\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1086251$D6A38C97-E09F-489B-9C45-7AADBFE8256B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086251$5EFC169F-7A05-4D9F-AEB5-B6C2D50449A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086251$28070873-713F-4DC8-A479-2A6C7C3E7BF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086251$5EC2AAB8-62F6-4A27-B5E5-792AA473FED6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b7275e0d4b526075acce84a242d8537e929bb2d","datavalue":{"value":"60C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086251$A5CD1111-2475-4390-BA57-09B80663B660","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086251$7918CCAB-D128-40DC-AA32-D723DE5BE8F0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2060bd64ac952782f723a855ea826558545a6848","datavalue":{"value":"3983204","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086251$38C4610D-6C1D-4E70-A10C-9C5AEA95CDAF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1086251$DDCB4578-632F-4C6B-A7DF-4A20E6ACE0A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b68bf22b6ea6dbda8bebf928107c946a7debc990","datavalue":{"value":"arc-lengths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1086251$E5FB405F-D189-4D8C-AA5F-26D3FFCAA3F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78069297bd30e9fe69be46605dc652d6d7ffe91e","datavalue":{"value":"shortest-path problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1086251$0310CF9F-98BA-4305-B0F8-87FE247FC6D4","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"7b5c75d2b9af4216c1a75c44c6b68310d0016550","datavalue":{"value":"Q56852738","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086251$B5ED8402-3118-4AD2-9EC6-5BFA9F972D04","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ee31696a3be6df3bdd79f474603a4526c11abc4","datavalue":{"value":{"entity-type":"item","numeric-id":1577015,"id":"Q1577015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086251$494CFA4D-DA07-485E-958A-0E4589AADA9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a7f7119d5407047e349351e6c0280b9bf47d5a63","datavalue":{"value":{"entity-type":"item","numeric-id":301808,"id":"Q301808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086251$08EC5CA4-774D-4221-A708-D05A01D448C9","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"1412ceb6c71a23f10e8f7e008bf034264afa1496","datavalue":{"value":{"entity-type":"item","numeric-id":41444,"id":"Q41444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086251$5B0B80A7-F035-4841-8F04-7B628699788E","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":"Q1086251$6BE5F9AC-0784-4ABF-ACF0-B1D06C90A79F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086251$BA6DEEE7-B1D6-4F97-A3F5-FCC9302D9321","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6b9bd619a6cb935cf602809b975ab212b4da797","datavalue":{"value":{"entity-type":"item","numeric-id":4747296,"id":"Q4747296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086251$71E75684-D8A3-4B17-8909-A84563173D67","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":"Q1086251$93A14AEC-ADF9-4893-8DC4-CD9E19408759","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14acfe2f4f339610911d7bf217920bda5474651c","datavalue":{"value":{"entity-type":"item","numeric-id":4091447,"id":"Q4091447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086251$96E60431-AC68-4514-A2AF-C99FBD9FD1CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e0cf74d931aaff34d1d8fcb3bce04750e284aea","datavalue":{"value":{"entity-type":"item","numeric-id":4003764,"id":"Q4003764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086251$D4A2D585-7C8D-4829-B8C9-2FDB51E59E45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfa111708107f38db5b38bd20d9da2aed453dead","datavalue":{"value":{"entity-type":"item","numeric-id":5668831,"id":"Q5668831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086251$38478155-278A-48BB-B879-9FF21729BE18","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1508e9123295b23613e279b14f38414291e0fe48","datavalue":{"value":"https://doi.org/10.1016/0166-218x(85)90059-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1086251$8CD7E165-79CA-471A-9D7C-59A2ABDF4D6D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ef68deab666ae8d21553938628368150bc89e4be","datavalue":{"value":"W2059014957","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086251$DA54DF48-E5B4-48D1-8483-281104E65BB1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a30e33c6d6d31138157ead62f46db629b1e56fca","datavalue":{"value":{"entity-type":"item","numeric-id":5287451,"id":"Q5287451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd28370cdd45bcb345b0a983075edc9ee07e1a44","datavalue":{"value":{"amount":"+0.9292747","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1086251$7676B08A-93E0-42C1-828B-17E82CE67794","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1b9ffabeeb7e2a2a224e42a3b041b10eb238290","datavalue":{"value":{"entity-type":"item","numeric-id":3699721,"id":"Q3699721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac4374eccdd679464cce6f8edc62f33105c94b44","datavalue":{"value":{"amount":"+0.92817545","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1086251$6C4A18F4-E102-47FB-BD72-DC233E11EB24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c60aab4075bafd81a9dc28f7956e5ecea06b87e","datavalue":{"value":{"entity-type":"item","numeric-id":2230798,"id":"Q2230798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4024b1b56e4a3eba4aa377bec0b3d417734e8d2c","datavalue":{"value":{"amount":"+0.92257786","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1086251$CAB5935A-C620-4485-8FD6-A6F3D0316A2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d57ac0035cf7d2286b448516a8b12145e8bbd35","datavalue":{"value":{"entity-type":"item","numeric-id":3787813,"id":"Q3787813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45cd74909e79463d599f54a63c1563d811ec2114","datavalue":{"value":{"amount":"+0.92111254","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1086251$A246ED6B-685F-4ED8-88EC-60C988ABFF0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c51fd30ec8dd9ed0b30a3ba518d3b4d7a7a08a7","datavalue":{"value":{"entity-type":"item","numeric-id":4005305,"id":"Q4005305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9cdb57afc0b2de3c41526f083071ff1667a5fe3","datavalue":{"value":{"amount":"+0.9172293","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1086251$F9C76456-6C6E-422C-9EF7-FBA268A8B1E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68d50230892e08491d88e4928669b53fd0b602f2","datavalue":{"value":{"entity-type":"item","numeric-id":6085709,"id":"Q6085709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7409557e346e97a927c727b36fb404075df8d06c","datavalue":{"value":{"amount":"+0.91570455","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1086251$8256A8F3-A476-4628-8AE7-9B4FD9BE26C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63dfcf2a27134ac8800956342765f6bb2849214a","datavalue":{"value":{"entity-type":"item","numeric-id":3301996,"id":"Q3301996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32a2ffa2e2f29ac1a4b85c9974d5ab813c027963","datavalue":{"value":{"amount":"+0.91171765","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1086251$ECE41F3A-41BD-4B82-B88E-6B74AEE27C46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"217926786e68f2da4bd0742d248a6376c5daec47","datavalue":{"value":{"entity-type":"item","numeric-id":3192154,"id":"Q3192154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98482286932fbf19c892d31f1421162212692e51","datavalue":{"value":{"amount":"+0.9108609","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1086251$E429F558-1CDD-44A8-BB63-DB4469A03997","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0fc3f57dd6e4d10e9202e7ccfb94e975f57b00f9","datavalue":{"value":{"entity-type":"item","numeric-id":2225067,"id":"Q2225067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae29904c41bae136b670edb870d5773628c393b4","datavalue":{"value":{"amount":"+0.9060528","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1086251$DDB7DE25-7A37-45E7-BC08-8527A50F78DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5574bffcd912be08fbb151f67b048d669ace17ac","datavalue":{"value":{"entity-type":"item","numeric-id":5323768,"id":"Q5323768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0dc01d51de374c91f1afd3cf54db6290444ac53b","datavalue":{"value":{"amount":"+0.90483975","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1086251$FD0A50BE-A078-4699-9939-1773F55EFDC0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1086251","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1086251"}}}}}