The shortest-path problem for graphs with random arc-lengths

From MaRDI portal
Publication:1086251

DOI10.1016/0166-218X(85)90059-9zbMath0608.05047OpenAlexW2059014957WikidataQ56852738 ScholiaQ56852738MaRDI QIDQ1086251

Geoffrey R. Grimmett, Alan M. Frieze

Publication date: 1985

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(85)90059-9




Related Items (58)

Simple and optimal randomized fault-tolerant rumor spreadingAmnesiac flooding: synchronous stateless information disseminationDistribution of Minimal Path Lengths when Edge Lengths are Independent Heterogeneous Exponential Random VariablesUnnamed ItemBroadcasting on paths and cyclesAll-pairs shortest paths and the essential subgraphStochastic analysis of rumor spreading with multiple pull operationsOn broadcasting time in the model of travelling agentsAsynchronous rumor spreading on random graphsDiameter and broadcast time of random geometric graphs in arbitrary dimensionsInformation Spreading in a Large Population of Active Transmitters and Passive ReceiversRandomised broadcasting: memory vs. randomnessFast shortest-paths algorithms in the presence of few destinations of negative-weight arcsRumors Spread Slowly in a Small-World Spatial NetworkStateless Information Dissemination AlgorithmsPush is Fast on Sparse Random GraphsShortest paths in random weighted graphsContinuous-time stochastic analysis of rumor spreading with multiple operationsOn the all-pairs shortest path algorithm of Moffat and TakaokaSharp Thresholds in Random Simple Temporal GraphsMessy broadcasting - decentralized broadcast schemes with limited knowledgeQuasi-random rumor spreading: reducing randomness can be costlyRandomized Rumour Spreading: The Effect of the Network TopologyAsymptotics for pull on the complete graphDirection-reversing quasi-random rumor spreading with restartsEfficient randomised broadcasting in random regular networks with applications in peer-to-peer systemsOn linear-time data dissemination in dynamic rooted treesProbabilistic Analysis of Rumor-Spreading TimeThe worst case behavior of randomized gossip protocolsParsimonious flooding in dynamic graphsIdentifying frequent items in a network using gossipFinding the shortest path in stochastic networksRandom shortest paths: non-Euclidean instances for metric optimization problemsOn Edge-Disjoint Spanning Trees in a Randomly Weighted Complete GraphAsymptotically Optimal Randomized Rumor SpreadingFinding real-valued single-source shortest paths in o(n 3) expected timePropagation time for probabilistic zero forcingFaster rumor spreading with multiple callsRumor spreading in social networksUnnamed ItemUnnamed ItemExpected coalescence time for a nonuniform allocation processEfficient Broadcasting in Random Power Law NetworksRumor spreading in random evolving graphsAsymptotics for push on the complete graphRumor spreading with bounded in-degreeOn patching algorithms for random asymmetric travelling salesman problemsIntroducing Quasirandomness to Computer ScienceSub-linear Universal Spatial Gossip ProtocolsBreaking the \(\log n\) barrier on rumor spreadingRobustness of randomized rumour spreadingA Time-Randomness Tradeoff for Quasi-Random Rumour SpreadingQuasirandom broadcasting on the complete graph is as fast as randomized broadcastingRumor spreading on random regular graphs and expandersA Forward-Backward Single-Source Shortest Paths AlgorithmUnnamed ItemCommunication complexity of quasirandom rumor spreadingSynchronous concurrent broadcasts for intermittent channels with bounded capacities


Uses Software


Cites Work


This page was built for publication: The shortest-path problem for graphs with random arc-lengths