{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T18:44:20Z","timestamp":1776105860057,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T00:00:00Z","timestamp":1558396800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T00:00:00Z","timestamp":1558396800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100011260","name":"FP7 Research infrastructures","doi-asserted-by":"crossref","award":["610764"],"award-info":[{"award-number":["610764"]}],"id":[{"id":"10.13039\/100011260","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,2]]},"DOI":"10.1007\/s00224-019-09928-w","type":"journal-article","created":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T23:00:09Z","timestamp":1558479609000},"page":"227-250","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Optimal Path Discovery Problem with Homogeneous Knowledge"],"prefix":"10.1007","volume":"64","author":[{"given":"Christopher","family":"Thraves Caro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5552-9134","authenticated-orcid":false,"given":"Josu","family":"Doncel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Olivier","family":"Brun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,5,21]]},"reference":[{"key":"9928_CR1","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications, 1st edn. Prentice Hall (1993)"},{"key":"9928_CR2","unstructured":"Alon, N., Emek, Y., Feldman, M., Tennenholtz, M.: Economical graph discovery. In: ICS, pp. 476\u2013486 (2011)"},{"issue":"1","key":"9928_CR3","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/S0167-6377(03)00058-0","volume":"32","author":"ID Aron","year":"2004","unstructured":"Aron, I.D., Van Hentenryck, P.: On the complexity of the robust spanning tree problem with interval data. Oper. Res. Lett. 32(1), 36\u201340 (2004)","journal-title":"Oper. Res. Lett."},{"key":"9928_CR4","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R Bellman","year":"1958","unstructured":"Bellman, R.: On a routing problem. Q. Appl. Math. 16, 87\u201390 (1958)","journal-title":"Q. Appl. Math."},{"issue":"4","key":"9928_CR5","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s00224-004-1180-4","volume":"38","author":"R Bruce","year":"2005","unstructured":"Bruce, R., Hoffmann, M., Krizanc, D., Raman, R.: Efficient update strategies for geometric computing with uncertainty. Theory Comput. Syst. 38(4), 411\u2013423 (2005)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"9928_CR6","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/BF02592101","volume":"73","author":"BV Cherkassky","year":"1996","unstructured":"Cherkassky, B.V., Goldberg, A.V., Radzik, T.: Shortest paths algorithms: Theory and experimental evaluation. Math. Program. 73(2), 129\u2013174 (1996)","journal-title":"Math. Program."},{"key":"9928_CR7","unstructured":"Davis, H.W., Pollack, R.B., Sudkamp, T.: Towards a better understanding of bidirectioanl search. In: AAAI (1984)"},{"issue":"1","key":"9928_CR8","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/322358.322360","volume":"30","author":"D de Champeaux","year":"1983","unstructured":"de Champeaux, D.: Bidirectional heuristic search again. J. ACM 30(1), 22\u201332 (1983)","journal-title":"J. ACM"},{"key":"9928_CR9","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1, 269\u2013271 (1959)","journal-title":"Numer. Math."},{"issue":"C","key":"9928_CR10","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.tcs.2015.11.025","volume":"613","author":"T Erlebach","year":"2016","unstructured":"Erlebach, T., Hoffmann, M., Kammer, F.: Query-competitive algorithms for cheapest set problems under uncertainty. Theor. Comput. Sci. 613(C), 51\u201364 (2016)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9928_CR11","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1137\/S0097539701395668","volume":"32","author":"T Feder","year":"2003","unstructured":"Feder, T., Motwani, R., Panigrahy, R., Olston, C., Widom, J.: Computing the median with uncertainty. SIAM J. Comput. 32(2), 538\u2013547 (2003)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9928_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jalgor.2004.07.005","volume":"62","author":"T Feder","year":"2007","unstructured":"Feder, T., Motwani, R., O\u2019Callaghan, L., Olston, C., Panigrahy, R.: Computing shortest paths with uncertainty. J. Algor. 62(1), 1\u201318 (2007)","journal-title":"J. Algor."},{"issue":"6","key":"9928_CR13","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"RW Floyd","year":"1962","unstructured":"Floyd, R.W.: Algorithm 97: Shortest path. Commun. ACM 5(6), 345 (1962)","journal-title":"Commun. ACM"},{"key":"9928_CR14","unstructured":"Ford, L.R.: Network flow theory. Technical Report Paper P-923, RAND Corporation, Santa Monica, California (1956)"},{"issue":"6","key":"9928_CR15","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/0020-0190(91)90203-T","volume":"40","author":"S Ghosh","year":"1991","unstructured":"Ghosh, S., Mahanti, A.: Bidirectional heuristic search with limited resources. Inf. Process. Lett. 40(6), 335\u2013340 (1991)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9928_CR16","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"Peter Hart","year":"1968","unstructured":"Hart, P. E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. In: IEEE Transactions on Systems Science and Cybernetics, pp. 100\u2013107 (1968)","journal-title":"IEEE Transactions on Systems Science and Cybernetics"},{"key":"9928_CR17","unstructured":"Hoffmann, M., Erlebach, T., Krizanc, D., Mihal\u2019\u00e1k, M., Raman, R.: Computing minimum spanning trees with uncertainty. In: 25th International Symposium on Theoretical Aspects of Computer Science, Leibniz International Proceedings in Informatics (LIPIcs), pp. 277\u2013288. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2008)"},{"issue":"1","key":"9928_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321992.321993","volume":"24","author":"DB Johnson","year":"1977","unstructured":"Johnson, D.B.: Efficient algorithms for shortest paths in sparse networks. J. ACM 24(1), 1\u201313 (1977)","journal-title":"J. ACM"},{"key":"9928_CR19","doi-asserted-by":"crossref","unstructured":"Kahan, S.: A model for data in motion. In: Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, STOC \u201991, pp. 265\u2013277. ACM (1991)","DOI":"10.1145\/103418.103449"},{"issue":"5","key":"9928_CR20","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/j.ipl.2005.11.001","volume":"97","author":"A Kasperski","year":"2006","unstructured":"Kasperski, A., Zieli\u0144ski, P.: An approximation algorithm for interval data minmax regret combinatorial optimization problems. Inf. Process. Lett. 97(5), 177\u2013180 (2006)","journal-title":"Inf. Process. Lett."},{"key":"9928_CR21","doi-asserted-by":"crossref","unstructured":"Khanna, S., Tan, W.-C.: On computing functions with uncertainty. In: Proceedings of the Twentieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS \u201901, pp. 171\u2013182. ACM (2001)","DOI":"10.1145\/375551.375577"},{"key":"9928_CR22","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/978-1-4613-8788-6_7","volume-title":"Search in Artificial Intelligence","author":"Richard E. Korf","year":"1988","unstructured":"Korf, R.E., Kumar, V.: Optimal path-finding algorithms. In: Kanal, L. (ed.) Search in Artificial Intelligence, Symbolic Computation, pp 223\u2013267. Springer, New York (1988)"},{"key":"9928_CR23","unstructured":"Lippi, M., Ernandes, M., Felner, A.: Efficient single frontier bidirectional search. In: Proceeding of the Forth International Symposium on Combinatorial Search (2012)"},{"issue":"1\u20134","key":"9928_CR24","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/BF01553908","volume":"4","author":"M Luby","year":"1989","unstructured":"Luby, M., Ragde, P.: A bidirectional shortest-path algorithm with good average-case behavior. Algorithmica 4(1\u20134), 551\u2013567 (1989)","journal-title":"Algorithmica"},{"key":"9928_CR25","unstructured":"Montemanni, R., Gambardella, L.M.: An algorithm for the relative robust shortest path problem with interval data. Technical Report IDSIA-05-02 Dalle Molle Institute for Artificial Intelligence (2002)"},{"key":"9928_CR26","unstructured":"Olston, C., Widom, J.: Offering a precision-performance tradeoff for aggregation queries over replicated data. In: Proceedings of the 26th International Conference on Very Large Data Bases, VLDB \u201900, pp. 144\u2013155. Morgan Kaufmann Publishers Inc. (2000)"},{"key":"9928_CR27","unstructured":"Karasan, H.Y.O.E., Pinar, M.C.: The robust shortest path problem with interval data. Technical report, Bilkent University, Department of Industrial Engineering (2001)"},{"key":"9928_CR28","doi-asserted-by":"crossref","unstructured":"Pohl, I.: Bi-Directional and Heuristics Search in Path Problems. PhD thesis, Standford University (1969)","DOI":"10.2172\/4785039"},{"key":"9928_CR29","unstructured":"Szepesv\u00e1ri, C.: Shortest path discovery problems: A framework, algorithms and experimental results. In: AAAI, pp. 550\u2013555 (2004)"},{"issue":"1","key":"9928_CR30","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0167-6377(01)00078-5","volume":"29","author":"H Yaman","year":"2001","unstructured":"Yaman, H., Karasan, O.E., Pinar, M.C.: The robust spanning tree problem with interval data. Oper. Res. Lett. 29(1), 31\u201340 (2001)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"9928_CR31","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1109\/JSAC.2016.2525518","volume":"34","author":"Olivier Brun","year":"2016","unstructured":"Brun, O., Wang, L., Gelenbe, E.: Big data for autonomic intercontinental overlays. IEEE J. Selected Areas Commun., 34(3) (2016)","journal-title":"IEEE Journal on Selected Areas in Communications"},{"key":"9928_CR32","doi-asserted-by":"crossref","unstructured":"Feamster, N., Balakrishnan, H., Rexford, J., Shaikh, A, van der Merwe, J.: The case for separating routing from routers. In: Proceedings of the ACM SIGCOMM Workshop on Future Directions in Network Architecture, pp 5\u201312. ACM, Portland (2004)","DOI":"10.1145\/1016707.1016709"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09928-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-019-09928-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09928-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,19]],"date-time":"2020-05-19T23:06:56Z","timestamp":1589929616000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-019-09928-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,21]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["9928"],"URL":"https:\/\/doi.org\/10.1007\/s00224-019-09928-w","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,21]]},"assertion":[{"value":"21 May 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}