{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T06:12:02Z","timestamp":1751609522064},"reference-count":12,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":7802,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1985,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given a directed graph <jats:italic>G<\/jats:italic>(\ud835\udccb,\ud835\udcb6), the problem of finding a minimum cardinality subset <jats:styled-content>\u03c5<\/jats:styled-content> \u2286 \ud835\udcb6 such that the subgraph, <jats:italic>G<\/jats:italic>(\ud835\udccb,\ud835\udcb6), preserves the reachability properties of <jats:italic>G<\/jats:italic>(\ud835\udccb,\ud835\udcb6) is well known to be difficult. In this article, we consider a generalization which seeks a minimum weight subset <jats:styled-content>\u03c5<\/jats:styled-content> satisfying the stated conditions where the weights of arcs in \ud835\udcb6 are assigned arbitrary integer values. A polynomial\u2010time algorithm is given for the case where the underlying, undirected graph is series\u2010parallel. Naturally, the stated algorithm subsumes the cardinality case on such graphs as well.<\/jats:p>","DOI":"10.1002\/net.3230150207","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T19:20:53Z","timestamp":1178911253000},"page":"217-228","source":"Crossref","is-referenced-by-count":16,"title":["An efficiently solvable case of the minimum weight equivalent subgraph problem"],"prefix":"10.1002","volume":"15","author":[{"given":"M. B.","family":"Richey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R. Gary","family":"Parker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R. L.","family":"Rardin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-27.1.85"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(65)90125-3"},{"key":"e_1_2_1_4_2","first-page":"89","article-title":"An algorithm for finding a minimum equivalent graph of a digraph","volume":"12","author":"Hsu H. T.","year":"1975","journal-title":"Networks"},{"key":"e_1_2_1_5_2","unstructured":"P. C.Liu andR. C.Geldmacher An 0(max(m n)) algorithm for finding a subgraph homeomorphic toK4. Proc. 11th Southeastern Conf. on Combinatorics Graph Theory and Computing (1980)597\u2013609."},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120202"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/321526.321534"},{"key":"e_1_2_1_8_2","unstructured":"R. L.Rardin R. G.ParkerandM. B.Richey A polynomial algorithm for a class of Steiner tree problems on graphs ISyE Report Series J\u201082\u20105 Georgia Tech August."},{"key":"e_1_2_1_9_2","unstructured":"R. L.Rardin R. G.ParkerandD. K.Wagner Definitions properties and algorithms for detecting series\u2010parallel graphs Technical Report Department of Industrial Engineering Purdue University W. Lafayete IN (1982)."},{"key":"e_1_2_1_10_2","unstructured":"M. B.Richey R. G.ParkerandR. L.Rardin On a class of graphs possessing at most one hamiltonian cycle. ISyE Report Series J\u201082\u201011 Georgia Tech. November."},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/0203021"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322328"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130202"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230150207","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230150207","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T21:23:01Z","timestamp":1697836981000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230150207"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,6]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1985,6]]}},"alternative-id":["10.1002\/net.3230150207"],"URL":"https:\/\/doi.org\/10.1002\/net.3230150207","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,6]]}}}