Wald, Joseph A.; Colbourn, Charles J. Steiner trees, partial 2-trees, and minimum IFI networks. (English) Zbl 0529.68036 Networks 13, 159-167 (1983). Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 1 ReviewCited in 81 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 05C05 Trees 94C15 Applications of graph theory to circuits and networks 68Q25 Analysis of algorithms and problem complexity Keywords:minimum isolated failure immune networks; linear time algorithm; linear time Steiner tree algorithm; NP-completeness PDF BibTeX XML Cite \textit{J. A. Wald} and \textit{C. J. Colbourn}, Networks 13, 159--167 (1983; Zbl 0529.68036) Full Text: DOI OpenURL References: [1] , and , The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA (1974). [2] and , Graph Theory with Applications. Macmillan, London (1976). · Zbl 1226.05083 [3] Farley, Networks 11 pp 255– (1981) [4] Farley, Discrete Appl. Math. 2 pp 185– (1980) [5] and , Extremal graphs with no disconnecting independent vertex set or matching. University of Oregon Computer and Information Science, Technical Report CIS-TR-80–21 (1980). [6] Garey, SIAM J. Appl. Math. 32 pp 826– (1977) [7] Garey, Theor. Comput. Sci. 1 pp 237– (1976) [8] Hakimi, Networks 1 pp 113– (1972) [9] Hakimi, Networks 3 pp 241– (1973) [10] Graph Theory. Addison-Wesley, Reading, MA (1969). [11] Reducibility among combinatorial problems. In Complexity of Computer Computations. and , Eds. Plenum, New New York 1972, pp. 85–104. [12] and , The subgraph homeomorphism problem. In Proceedings, Tenth ACM Symposium on the Theory of Computing, 1978, pp. 40–50. · Zbl 1282.68183 [13] and , Graph reducibility. In Proceedings, Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing, 1976, pp. 433–455. [14] and , An O(max (m, n)) algorithm for finding a subgraph homeomorphic to K4. Proceeding Eleventh Southeastern Conference on Combinatorics, Graph Theory, and Computing, 1980, pp. 597–609. [15] Rose, Discrete Math. 7 pp 317– (1974) · Zbl 0285.05128 [16] Tarjan, SIAM J. Comput. 1 pp 146– (1972) [17] and , Steiner trees in outerplanar graphs. In Proceedings, Thirteenth Southeastern Conference on Combinatorics, Graph Theory, and Computing, 1982, pp. 15–22. This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.