{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T00:07:40Z","timestamp":1699834060809},"reference-count":21,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":10176,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1978,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A new algorithm for updating shortest paths from all vertices to a set of vertices following a decreasing\u2010length\u2010modification of some arcs, is presented. The algorithm is based on a formula which has an algebraic analogy with the well\u2010known Householder formula for inverting modified matrices. The number of operations (i.e., additions and comparisons) required for solving the modified shortest path problem is estimated as 0(mn<jats:sup>2<\/jats:sup>), where n is the overall number of vertices and m is a parameter related to the arcs which have been updated. The algorithm proposed here is particularly powerful for solving large\u2010scale networks with sparse structure.<\/jats:p>","DOI":"10.1002\/net.3230080406","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T09:19:35Z","timestamp":1178875175000},"page":"341-372","source":"Crossref","is-referenced-by-count":18,"title":["A new shortest path updating algorithm"],"prefix":"10.1002","volume":"8","author":[{"given":"S.","family":"Goto","sequence":"first","affiliation":[]},{"given":"A.","family":"Sangiovanni\u2010Vincentelli","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.17.3.395"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1090\/qam\/102435"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1093\/imamat\/7.3.273"},{"key":"e_1_2_1_6_2","series-title":"RAAG Research Notes, Third Series, No. 185","volume-title":"Path Sets, Operator Semi\u2010Groups and Shortest Path Algorithms on a Network","author":"Iri M.","year":"1972"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCS.1976.1084155"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/0204032"},{"key":"e_1_2_1_9_2","unstructured":"Hsieh W. A.KershenbaumandB.Golden \u201cConstrained Routing in Large Sparse Networks \u201dProc. of IEEE International Conference on Communications Philadelphia Pennsylvania 1976 pp.38.14\u201338.18."},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(68)90148-1"},{"key":"e_1_2_1_11_2","unstructured":"Murchland J. \u201cThe Effect of Increasing or Decreasing the Length of a Single Arc on All Shortest Distances in a Graph \u201d Report LBS\u2010TNT\u201026 London Graduate School of Business Studies September1967."},{"key":"e_1_2_1_12_2","first-page":"96","article-title":"A Network Evaluation Procedure","volume":"205","author":"Loubal P.","year":"1967","journal-title":"Highway Research Record"},{"key":"e_1_2_1_13_2","first-page":"79","volume-title":"Principles of Numerical Analysis","author":"Householder A. S.","year":"1953"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCS.1976.1084171"},{"key":"e_1_2_1_15_2","volume-title":"Shortest Path Tree Updating Procedures","author":"Hsieh W.","year":"1975"},{"key":"e_1_2_1_16_2","volume-title":"Sparse Matrices","author":"Tewarson R. P.","year":"1973"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01436076"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1972.1083550"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/321556.321565"},{"key":"e_1_2_1_21_2","volume-title":"Theorie der Endlichen und Unendilichen Graphen","author":"K\u00f6nig D.","year":"1936"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.1975.5.1.45"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230080406","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230080406","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T08:37:55Z","timestamp":1699778275000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230080406"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1978,12]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1978,12]]}},"alternative-id":["10.1002\/net.3230080406"],"URL":"https:\/\/doi.org\/10.1002\/net.3230080406","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1978,12]]}}}