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
Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Combinatorial probability (60C05)
Related Items (58)
Simple and optimal randomized fault-tolerant rumor spreading ⋮ Amnesiac flooding: synchronous stateless information dissemination ⋮ Distribution of Minimal Path Lengths when Edge Lengths are Independent Heterogeneous Exponential Random Variables ⋮ Unnamed Item ⋮ Broadcasting on paths and cycles ⋮ All-pairs shortest paths and the essential subgraph ⋮ Stochastic analysis of rumor spreading with multiple pull operations ⋮ On broadcasting time in the model of travelling agents ⋮ Asynchronous rumor spreading on random graphs ⋮ Diameter and broadcast time of random geometric graphs in arbitrary dimensions ⋮ Information Spreading in a Large Population of Active Transmitters and Passive Receivers ⋮ Randomised broadcasting: memory vs. randomness ⋮ Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs ⋮ Rumors Spread Slowly in a Small-World Spatial Network ⋮ Stateless Information Dissemination Algorithms ⋮ Push is Fast on Sparse Random Graphs ⋮ Shortest paths in random weighted graphs ⋮ Continuous-time stochastic analysis of rumor spreading with multiple operations ⋮ On the all-pairs shortest path algorithm of Moffat and Takaoka ⋮ Sharp Thresholds in Random Simple Temporal Graphs ⋮ Messy broadcasting - decentralized broadcast schemes with limited knowledge ⋮ Quasi-random rumor spreading: reducing randomness can be costly ⋮ Randomized Rumour Spreading: The Effect of the Network Topology ⋮ Asymptotics for pull on the complete graph ⋮ Direction-reversing quasi-random rumor spreading with restarts ⋮ Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems ⋮ On linear-time data dissemination in dynamic rooted trees ⋮ Probabilistic Analysis of Rumor-Spreading Time ⋮ The worst case behavior of randomized gossip protocols ⋮ Parsimonious flooding in dynamic graphs ⋮ Identifying frequent items in a network using gossip ⋮ Finding the shortest path in stochastic networks ⋮ Random shortest paths: non-Euclidean instances for metric optimization problems ⋮ On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph ⋮ Asymptotically Optimal Randomized Rumor Spreading ⋮ Finding real-valued single-source shortest paths in o(n 3) expected time ⋮ Propagation time for probabilistic zero forcing ⋮ Faster rumor spreading with multiple calls ⋮ Rumor spreading in social networks ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Expected coalescence time for a nonuniform allocation process ⋮ Efficient Broadcasting in Random Power Law Networks ⋮ Rumor spreading in random evolving graphs ⋮ Asymptotics for push on the complete graph ⋮ Rumor spreading with bounded in-degree ⋮ On patching algorithms for random asymmetric travelling salesman problems ⋮ Introducing Quasirandomness to Computer Science ⋮ Sub-linear Universal Spatial Gossip Protocols ⋮ Breaking the \(\log n\) barrier on rumor spreading ⋮ Robustness of randomized rumour spreading ⋮ A Time-Randomness Tradeoff for Quasi-Random Rumour Spreading ⋮ Quasirandom broadcasting on the complete graph is as fast as randomized broadcasting ⋮ Rumor spreading on random regular graphs and expanders ⋮ A Forward-Backward Single-Source Shortest Paths Algorithm ⋮ Unnamed Item ⋮ Communication complexity of quasirandom rumor spreading ⋮ Synchronous concurrent broadcasts for intermittent channels with bounded capacities
Uses Software
Cites Work
- A note on two problems in connexion with graphs
- New Bounds on the Complexity of the Shortest Path Problem
- Random contact processes, snowball sampling and factorial series distributions
- A New Algorithm for Finding All Shortest Paths in a Graph of Positive Arcs in Average Time $O(n^2 \log ^2 n)$
- Unnamed Item
- Unnamed Item
This page was built for publication: The shortest-path problem for graphs with random arc-lengths