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

No abstract is available for this paper.

• Publication year

  1985

• Venue

  Discrete Applied Mathematics

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0166-218X(85)90059-9
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Random contact processes, snowball sampling and factorial series distributions

  1983cited by this paper
• A shortest-path algorithm with expected time O(n2 log n log* n)

  1980influential reference
• New Bounds on the Complexity of the Shortest Path Problem

  1976cited by this paper
• The Design and Analysis of Computer Algorithms

  1974cited by this paper
• A New Algorithm for Finding all Shortest Paths in a Graph of Positive Arcs in Average Time 0(n2 log2n)

  1973cited by this paper
• Algorithm 97: Shortest path

  1962influential reference
• A note on two problems in connexion with graphs

  1959cited by this paper

• Rumors on evolving graphs through stationary times

  2025cites this paper
• Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders

  2025cites this paper
• Opinion Dynamics: A Comprehensive Overview

  2025cites this paper
• On the average-case complexity of Berge algorithm

  2025cites this paper
• Distributed identification of stable large-scale isomorphic nonlinear networks using partial observations

  2024influential citation
• Uniform Sampling of Negative Edge Weights in Shortest Path Networks

  2024cites this paper
• Rumour Spreading Depends on the Latent Geometry and Degree Distribution in Social Network Models

  2024cites this paper
• Why the Metric Backbone Preserves Community Structure

  2024cites this paper
• Randomized Rumor Spreading Revisited (Long Version)

  2023cites this paper
• Self-Stabilizing Clock Synchronization in Probabilistic Networks

  2023cites this paper
• Weighted Tree Games

  2023influential citation
• How Fast do Rumours Spread?

  2023cites this paper
• Continuous-Time Stochastic Analysis of Rumor Spreading with Multiple Operations

  2023cites this paper
• Increasing paths in random temporal graphs

  2023cites this paper
• On the expected efficiency of branch and bound for the asymmetric TSP

  2023cites this paper
• Stochastic Analysis of Rumor Spreading with Multiple Pull Operations in Presence of Non-cooperative Nodes

  2023cites this paper
• Solving a Random Asymmetric TSP Exactly in Quasi‐Polynomial Time W.H.P.

  2023cites this paper
• Rumors with Changing Credibility

  2023influential citation
• Karp's patching algorithm on random perturbations of dense digraphs

  2022cites this paper
• LS-Gossip: An Improved Block Distribution Algorithm in Blockchain Networks

  2022cites this paper
• Amnesiac Flooding: Synchronous Stateless Information Dissemination

  2021cites this paper
• Cooperation in Large Societies∗

  2021cites this paper
• Asynchronous Gossip in Smartphone Peer-to-Peer Networks

  2021cites this paper
• Stochastic Analysis of Rumor Spreading with Multiple Pull Operations

  2021cites this paper
• Non asymptotic bounds in asynchronous sum-weight gossip protocols

  2021cites this paper
• Communication and Community Enforcement

  2021cites this paper
• Asymptotics for pull on the complete graph

  2021cites this paper
• Analysis of Rumor Spreading with 2-pull or 3-pull Operations

  2021cites this paper
• Who Started This Rumor? Quantifying the Natural Differential Privacy of Gossip Protocols

  2020cites this paper
• Sharp Thresholds in Random Simple Temporal Graphs

  2020cites this paper
• Analysis of Amnesiac Flooding

  2020cites this paper
• Structural Information and Communication Complexity: 27th International Colloquium, SIROCCO 2020, Paderborn, Germany, June 29–July 1, 2020, Proceedings

  2020cites this paper
• Stateless Information Dissemination Algorithms

  2020cites this paper
• Asymptotics for Push on the Complete Graph

  2020cites this paper
• Synchronous Concurrent Broadcasts for Intermittent Channels with Bounded Capacities

  2020cites this paper
• Social Learning in Multi Agent Multi Armed Bandits

  2020cites this paper
• On Broadcasting Time in the Model of Travelling Agents

  2020cites this paper
• Pulling multiple nodes for rumor spreading

  2020cites this paper
• Evolution Matters: Content Transmission in Evolving Wireless Social Networks

  2020cites this paper
• Probabilistic Analysis of Rumor-Spreading Time

  2020cites this paper
• Broadcasting on paths and cycles

  2020cites this paper
• On linear-time data dissemination in dynamic rooted trees

  2019cites this paper
• Random Gossip Processes in Smartphone Peer-to-Peer Networks

  2019cites this paper
• HABILITATION À DIRIGER LES RECHERCHES

  2019cites this paper
• Equilibrium-Based Voting: A Strategy for Electing Service Providers in P2P E-Learning

  2019influential citation
• Two-stage multicriteria georeferenced express analysis of new electric transmission line projects

  2019cites this paper
• Social Learning in Multi Agent Multi Armed Bandits

  2019cites this paper
• An Improved Gossip Algorithm Based on Semi-Distributed Blockchain Network

  2019cites this paper
• Randomized Information Dissemination in Dynamic Environments

  2019cites this paper
• The Capacity of Smartphone Peer-to-Peer Networks

  2019cites this paper
• Who started this rumor? Quantifying the natural differential privacy guarantees of gossip protocols

  2019influential citation
• Robustness of randomized rumour spreading

  2019cites this paper
• Who started this rumor? Quantifying the natural differential privacy guarantees of gossip protocols

  2019influential citation
• Brief Announcement: Ultra-Fast Asynchronous Randomized Rumor Spreading

  2019cites this paper
• Distributed Data Summarization in Well-Connected Networks

  2019cites this paper
• Ultra-Fast Asynchronous Randomized Rumor Spreading (Brief Announcement)

  2019cites this paper
• Rumor Spreading and Conductance

  2018cites this paper
• Randomized Rumor Spreading in Ad Hoc Networks with Buffers

  2018cites this paper
• Consensus Needs Broadcast in Noiseless Models but can be Exponentially Easier in the Presence of Noise

  2018cites this paper
• Optimal Gossip Algorithms for Exact and Approximate Quantile Computations

  2017cites this paper
• Precise Analysis of Epidemic Algorithms

  2017cites this paper
• Equilibria of rumor propagation: Deterministic and network approaches

  2017cites this paper
• Breaking the $$\log n$$logn barrier on rumor spreading

  2017cites this paper
• Gossip in a Smartphone Peer-to-Peer Network

  2017cites this paper
• Optimal epidemic dissemination

  2017cites this paper
• Parallelization of shortest path algorithm using OpenMP and MPI

  2017cites this paper
• Ant-Inspired Dynamic Task Allocation via Gossiping

  2017cites this paper
• FIFO Queues Are Bad for Rumor Spreading

  2017cites this paper
• Leader Election in a Smartphone Peer-to-Peer Network

  2017cites this paper
• Optimal broadcasting in networks with faulty nodes

  2017cites this paper
• Random Graphs and Algorithms

  2017cites this paper
• Randomized Rumor Spreading Revisited

  2017cites this paper
• Universal protocols for information dissemination using emergent signals

  2017cites this paper
• Linear-Time Data Dissemination in Dynamic Networks

  2017cites this paper
• Spreading a Confirmed Rumor: A Case for Oscillatory Dynamics

  2017cites this paper
• Pull and Push&Pull in Random Evolving Graphs

  2017cites this paper
• An Efficient General Decentralized Clustering Exploiting Hierarchy

  2017cites this paper
• Push is Fast on Sparse Random Graphs

  2017cites this paper
• Tight(er) bounds for similarity measures, smoothed approximation and broadcasting

  2016cites this paper
• Ephemeral networks with random availability of links: The case of fast networks

  2016cites this paper
• Rumors Spread Slowly in a Small-World Spatial Network

  2016cites this paper
• Centrality-Aware Link Recommendations

  2016cites this paper
• Efficient computation of Harmonic Centrality on large networks: theory and practice

  2016cites this paper
• Analysis of the propagation time of a rumour in large-scale distributed systems

  2016cites this paper
• On spreading rumor in heterogeneous systems

  2016cites this paper
• Deposited in DRO : 28 October 2015 Version of attached le : Accepted Version Peer-review status of attached

  2016cites this paper
• How to Discreetly Spread a Rumor in a Crowd

  2016cites this paper
• Modélisation de la variabilité des temps de parcours et son intégration dans des algorithmes de recherche du plus court chemin stochastique

  2016cites this paper
• A Review and Evaluations of Real Time Shortest Path according to current traffic on road

  2015cites this paper
• Faster Rumor Spreading With Multiple Calls

  2015influential citation
• Why are certain polynomials hard?: A look at non-commutative, parameterized and homomorphism polynomials

  2015cites this paper
• Minimizing Seed Selection for Disseminating News with Probabilistic Coverage Guarantee

  2015cites this paper
• GDCluster: A General Decentralized Clustering Algorithm

  2015cites this paper
• Gossiping with Message Splitting on Structured Networks

  2015cites this paper
• Rumor Spreading with Bounded In-Degree

  2015cites this paper
• Supercritical minimum mean-weight cycles

  2015cites this paper
• Rumours Spread Slowly in a Small World Spatial Network

  2015cites this paper
• The power of frequency hopping and information dissemination in constrained communication models

  2015influential citation
• Random walk-based algorithms on networks

  2015cites this paper
• Breaking the log n barrier on rumor spreading

  2015cites this paper