Computing a Most Probable Delay Constrained Path: NP-Hardness and Approximation Schemes

DOI10.1109/TC.2011.61MaRDI QIDQ5277615zbMATH OpenOpenAlexFDO

Authors Ying Xiao, Krishnaiyan Thulasiraman, Xi Fang, Dejun Yang, Guoliang Xue

Publication date 12 July 2017

Published in IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/tc.2011.61

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cited in

(5)

• Itinerary planning with time budget for risk-averse travelers
• Delay-constrained shortest paths: approximation algorithms and second-order cone models
• A fully polynomial time approximation scheme for the probability maximizing shortest path problem
• Finding cheapest deadline paths
• An edge-turbulence algorithm for the 2-MRS problem on trees with unreliable edges

This page was built for publication: Computing a Most Probable Delay Constrained Path: NP-Hardness and Approximation Schemes

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