{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T00:07:45Z","timestamp":1699834065425},"reference-count":15,"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":11971,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1974,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The concept of an alternating path has been very useful in analyzing matching problems and has formed the basis for a number of matching algorithms. However, no techniques have been devised to find the shortest alternating path in a weighted graph. This paper defines different types of directed and undirected alternating paths, and shows how the problem of finding the shortest directed alternating path can be transformed into a problem of finding the shortest path in a directed graph. Utilizing this transformation, an efficient algorithm is developed for finding the shortest undirected alternating path. Computational experience is given. Extensions of the techniques in this paper to other types of alternating paths are discussed.<\/jats:p>","DOI":"10.1002\/net.3230040404","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T02:17:33Z","timestamp":1178849853000},"page":"311-334","source":"Crossref","is-referenced-by-count":4,"title":["Shortest alternating path algorithms"],"prefix":"10.1002","volume":"4","author":[{"given":"J. R.","family":"Brown","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Combinatorial Mathematics and Its Applications, Proc. of the Conference held at the University of North Carolina at Chapel Hill, April 10\u201314, 1967","author":"Balinski M. L.","year":"1969"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.43.9.842"},{"key":"e_1_2_1_4_2","volume-title":"The Theory of Graphs and Its Applications","author":"Berge C.","year":"1962"},{"key":"e_1_2_1_5_2","unstructured":"Brown J. R. \u201cComputational Experience of the Shortest Undirected Alternating Path Algorithm \u201dCenter for Business and Economic Research Working Paper Kent State University 1973."},{"key":"e_1_2_1_6_2","unstructured":"Desler J. F. \u201cDegree Constrained Subgraphs Covers Codes and K\u2010graphs \u201d unpublished Ph.D. Dissertation Northwestern University 1969."},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.17.6.1017"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.17.3.395"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1962-10791-5"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","unstructured":"Edmonds J. \u201cPaths Trees and Flowers \u201dCanadian Journal of Mathematics 1965 pp.449\u2013467.","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.013"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/367766.368168"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1515\/9781400875184"},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"Ore O. Theory of Graphs American Mathematical Society Colloquium Publication Providence Rhode Island 1962.","DOI":"10.1090\/coll\/038"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392606"},{"key":"e_1_2_1_16_2","unstructured":"Urquhart R. J. \u201cDegree Constrained Subgraphs of Linear Graphs \u201d unpublished Ph.D. Dissertation University of Michigan 1967."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230040404","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230040404","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T14:07:55Z","timestamp":1699798075000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230040404"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1974,1]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1974,1]]}},"alternative-id":["10.1002\/net.3230040404"],"URL":"https:\/\/doi.org\/10.1002\/net.3230040404","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1974,1]]}}}