Premium
The probabilistic longest path problem
Author(s) -
Murat Cécile,
Paschos Vangelis Th.
Publication year - 1999
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199905)33:3<207::aid-net7>3.0.co;2-7
Subject(s) - probabilistic logic , path (computing) , computer science , mathematical optimization , probabilistic analysis of algorithms , theoretical computer science , algorithm , mathematics , artificial intelligence , programming language
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 strategy, and we evaluate the complexities of computing this functional and of computing the deterministic solution maximizing it. © 1999 John Wiley & Sons, Inc. Networks 33: 207–219, 1999