The probabilistic longest path problem

Authors
Murat, C Paschos, VT
Citation
C. Murat et Vt. Paschos, The probabilistic longest path problem, NETWORKS, 33(3), 1999, pp. 207-219
Citations number
10
Categorie Soggetti
Computer Science & Engineering
Journal title
NETWORKS
ISSN journal
00283045 → ACNP
Volume
33
Issue
3
Year of publication
1999
Pages
207 - 219
Database
ISI
SICI code
0028-3045(199905)33:3<207:TPLPP>2.0.ZU;2-J
Abstract
We study the probabilistic longest path problem. We propose a modification strategy adapting a solution for a deterministic instance to a solution for the probabilistic one, we compute the functional associated with this stra tegy, and we evaluate the complexities of computing this functional and of computing the deterministic solution maximizing it. (C) 1999 John Wiley & S ons, Inc.