The expected length of a shortest path
type: Item
instance of: scholarly article
title: The expected length of a shortest path
zbMATH Open document ID: 0784.68064
DOI: 10.1016/0020-0190(93)90059-I
author: K. Appert
published in: Information Processing Letters
publication date: 1994-03-27T00:00:00Z
review text: The object under consideration is a directed complete graph whose arc lengths are independent and exponentially distributed with parameter \(\mu\). For the expected length of a shortest path an easily -- computable summation formula and a closed -- form approximation function are given. Also experimental validation of this result is given.
reviewed by: Andreas Brandstädt
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 404998
zbMATH Keywords: graphs with random arc lengths
zbMATH Keywords: expected length of shortest paths
MaRDI profile type: Publication
cites work: Shortest Paths in Probabilistic Graphs
cites work: On Shortest Paths in Graphs with Random Weights
cites work: Shortest paths in networks with exponentially distributed arc lengths
cites work: Distribution of the Time Through a Directed, Acyclic Network
cites work: The use of cutsets in Monte Carlo analysis of stochastic networks
cites work: The Stochastic Shortest Route Problem
full work available at URL: 0020-0190(93)90059-i
OpenAlex ID: W2074567977
description: scientific article; zbMATH DE number 404998