The probabilistic longest path problem

DOI10.1002/(SICI)1097-0037(199905)33:3%3C207::AID-NET7%3E3.0.CO;2-7MaRDI QIDQ4254356zbMATH OpenOpenAlexFDO

Authors C. Murat, Vangelis Th. Paschos

Publication date 29 June 1999

Full work available at URL https://doi.org/10.1002/(sici)1097-0037(199905)33:3%3C207::aid-net7%3E3.0.co;2-7

zbMATH Keywords

complexitiesprobabilistic combinatorial optimizationprobabilistic longest path problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Stochastic network models in operations research (90B15) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Maximum probability shortest path problem
• A fully polynomial time approximation scheme for the probability maximizing shortest path problem
• Maximum probabilistic all-or-nothing paths
• scientific article; zbMATH DE number 844506
• Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG

Cited in

(11)

• The probabilistic minimum dominating set problem
• On the probabilistic min spanning tree problem
• Maximum probabilistic all-or-nothing paths
• On the probabilistic minimum coloring and minimum k-coloring
• A survey on combinatorial optimization in dynamic environments
• Theory and application of reciprocal transformation of “path problem” and “time float problem”
• Probabilistic models for the Steiner tree problem
• Information security: Designing a stochastic-network for throughput and reliability
• Vertex-Uncertainty in Graph-Problems
• Network reliability: Heading out on the highway
• Probabilistic graph-coloring in bipartite and split graphs

This page was built for publication: The probabilistic longest path problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4254356)