Computing shortest paths with uncertainty Export

@misc{citeulike:2826349, abstract = {We consider the problem of estimating the length of a shortest path in a DAG whose edge lengths are known only approximately but can be determined exactly at a cost. Initially, each edge e is known only to lie within an interval [l e ; he ]; the estimation algorithm can pay ce to find the exact length of e. In particular, we study the problem of finding the cheapest set of edges such that, if exactly these edges are queried, the length of the shortest path will be known, within an...}, author = {Feder, T. and Motwani, R. and O'Callaghan, L. and Olston, C. and Panigrahy, R.}, citeulike-article-id = {2826349}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.3794}, keywords = {graph-algorithms}, posted-at = {2008-05-23 17:18:16}, priority = {2}, title = {Computing shortest paths with uncertainty}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.3794}, year = {2003} }

TY - GEN ID - citeulike:2826349 L3 - citeulike-article-id:2826349 N2 - We consider the problem of estimating the length of a shortest path in a DAG whose edge lengths are known only approximately but can be determined exactly at a cost. Initially, each edge e is known only to lie within an interval [l e ; he ]; the estimation algorithm can pay ce to find the exact length of e. In particular, we study the problem of finding the cheapest set of edges such that, if exactly these edges are queried, the length of the shortest path will be known, within an... TI - Computing shortest paths with uncertainty KW - graph-algorithms AU - Feder, T AU - Motwani, R AU - O'Callaghan, L AU - Olston, C AU - Panigrahy, R PY - 2003/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.3794 ER -