{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T23:38:11Z","timestamp":1761176291494,"version":"build-2065373602"},"reference-count":0,"publisher":"IOS Press","isbn-type":[{"value":"9781643686318","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,10,21]],"date-time":"2025-10-21T00:00:00Z","timestamp":1761004800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,10,21]]},"abstract":"<jats:p>We study the problem of inferring all possible sources and targets of shortest walks in a weighted directed graph, constrained by a set of observed edges. We present two efficient polynomial-time algorithms to solve this problem. The first algorithm applies to graphs with strictly positive edge weights, while the second, a more complex algorithm, handles graphs with non-negative weight cycles, the broadest class of graphs where shortest walks exist. We demonstrate the effectiveness of the first algorithm by evaluating it on real-world road networks, achieving consistent performance on graphs with up to 7.7 million nodes and over 16 million edges. Our results show that the proposed approach scales efficiently and robustly across large networks.<\/jats:p>","DOI":"10.3233\/faia251389","type":"book-chapter","created":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T10:00:15Z","timestamp":1761127215000},"source":"Crossref","is-referenced-by-count":0,"title":["Efficient Inference of Sources and Targets in a Graph with Limited Observations"],"prefix":"10.3233","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0216-3762","authenticated-orcid":false,"given":"Wanrong","family":"Yang","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Liverpool"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5560-0546","authenticated-orcid":false,"given":"Dominik","family":"Wojtczak","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Liverpool"}]}],"member":"7437","container-title":["Frontiers in Artificial Intelligence and Applications","ECAI 2025"],"original-title":[],"link":[{"URL":"https:\/\/ebooks.iospress.nl\/pdf\/doi\/10.3233\/FAIA251389","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T10:00:15Z","timestamp":1761127215000},"score":1,"resource":{"primary":{"URL":"https:\/\/ebooks.iospress.nl\/doi\/10.3233\/FAIA251389"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,21]]},"ISBN":["9781643686318"],"references-count":0,"URL":"https:\/\/doi.org\/10.3233\/faia251389","relation":{},"ISSN":["0922-6389","1879-8314"],"issn-type":[{"value":"0922-6389","type":"print"},{"value":"1879-8314","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,21]]}}}