{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:39:31Z","timestamp":1760236771332,"version":"build-2065373602"},"reference-count":17,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2021,12,17]],"date-time":"2021-12-17T00:00:00Z","timestamp":1639699200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In a previous paper by the author, a pathfinding problem for directed trees is studied under the following situation: each edge has a nonnegative integer length, but the length is unknown in advance and should be found by a procedure whose computational cost becomes exponentially larger as the length increases. In this paper, the same problem is studied for a more general class of graphs called fork-join directed acyclic graphs. The problem for the new class of graphs contains the previous one. In addition, the optimality criterion used in this paper is stronger than that in the previous paper and is more appropriate for real applications.<\/jats:p>","DOI":"10.3390\/a14120367","type":"journal-article","created":{"date-parts":[[2021,12,19]],"date-time":"2021-12-19T20:41:55Z","timestamp":1639946515000},"page":"367","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Pathfinding Problem for Fork-Join Directed Acyclic Graphs with Unknown Edge Length"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1750-1891","authenticated-orcid":false,"given":"Kunihiko","family":"Hiraishi","sequence":"first","affiliation":[{"name":"School of Information Science, Japan Advanced Institute of Science and Technology, 1-1 Asahiday, Nomi 923-1292, Ishikawa, Japan"}]}],"member":"1968","published-online":{"date-parts":[[2021,12,17]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jda.2018.04.002","article-title":"A Pathfinding Problem for Search Trees with Unknown Edge Length","volume":"49","author":"Hiraishi","year":"2018","journal-title":"J. Discret. Algorithms"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Kikuchi, S., and Tsuchiya, S. (2010, January 22\u201326). Configuration Procedure Synthesis for Complex Systems Using Model Finder. Proceedings of the 15th IEEE International Conference on Engineering of Complex Computer Systems (ICECCS 2010), Oxford, UK.","DOI":"10.1109\/ICECCS.2010.17"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1696","DOI":"10.1587\/transinf.E96.D.1696","article-title":"Synthesis of Configuration Change Procedure Using Model Finder","volume":"E-96-D","author":"Kikuchi","year":"2013","journal-title":"IEICE Trans. Inf. Syst."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A Formal Basis for the Heuristic Determination of Minimum Cost Paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0004-3702(85)90084-0","article-title":"Depth-first Iterative-Deepening: An Optimal Admissible Tree Search","volume":"27","author":"Korf","year":"1985","journal-title":"Artif. Intell."},{"key":"ref_6","unstructured":"Bj\u00f6rnsson, Y., Enzenberger, M., Holte, R.C., and Schaeffer, J. (2005, January 4\u20136). Fringe Search: Beating A* at Pathfinding on Game Maps. Proceedings of the 2005 IEEE Symposium on Computational Intelligence and Games, Colchester, Essex, UK."},{"key":"ref_7","unstructured":"Russell, S. (1992, January 3\u20137). Efficient Memory-bounded Search Methods. Proceedings of the 10th European Conference on Artificial Intelligence, Vienna, Austria."},{"key":"ref_8","first-page":"552","article-title":"Stochastic Shortest Paths via Quasi-convex Maximization","volume":"4168","author":"Nikolova","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1007\/BFb0035787","article-title":"Shortest Paths Without a Map","volume":"Volume 372","author":"Papadimitriou","year":"1989","journal-title":"Lecture Notes in Computer Science"},{"key":"ref_10","unstructured":"Karger, D., and Nikolova, E. (2008). Exact Algorithms for the Canadian Traveler Problem on Paths and Trees, MIT. MIT-CSAIL-TR-2008-004."},{"key":"ref_11","first-page":"2369","article-title":"The On-Line Shortest Path Problem Under Partial Monitoring","volume":"8","author":"Linder","year":"2007","journal-title":"J. Mach. Learn. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1016\/j.trb.2019.04.009","article-title":"An Online Shortest Path Algorithm for Reliable Routing in Schedule-based Transit Networks Considering Transfer Failure Probability","volume":"126","author":"Khani","year":"2019","journal-title":"Transp. Res. Part B"},{"key":"ref_13","unstructured":"Blei, D., and Kaelbling, L. (August, January 31). Shortest Paths in a Dynamic Uncertain Domain. Proceedings of the IJCAI Workshop on Adaptive Spatial Representations of Dynamic Environments, Stockholm, Sweden."},{"key":"ref_14","unstructured":"Boyan, J., and Mitzenmacher, M. (2001, January 7\u20139). Improved Results for Route Planning in Stochastic Transportation Networks. Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, Washington, DC, USA."},{"key":"ref_15","unstructured":"Nikolova, E., Brand, M., and Karger, D.R. (2006, January 6\u201310). Optimal Route Planning Under Uncertainty. Proceedings of the International Conference on Automated Planning and Scheduling, Cumbria, UK."},{"key":"ref_16","unstructured":"Karp, R.M. (1992, January 7\u201311). On-Line Algorithms Versus Off-Line Algorithms: How Much is it Worth to Know the Future?. Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture-Information Processing \u201992, Madrid, Spain."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1145\/65950.65957","article-title":"Acyclic Fork-join Queuing Networks","volume":"36","author":"Baccelli","year":"1989","journal-title":"J. ACM"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/12\/367\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:50:51Z","timestamp":1760169051000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/12\/367"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,17]]},"references-count":17,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2021,12]]}},"alternative-id":["a14120367"],"URL":"https:\/\/doi.org\/10.3390\/a14120367","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,12,17]]}}}