{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,27]],"date-time":"2022-04-27T09:12:21Z","timestamp":1651050741266},"reference-count":0,"publisher":"Walter de Gruyter GmbH","issue":"4","license":[{"start":{"date-parts":[[2013,12,1]],"date-time":"2013-12-01T00:00:00Z","timestamp":1385856000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013,12,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Bipartite graphs are widely used for modeling of complex structures in biology, engineering, and computer science. The search for shortest paths in such structures is a highly demanded procedure that requires optimization. This paper presents a variant of the all-pairs shortest path algorithm for bipartite graphs. The method is based on the distance matrix product and improves the general algorithm by exploiting the graph topology. The space complexity is reduced by a factor of at least four and the time complexity decreased by almost an order of magnitude when compared with the basic APSP algorithm.<\/jats:p>","DOI":"10.2478\/s13537-013-0110-4","type":"journal-article","created":{"date-parts":[[2013,12,27]],"date-time":"2013-12-27T00:51:45Z","timestamp":1388105505000},"page":"149-157","source":"Crossref","is-referenced-by-count":1,"title":["An all-pairs shortest path algorithm for bipartite graphs"],"prefix":"10.2478","volume":"3","author":[{"given":"Svetlana","family":"Torgasin","sequence":"first","affiliation":[{"name":"Hamburg University of Technology, 21071, Hamburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karl-Heinz","family":"Zimmermann","sequence":"additional","affiliation":[{"name":"Hamburg University of Technology, 21071, Hamburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2013,12,28]]},"container-title":["Open Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.2478\/s13537-013-0110-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.2478\/s13537-013-0110-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.2478\/s13537-013-0110-4\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.2478\/s13537-013-0110-4\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,27]],"date-time":"2022-04-27T08:44:26Z","timestamp":1651049066000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.2478\/s13537-013-0110-4\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12,1]]},"references-count":0,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2013,12,28]]},"published-print":{"date-parts":[[2013,12,1]]}},"alternative-id":["10.2478\/s13537-013-0110-4"],"URL":"https:\/\/doi.org\/10.2478\/s13537-013-0110-4","relation":{},"ISSN":["2299-1093"],"issn-type":[{"value":"2299-1093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12,1]]}}}