{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T05:47:56Z","timestamp":1771307276903,"version":"3.50.1"},"reference-count":17,"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":8533,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1983,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Minimum isolated failure immune networks are shown to be 2\u2013trees. Further, subgraphs of 2\u2010trees are shown to be exactly those graphs which contain no subgraph homeomorphic to the four\u2010vertex complete graph. Together, these two characterizations yield a linear time algorithm for adding lines to a network to produce a minimum isolated failure immune network, whenever this is possible. This same algorithm, in conjunction with a linear time Steiner tree algorithm for 2\u2010tress, yields a linear time Steiner tree algorithm for partial 2\u2010tress. This contrasts with the known NP\u2010completeness of the Steiner tree problem for planar graphs.<\/jats:p>","DOI":"10.1002\/net.3230130202","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T14:59:22Z","timestamp":1178895562000},"page":"159-167","source":"Crossref","is-referenced-by-count":168,"title":["Steiner trees, partial 2\u2013trees, and minimum IFI networks"],"prefix":"10.1002","volume":"13","author":[{"given":"Joseph A.","family":"Wald","sequence":"first","affiliation":[]},{"given":"Charles J.","family":"Colbourn","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho A. V.","year":"1974"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-349-03521-2"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110304"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(80)90039-6"},{"key":"e_1_2_1_6_2","unstructured":"A. M.FarleyandA.Proskurowski Extremal graphs with no disconnecting independent vertex set or matching. University of Oregon Computer and Information Science Technical Report CIS\u2010TR\u201080\u201321 (1980)."},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/0132071"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010203"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230030304"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.21236\/AD0705364"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","unstructured":"A.LaPaughandR. L.Rivest The subgraph homeomorphism problem. InProceedings Tenth ACM Symposium on the Theory of Computing 1978 pp.40\u201350.","DOI":"10.1145\/800133.804330"},{"key":"e_1_2_1_14_2","unstructured":"P. C.LiuandR. C.Geldmacher Graph reducibility. InProceedings Seventh Southeastern Conference on Combinatorics Graph Theory and Computing 1976 pp.433\u2013455."},{"key":"e_1_2_1_15_2","unstructured":"P. C.LiuandR. C.Geldmacher AnO(max (m n)) algorithm for finding a subgraph homeomorphic to K4.Proceeding Eleventh Southeastern Conference on Combinatorics Graph Theory and Computing 1980 pp.597\u2013609."},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90042-9"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_1_18_2","unstructured":"J. A.WaldandC. J.Colbourn Steiner trees in outerplanar graphs. InProceedings Thirteenth Southeastern Conference on Combinatorics Graph Theory and Computing 1982 pp.15\u201322."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230130202","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230130202","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T09:16:26Z","timestamp":1697793386000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230130202"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,6]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1983,6]]}},"alternative-id":["10.1002\/net.3230130202"],"URL":"https:\/\/doi.org\/10.1002\/net.3230130202","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1983,6]]}}}