×

zbMATH — the first resource for mathematics

Steiner trees, partial 2-trees, and minimum IFI networks. (English) Zbl 0529.68036

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
PDF BibTeX XML Cite
Full Text: DOI
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 · doi:10.1007/978-1-349-03521-2
[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. · doi:10.1007/978-1-4684-2001-2_9
[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 · doi:10.1016/0012-365X(74)90042-9
[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.