ЛИТЕРАТУРА

1.1. Whitney Н., 2-Isomorphic Graphs., Am. J. Math., 55, 245—254 (1933).

1.2. Berge C., Graphs and Hypergraphs, North Holland, Amsterdam, 1973.

1.3. Harary F. Graph Theory, Addison-Wesley, Reading, Mass., 1969. [Имеется перевод: Ф. Харари. Теория графов: — М.: Мир, 1973.]

1.4. J. A. Bondy, U.S.R. Murty, Graph Theory with Applications, Macmillan, London, 1976.

1.5. R. J. Wilson, Introduction to Graph Theory, Oliver and Boyed, Edinburgh, 1972. [Имеется перевод: P. Уилсон. Введение в теорию графов.— М.: Мир, 1977.]

1.6. С. L. Liu, Introduction to Combinatorial Mathematics, McGraw-Hill, New York, 1968.

1.7. M. Behzad, G. Chartrand, Introduction to the Theory of Graphs, Allyn and Bacon, Boston, 1971.

1.8. N. Deo, Graph Theory with Applications to Engineering and Computer Science, Prentice-Hall, Englewood Cliffs, N.J., 1974.

2.1. S. Seshu, М. B. Reed, Linear Graphs and Electrical Networks, Addison-Wesley, Reading, Mass., 1961.

2.2. М. B. Reed. The Seg: A New Class of Subgraphs, IRE Trans. Circuit Theory, Vol. CT-8, 17—22 (1961).

2.3. W. H. Kim, R. T. Chien, Topological Analysis and Synthesis of Communication Networks, Colombia University Press, New York, 1962.

2.4. W. K- Chen, Applied Graph Theory: Graphs and Electrical Networks, North-Holland, Amsterdam, 1971.

2.5. W. Mayeda, Graph Theory, Wiley-Interscience, New York, 1972.

2.6. H. Whitney, On the Abstract Properties of Linear Dependence, Am. J. Math., Vol. 57, 509—533 (1935).

2.7. C. St. J. A. Nash-Williams, Edge-Disjoint Spanning Trees of Finite Graphs, J. London Math. Soc., Vol. 36, 445—450 (1961).

2.8. W. T. Tutte, On the Problem of Decomposing a Graph into n Connected Factors, J. London Math. Soc., Vol. 36, 221—230 (1961).

2.9. R. L. Cummins, Hamilton Circuits in Tree Graphs, IEEE Trans. Circuit Theory, Vol. CT-13, 82-90 (1966).

3.1. V. Chvatal, On Hamilton’s Ideals, J. Combinatorial Theory B, Vol. 12, 163—168 (1972).

3.2. G. A. Dirac, Some Theorems on Abstract Graphs, Proc. London Math. Soc., Vol. 2, 69—81 (1952).

3.3. O. Ore, Arc Coverings of Graphs, Ann. Mat. Рига Appl., Vol. 55, 315—321 (1961).

3.4. L. Posa, A Theorem Concerning Hamilton Lines, Magyar Tud. Akad. Mat. Kutato Int. Kozl., Vol. 7, 225—226 (1962).

3.5. J. A. Bondy, Properties of Graphs with Constraints on Degrees, Studia Sci. Math. Hungar., Vol. 4 , 473—475 (1969).

3.6. C. L. Liu, Introduction to Combinatorial Mathematics, McGraw-Hill, New York, 1968.

3.7. M. Behzad and G. Chartrand, Introduction to the Theory of Graphs, AHyn and Bacon, Boston, 1971.

3.8. S. Lin, Computer Solutions of the Traveling Salesman Problem, Bell Syst. Tech. J., Vol. 44, 2245—2269 (1965).

3.9. M. Belmore and G. L. Nemhauser, The Traveling Salesman Problem: A Survey, Operations Res., Vol. 16, 538—558 (1968).

3.10. M. Held and R. M. Karp, The Traveling Salesman Problem and Minimum Spanning Trees, Operations Res., Vol. 18, 1138—1162 (1970).

3.11. M. Held and R. M. Karp, The Traveling Salesman Problem and Minimum Spanning Trees: Part II, Math. Programming, Vol. 1, 6—25 (1971).

3.12. C. Berge, Graphs and Hypergraphs, North Holland, Amsterdam, 1973.

3.13. J. A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan, London, 1976, chap. 4.

3.14. C. St. J. A. Nash-Williams, Hamilton Arcs and Circuits, in Recent Trends in Graph Theory, Springer, Berlin, 1971, pp. 197—210.

3.15. J. A. Bondy and V. Chvatal, A Method in Graph Theorv, Discrete Math., Vol. 15, 111—135 (1976).

3.16. C. St. J. A. Nash-Williams, Hamiltonian Circuits, in Studies in Graph Theory, Part. II, MAA Press, 1975, pp. 301—360.

3.17. L. Lesniak-Foster, Some Recent Results in Hamiltonian Graphs, J. Graph Theory, Vol. 1, 27—36 (1977).

3.18. P. Erdos and T. Gallai, On Maximal Paths and Circuits of Graphs, Acta Math. Acad. Sci. Hung., Vol. 10, 337—356 (1959).

3.19. R. L. Cummins, Hamilton Circuits in Tree Graphs, IEEE Trans. Circuit Theory, Vol. CT-13, 82—90 (1966).

3.20. H. Shank, A Note on Hamilton Circuits in Tree Graphs, IEEE Trans. Circuit Theory, Vol. CT-15, 86 (1968).

4.1. S. MacLane and G. Birkhoff, Algebra, Macmillan, New York, 1967.

4.2. P. R. Halmos, Finite—Dimensional Vector Spaces, Van Nostrand Reinhold, New York, 1958.

4.3. F. E. Hohn, Elementary Matrix Algebra, Macmillan, New York, 1958.

4.4. W. K- Chen, On Vector Spaces Associated with a Graph, SIAM J. Appl. Math., Vol., 20, 526—529 (1971).

4.5. T. W. Williams and L. M. Maxwell, The Decomposition of a Graph and the Introduction of a New Class of Subgraphs, SIAM J. Appl. Math., Vol. 20, 385—389 (1971).

4.6. R. Gould, Graphs and Vectors Spaces, J. Math. Phys., Vol. 37, 193—214 (1958).

5.1. S. W. Golomb, Shift Register Sequences, Holden-Day, San Francisco, 1967.

5.2. M. Hall, Jr., Combinarotial Theory, Blaisdell, Waltham, Mass., 1967.

5.3. T. Van Aardenne-Ehrenfest and N. G. de Bruijn, Circuits and Trees in Oriented Linear Graphs, Simon Stevin, Vol. 28, 203—217 (1951).

5.4. J. W. Moon, On Subtournaments of a Tournament, Canad. Math. Bull., Vol. 9, 297—301 (1966).

5.5. C. Berge, Graphs and Hypergraphs, North Holland, Amsterdam, 1973.

5.6. J. A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan, London, 1976.

5.7. M. G. Kendall, Further Contributions to the Theory of Paired Comparisons, Biometrics, Vol. 11, 43—62 (1955).

5.8. J. W. Moon and N. J. Pullman, On Generalized Tournament Matrices. SIAM Rev., Vol. 12, 384—389 (1970).

5.9. Ф. Харари Теория графов.—М.: Мир, 1973.

5.10. J. W. Moon, Topics on Tournaments, Holt, Rinehart and Winston, New York, 1968.

5.11. C. St. J. A. Nash-Williams, Hamiltonian Circuits, in Studies in Graph Theory, Part II, MAA Press, 1975, pp. 301—360.

5.12. D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Addison-Wesley, Reading Mass, 1968.

5.13. D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, Reading, Mass., 1973. [Имеется перевод: Д. E. Кнут. Искусство программирования для ЭВМ. т. 3: Сортировка и поиск:— М.: Мир, 1978.]

5.14. А. V. Aho, J. Е. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974. [Имеется перевод: A. Axo, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов.— М.: Мир, 1979.]

5.15. Е. М. Reingold, J. Nievergelt, and N. Deo, Combinatorial Algorithms: Theory and Practice, Prentice Hall, Englewood Cliffs, N.J., 1977. [Имеется перевод: Э. М. Рейнгольд, Ю. Нивергельт, Н. Дсо. Комбинаторные алгоритмы: Теория и практика: — М.: Мир, 1980.]

5.16. F. Нагагу, R. Z. Norman, and D. Cartwright, Structural Models: An Intro-duction to the Theory of Directed Graphs, Wiley, New York, 1965.

5.17. V. Chvatal and L. Lovasz, Every Directed Graph Has a Semi-Kernel, in Hypergraph Seminar (Eds. C. Berge and D. K- Ray-Chaudhuri), Springer, New York, 1974, p. 175.

6.1. F. E. Hohn, Elementary Matrix Algebra, Macmillan, New York, 1958.

6.2. W. K- Chen, Applied Graph Theory, North Holland, Amsterdam, 1971.

6.3. G. Kirchhoff, Uber die Auflosung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Strome geftihrt wird, Ann. Phys. Chem., Vol. 72, 497—508 (1947).

6.4. A. Cayley, A Theorem on Trees, Quart. J. Math., Vol. 23, 376—378 (1889).

6.5. J. W. Moon, Various Proofs of Cayley’s Formula for Counting Trees, in A Seminar on Graph Theory (Ed. F. Harary and L. W. Beinke), Holt, Rinehart and Winston, New York, 1967, pp. 70—78.

6.6. H. Priifer, Neuer Beweis eines Satzes fiber Permutationen, Arch. Math. Phys., Vol. 27, 742—744 (1918).

6.7. K- Sankara Rao, V. V. Bapeswara Rao, and V. G. K- Murti, Two—Three Admittance Products, Electron. Lett., Vol. 6, 834—835 (1970).

6.8. W. T. Tutte, The Dissection of Equilateral Triangles into Equilateral Triangles, Proc. Cambridge Phil. Soc., Vol. 44, 203—217 (1948).

6.9. F. Harary, The Determinant of the Adjacency Matrix of a Graph, SIAM Rev., Vol. 4, 202—210 (1962).

6.10. C. L. Coates. Flow-Graph Solutions of Linear Algebraic Equations IRE Trans., Circuit Theory, Vol. CT-6, 170—187 (1959).

6.11. S. J. Mason, Feedback Theory: Some Properties of Signal Flow Graphs, Proc. IRE., Vol. 41, 1144—1156 (1953).

6.12. S. J. Mason, Feedback Theory: Further Properties of Signal Flow Graphs,

Proc. IRE., Vol. 44, 920—926 (1956).

6.13. S. Seshu, М. B. Reed, Linear Graphs and Electrical Networks, Addison-Wesley, Reading, Mass., 1961.

6.14. W. Mayeda, Graph Theory, Wiley-Interscience, New York, 1972.

6.15. N. Deo. Graph Theory with Applications to Engineering and Computer Science, Prentice-Hall, Englewood Cliffs, N.J., 1974.

6.16. F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, New York, 1973. [Имеется перевод: Ф. Харари, Е. Палмер. Перечисление графов: —М.: Мир, 1977.]

6.17. В. R. Myers, Number of Trees in a Cascade of 2-Port Networks, IEEE Trans. Circuit Theory, Vol CT-14, 284—290 (1967).

6.18. B. R. Myers, Number of Spanning Trees in a Wheel, IEEE Trans. Circuit Theory, Vol. CT-18, 280—282 (1971).

6.19. S. D. Bedrosian, Number of Spanning Trees in Multigraph Wheels, IEEE Trans. Circuit Theory, Vol. CT-19, 77—78 (1972).

6.20. N. K- Bose, R. Feick, and F. K- Sun, Genera! Solution to the Spanning Tret

Enumeration Problem in Multigraph Wheels, IEEE Trans. Circuit Theory, Vol. CT-20, 69—70 (1973).

6.21. M.N.S. Swamy and K- Thulasiraman, A Theorem in the Theory of Determinants and the Number of Spanning Trees of a Graph, Proc. IEEE Int. Symp. on Circuits and Systems, 153—156 (1976).

6.22. C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973.

6.23. L.P.A. Robichaud, M. Boisvert, and J. Robert, Signal Flow Graphs and Applications, Prentice-Hall, Englewood Cliffs, N.J., 1962.

6.24. N. Balabanian and T. A. Bickart, Electrical Network Theory, Wiley, New York, 1969.

6.25. Y. Kajitani and S. Ueno, On the Rank of Certain Classes of Cutsets and Tie-Sets of a Graph, IEEE Trans. Circuits and Sys., Vol. CAS-26, 666—668 (1979).

7.1. K- Wagner, Bemerkungen zum Vierfarbenproblem, Ober Deutsh. Math. Verein, Vol. 46, 26—32 (1936).

7.2. I. Fary, On Straight Line Representation of Planar Graphs, Acta Sci. Math. Szeged, Vol. 11, 229—233 (1948).

7.3. S. K- Stein, Convex Maps, Proc. Am. Math. Soc., Vol. 2, 464—466 (1951).

7.4. H. Whitney, Non-Separable and Planar Graphs, Trans. Am. Math. Soc., Vol. 34 , 339—362 (1932).

7.5. C. Kuratowski, Sur le probleme des courbes gauches en topologie, Fund. Math., Vol. 15, 271—283 (1930).

7.6. Cm. [1.3].

7.7. W. T. Tutte, How to Draw a Graph, Proc. London Math. Soc., Vol. 13, 743—767 (1963).

7.8. K- Wagner, Uber eine Eigenschaft der ebenen Komplexe, Math. Ann., Vol. 114, 570—590 (1937).

7.9. F. Harary and W. T. Tutte, A Dual Form of Kuratowski’s Theorem, Canad. Math. Bull., Vol. 8, 17—20 (1965).

7.10. S. MacLane, A Structural Characterization of Planar Combinatorial Graphs, Duke Math. J., Vol. 3, 340—372 (1937).

7.11. H. Whitney, Planar Graphs, Fund. Math., Vol. 21, 73—84 (1933).

7.12. T. D. Parsons, On Planar Graphs, Am. Math. Monthly, Vol. 78, 176—178 (1971).

7.13. S. Seshu, М. B. Reed, Linear Graphs and Electrical Networks, Addison-Wesley, Reading, Mass., 1961.

7.14. H. Whitney A Set of Topological Invariants for Graphs, Am. J. Math., Vol. 55, 231—235 (1933).

7.15. O. Ore, The Four Colour Problem, Academic Press, New York, 1967.

7.16. J. A. Bondy and U.S.R. Murty, Graph Theory with Applications Macmillan, London, 1976.

7.17. J. E. Hopcroft and R. E. Tarjan, Efficient Planarity Testing, J. ACM, Vol. 21, 549—568 (1974).

7.18. N. K. Bose and K- A. Prabhu, Thickness of Graphs with Degree Constrained Vertices, IEEE Trans. Circuits and Sys., Vol. CAS—24, 184—190 (1975).

7.19. W. T. Tutte, On the Nonbiplanar Character of the Complete 9-graph, Canad. Math. Bull., Vol. 6, 319—330 (1963).

8.1. F. Harary The Maximum Connectivity of a Graph, Proc. Nat. Acad. Sci., U.S., Vol. 48, 1142—1146 (1962).

8.2. J. A. Bondy, Properties of Graphs with Constraints on Degrees, Studia Sci, Math. Hung., Vol. 4, 473—475 (1969).

8.3. G. Chartrand, A Graph Theoretic Approach to a Communication Problem, SIAM J. Appl. Math., Vol. 14, 778—781 (1966).

8.4. S. L. Hakimi, On the Realizability of a Set of Integers as Degrees of the Vertices of a Graph, SIAM J. Appl. Math., Vol. 10, 496—506 (1962).

8.5. V. Havel, A Remark on the Existence of Finite Graphs (in Hungarian), Casopois Pest. Mat., Vol. 80, 477—480 (1955).

8.6. D. L. Wang and D. L. Kleitman, On the Existence of «-Connected Graphs with Prescribed Degrees (n^s2), Networks, Vol. 3, 225—239 (1973).

8.7. P. Erdos and T. Gallai, Graphs with Prescribed Degrees of Vertices (in Hungarian), Mat. Lapok, Vol. 11, 264—274 (1960).

8.8. Cm. [1.3].

8.9. J. Edmonds, Existence of A-Edge-Connected Ordinary Graphs with Prescribed Degrees, J. Res. Nat. Bur. Stand. B., Vol. 68, 73—74 (1964).

8.10. D. L. Wang and D. J. Kleitman, A Note on n-Edge Connectivity, SIAM J. Appl. Math., Vol. 26, 313—314 (1974).

8.11. K- Menger, Zur allgemeinen Kurventheorie, Fund. Math., Vol. 10, 96—115 (1927).

8.12. H. Whitney, Congruent Graphs and the Connectivity of Graphs, Am. J. Math., Vol. 54, 150—168 (1932).

8.13. W. T. Tutte, A Theory of 3-Connected Graphs, Indag. Math., Vol. 23, 441—455 (1961).

8.14. L. R. Ford and D. R. Fulkerson, Maximal Flow Through a Network, Canad. J. Math., Voi. 8, 399—404 (1956).

8.15. P. Elias, A. Feinstein, С. E. Shannon, A Note on the Maximum Flow Through a Network, IRE Trans. Inform. Theory, IT-2, 117—119 (1956). [Имеется перевод: П. Элиас, А. Файнстейн, К- Шеннон. О максимальном потоке через сеть: В сб. К- Шеннон. Работы по теории информации и кибернетике: —М.: ИЛ, 1963.]

8.16. P. Hall, On Representatives of Subsets, J. London Math. Soc., Vol. 10, 26—30 (1935).

8.17. P. R. Halmosn, H. E. Vaughan, The Marriage Problem, Am. J. Math., Vol. 72, 214—215 (1950).

8.18. D. Konig, Graphs and Matrices, Mat. Fiz. Lapok, Vol. 38, 116—119 (1931).

8.19. O. Ore, Graphs and Matching Theorems, Duke Math J., Vol. 22 , 625—639 (1955).

8.20. R. Rado, Note on the Transfinite Case of Hall’s Theorem on Representatives, J. London Math. Soc., Vol. 42, 321—324 (1967).

8.21. C. Berge, Two Theorems in Graph Theory, Proc. Nat. Acad. Sci. U.S., Vol. 43, 842-844 (1957).

8.22. N.S. Mendelsohn, A. L. Dulmage, Some Generalizations of the Problem of Distinct Representatives, Canad, J. Math., Vol. 10, 230—241 (1958).

8.23. W. T. Tutte, The Factorization of Linear Graphs, J. London Math. Soc., Vol. 22, 107—111 (1947).

8.24. I. Anderson, Perfect Matchings of a Graph., J. Combinatorial Theory B., Vol. 10, 183-186 (1971).

8.25. L. Lovasz, Three Short Proofs in Graph Theory, J. Combinatorial Theory B, Vol. 19, 111—113 (1975).

8.26. C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973.

8.27. F. T. Boesch (Ed.), Large-Scale Networks: Theory and Design, IEEE Press, New York, 1976.

8.28. S. L. Hakimi, An Algorithm for Construction of Least Vulnerable Communication Networks or the Graph with the Maximum Connectivity, IEEE Trans. Circuit Theory, Vol. CT-16, 229—230 (1969).

8.29. F. T. Boesch and R. E. Thomas, On Graphs of Invulnerable Communication Nets, IEEE Trans. Circuit Theory, Vol. CT-17, 183—192 (1970).

8.30. A. T. Amin and S. L. Hakimi, Graphs with Given Connectivity and Independence Number or Networks with Given Measures of Vulnerability and Survivability, IEEE Trans. Circuit Theory, Vol. CT-20, 2—10 (1973).

8.31. H. Frank and I. T. Frisch, Communication, Transmission, and Transsorta-tion Networks, Addison-Wesley, Reading, Mass., 1971.

8.32. L. Mirsky and H. Perfect, Systems of Representatives, J. Math. Anal. Applic., Vol. 15, 520—568 (1966).

8.33. R. A. Brualdi, Transversal Theory and Graphs, in Studies in Graph Theory, Part II, MAA Press, 1975, pp. 23—88.

8.34. L. Mirsky, Transversal Theory, Academic Press, New York, 1971.

8.35. J. A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmil-lan, London, 1976. 8.36. Cm. [1.5].

9.1. D. Konig, Graphs and Matrices (in Hungarian), Mat. Fiz. Lapok, Vol. 38, 116—118 (1931).

9.2. C. Berge, Graphs and Hypergraphs, North Holland, Amsterdam, 1973.

9.3. T. Gallai, Uber extreme Punkt und Kantenmengen, Ann. Univ. Sci. Budapest, Edtvos Sect. Math., Vol. 2, 133—138 (1959).

9.4. V- G. Vizing, On an Estimate of the Chromatic Class of a p-Graph (in Russian), Diskret. Analiz., Vol. 3, 25—30 (1964).

9.5. J. C. Fournier, Colorations des aretes d’un graphe, Cahiers du CERO, Vol. 15, 311—314 (1973).

9.6. J. A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan, London, 1976.

9.7. R. L. Brooks, On Colouring the Nodes of a Network, Proc. Cambridge Phil. Soc., Vol. 37, 194—197 (1941).

9.8. L. S. Melnikov and V. G. Vizing, New Proof of Brooks’ Theorem, J. Combinatorial Theory, Vol. 7, 289—290 (1969).

9.9. L. Lovasz, Three Short Proofs in Graph Theory, J. Combinatorial Theory B, Vol. 19, 111—113 (1975).

9.10. P. J. Heawood, Map Colour Theorems, Quart. J. Math., Vol. 24, 332—338 (1890).

9.11. K. I. Appel and W. Haken, Every Planar Map is Four-Colorable, Bull. Am. Math. Soc., Vol. 82, 711—712 (1976).

9.12. O. Ore, The Four-Color Problem, Academic Press, New York, 1967.

S. 13. T. L. Saaty, Thirteen Colorful Variations on Guthrie’s Four-Color Conjecture, Am. Math. Monthly, Vol. 79, 2—43 (1972).

9.14. T. L. Saaty and P. C. Kainen, The Four-Coior Problem: Assaults and Conquests, McGraw-Hill, New York, 1977.

9.15. H. Whitney and W. T. Tutte, Kempe Chains and the Four Colour Problem, in Studies in Graph Theory, Part II, MAA Press, 1975, pp. 378—413.

9.16. Cm. [1.3].

9.17. P. Turan, An Extremal Problem in Graph Theory (in Hungarian), Mat. Fiz. Lapok, Vol. 48, 436—452 (1941).

9.18. P. Erdos, On the Graph Theorem of Turan (in Hungarian), Mat. Lapok, Vol. 21, 249—251 (1970).

9.19. B. Bollobas, Extremal Graph Theory, Academic Press, New York, 1978.

9-20 H. Frank and I. T. Frisch, Communication, Transmission, and Transportation Networks, Addison-Wesley, Reading, Mass., 1971.

9.21. F. T. Boesch (Ed.), Large-Scale Networks: Theory and Design, IEEE Press, New York, 1976.

9.22. P. Karivaratharajan and K- Thulasiraman, К-Sets of a Graph and Vulnerability of Communication Nets, Matrix and Tensor Quart., Vol. 25, 63—66 (1974), 77—86 (1975).

9.23. P. Karivaratharajan and K. Thulasiraman, An Extremal Problem in Graph Theory and Its Applications, Proc. IEEE Intl. Symp. on Circuits and Systems, Tokyo, Japan, 1979.

9.24. C. L. Liu, Introduction to Combinatorial Mathematics, McGraw-Hill, New York, 1968.

9.25. L. Lovasz, On the Shannon Capacity of a Graph, IEEE Trans. Inform. Theory, Vol. IT-25, 1—7 (1979).

9.26. R. C. Read, An Introduction to Chromatic Polynomials, J. Combinatorial Theory, Vol. 4, 52—71 (1968).

9.27. G. D. Birkhoff, A Determinan Formula for the Number of Ways of Coloring a Map, Ann. Math., Vol. 14, 42—46 (1912).

9.28. W. T. Tutte, On Chromatic Polynomials and the Golden Ratio, J. Combinatorial Theory, Vol. 9, 289—296 (1970).

9.29. W. T. Tutte, Chromials in Studies in Graph Theory, Part II, MAA Press, 1975, pp. 361—377.

9.30. D. C. Wood, A Technique for Colouring a Graph Applicable to Large-Scale Timetabling Problems, Computer J., Vol. 12, 317 (1969).

9.31. N. Christofides, Graph Theory: An Algorithmic Approach, Academic Press, New York, 1975. [Имеется перевод: H. Крис'тофидес. Теория графов: Алгоритмический подход: — М.: Мир, 1978.]

9.32. Е. J. Cockayne and S. Т. Hedetniemi, Towards a Theory of Domination in Graphs, Networks, Vol. 7, 247—267 (1977).

9.33. E. J. Cockayne, S. T. Hedetniemi, Optimal Domination in Graphs, IEEE Trans. Circuits and Sys., Vol. CAS-22, 41—44 (1975).

9.34. D.J.A. Welsh, М. B. Powell, An Upper Bound for the Chromatic of a Graph and Its Application of Timetabling Problems, Computer J., Vol. 10, 85—87 (1967).

10.1. H. Whitney, On the Abstract Properties of Linear Dependence, Am. J. Math., Vol. 57, 509—533 (1935).

10.2. G. J. Minty, On the Axiomatic Foundations of the Theories of Directed Linear Graphs, Electrical Networks and Network Programming, J. Math, and Mech., Vol. 15, 485—520 (1966).

10.3. W. T. Tutte, Introduction to the Theory of Matroids, American Elsevier, New York, 1971.

10.4. D.J.A. Welsh, Matroid Theory, Academic Press, New York, 1976.

10.5. G. J. Minty, Monotone Networks, Proc. Roy. Soc., A, Vol. 257, 191—212 (1960).

10.6. G. J. Minty, Solving Steady-State Non-Linear Networks of ‘Monotone’ Elements, IRE Trans. Circuit Theory, Vol. CT-8, 99—104 (1961).

10.7. J. B. Kruskal, On the Shortest Spanning Subgraph of a Graph and the Travelling Salesman Problem, Proc. Am. Math. Soc., Vol. 7, 48—49 (1956).

10.8. R. Rado, Note on Independence Functions, Proc. London Math. Soc., Vol. 7, 300—320 (1957).

10.9. J. Edmonds, Matroids and the Greedy Algorithm, Math. Programming, Vol. 1, 127—136 (1971).

10.10. D. Gale, Optimal Assignments in an Ordered Set: An Application of .Matroid Theory, J. Combinatorial Theory, Vol. 4, 176—180 (1968).

10.11. D.J.A. Welsh, Kruskal’s Theorem for Matroids, Proc. Cambridge Phil. Soc., Vol. 64, 3—4 (1968).

10.12. Rabe von Randow, Introduction to the Theory of Matroids, Springer Lecture Notes in Mathematical Economics, Vol. 109, 1975.

10.13. C. Berge, Graphs and Hypergraphs, North Holland, Amsterdam, 1973.

10.14. Cm. [1.5].

10.15. R. Rado, A Theorem on Independence Relations, Quart, J. Math. (Oxford), Vol. 13, 83—89 (1942).

10.16. A. Lehman, A Solution of the Shannon Switching Game, SIAM J. Appl. Math., Vol. 12, 687—725 (1964).

10.17. W. T. Tutte, A Homotopy Theorem for Matroids-I and II, Trans. Am. Math. Soc., Vol. 88, 144—174 (1958).

10.18. W. T. Tutte, Lectures on Matroids, J. Res. Nat. Bur. Stand., Vol. 69B, 1—48 (1965).

10.19. W. T. Tutte, Matroids and Graphs, Trans. Am. Math. Soc., Vol. 90, 527— 552 (1959).

10.20. W. T. Tutte, Connectivity in Matroids, Canad. J. Math., Vol. 18, 1301 — 1324 (1966).

10.21. L. Mirsky, Application of the Notion of Independence to Combinatorial Analysis, J. Combinatorial Theory, Vol. 2, 327—357 (1967).

10.22. F. Harary and D.J.A. Welsh, Matroids versus Graphs, in The Many Facets of Graph Theory, Springer Lecture Notes, Vol. 110, 1969, pp. 155—170.

10.23. R. J. Wilson, An Introduction to Matroid Theory, Am- Math. Monthly, Vol. 80, 500—525 (1973).

10.24. J. Edmonds, Minimum Partition of a Matroid into Independent Subsets, J. Res. Nat. Bur. Stand., Vol. 69B, 67—72 (1965).

10.25. J. Edmonds and D. R. Fulkerson, Transversals and Matroids Partition, J. Res. Nat. Bur. Stand., Vol. 69B, 147—153 (1965).

10.26. L. Mirsky, Tranversal Theory, Academic Press, London, 1971.

10.27. E. L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976.

10.28. R.G. Bland and M. Las Vergnas, Orientability of Matroids, J. Combinatorial Theory B, Vol. 24, 94—123 (1978).

10.29. J. Folkman and J. Lawrence, Oriented Matroids, J. Combinatorial Theory B, Vol. 25, 199—236 (1978).

10.30. J. Edmonds, Lehman’s Switching Game and a Theorem of Tutte and Nash-Williams, J. Res. Nat. Bur. Stand.., Vol. 69B, 73—77 (1965).

10.31. J. Bruno and L. Weinberg, A Constructive Graph-Theoretic Solution of the Shannon Switching Game, IEEE Trans. Circuit Theory, Vol. CT-17, 74-81 (1970).

10.32. D. E. Knuth, Matroid Partitioning, Stanford University Rep. STAN-CS-73-342, 1—12 (1973).

10.33. J. Edmonds, Matroid Partition, in Lectures in Appl. Math., Vol. 11: Mathematics of Decision Sciences, 1967, pp. 335—346.

10.34. R. J. Duffin, Topology of Series-Parallel Networks, J. Math. Anal. Appl., Vol. 10, 303-318 (1965).

10.35. R. J. Duffin and T. D. Morley, Wang Algebra and Matroids, IEEE Trans. Circuits and Syst., Vol. CAS-25, 755—762 (1978).

10.36. H. Narayanan, Theory of Matroids and Network Analysis, Ph. D. Thesis, Indian Institute of Technology, Bombay, India, 1974.

10.37. J. Bruno and L. Weinberg, Generalized Networks: Networks Embedded on a Matroid, Part 1, Networks, Vol. 6, 53—94 (1976).

10.38. J. Bruno and L. Weinberg, Generalized Networks: Networks Embedded on a Matroid, Part 2, Networks, Vol. 6, 231—272 (1976).

10.39. L. Weinberg, Matroid, Generalized Networks and Electric Network Synthesis, J. Combinatorial Theory B, Vol. 23, 106—126 (1977).

10.40. M. Iri and N. Tomizawa, A Unifying Approach to Fundamental Problems in Network Theory by Means of Matroids, Electron. Commun. in Japan, Vol. 58-A, 28—35 (1975).

10.41. A. Recski, On Partitional Matroids with Applications, in Coll. Math. Soc. J. Bolyai, Vol. 10: Infinite and Finite Sets, North-Holland-American Elsevier, Amsterdam, 1974, pp. 1169—1179.

10.42. A. Recski, Matroids and Independent State Variables, Proc. 2nd European Conf. Circuit Theory and Design, Genova, 1976.

10.43. B. Petersen, Investigating Solvability and Complexity of Linear Active Networks by Menas of Matroids, IEEE Trans. Circuits and Syst., Vol. CAS-26, 330—342 (1979).

10.44. C. Greene, A Multiple Exchange Property for Bases, Proc. Am. Math. Soc., Vol. 39, 45—50 (1973).

10.45. J. H. Mason, On a Class of Matroids Arising from Paths in Graphs, Proc. London Math. Soc., Vol. 25, 55—74 (1972).

10 46. R. C. Prim, Shortest Connection Networks and Some Generalizations, Bell Sys. Tech. J., Vol. 36, 1389—1402 (1957).

11.1. B. D. H. Tellegen, A General Network Theorem with Applications, Philips Res. Rept., Vol. 7, 259—269 (1952).

11.2. P. Penfield, Jr., R. Spence, and S. Duinker, A Generalized Form of Telle-gen’s Theorem, IEEE Trans. Circuit Theory, Vol. CT-17, 302—305 (1970).

11.3. P. Penfield, Jr., R. Spence, and S. Duinker, Tellegen’s Theorem and Electrical Networks, M.I.T. Press, Cambridge, Mass., 1970.

11.4. J. L. Bordewijk, Inter-Reciprocity Applied to Electrical Networks, Appl. Sci. Res., Vol. B6, 1—74 (1956).

11.5. S. W. Director and R. A. Rohrer, Automated Network Design—The Frequency Domain Case, IEEE Trans. Circuit Theory, Vol. CT-16, 330—337 (1969).

11.6. G. Kishi and T. Kida, Edge-Port Conservation in Networks, IEEE Trans. Circuit Theory, Vol. CT-15, 274—276 (1968).

11.7. G. Kishi and Y. Kajitani, Maximally Distant Trees and Principal Partition of a Linear Graph, IEEE Trans. Circuit Theory, Vol. CT-16, 323—330 (1969).

11.8. T. Ohtsuki, Y. Ishizaki, and H. Watanabe, Topological Degrees of Freedom and Mixed Analysis of Electrical Networks, IEEE Trans. Circuit Theory, Vol. CT-17, 491—499 (1970).

11.9. P. M. Lin, An Improved Algorithm for Principal Partition of Graphs, Proc. IEEE Intl. Symp. Circuits and Systems, 1976, pp. 145—148.

11.10. J. Bruno and L. Weinberg, The Principal Minors of a Matroid, Linear Algebra and Its Appl., Vol. 4, 17—54 (1971).

11.11. N. Balabanian and T. A. Bickart, Electrical Network Theory, Wiley, New York, 1969.

11.12. E. S. Kuh and R. A. Rohrer, TheState Variable Approach to Network Analysis, Proc. IEEE, Vol. 53, 672—686 (1965).

11.13. D. H. Wolaver, Proof in Graph Theory of the ‘No-Gain’ Property of Resistor Networks, IEEE Trans. Circuit Theory, Vol. CT-17, 436—437 (1970).

11.14. A. Talbot, Some Fundamental Properties of Networks without Mutual Inductance, Proc. I EE (London), Vol. 102, 168—175 (1955).

11.15. R. J. Schwartz, A Note on the Transfer Ratio of Resistive Networks with Positive Elements, Proc. IRE, Vol. 43, 1670 (1955).

11.16. Cm. [2.1].

11.17. W. H. Kim and R. T. Chien, Topological Analysis and Synthesis of Communication Networks, Columbia Univ. Press, New York, 1962.

11.18. W. K- Chen, Applied Graph Theory, North-Holland, Amsterdam, 1971.

11.19. W. Mayeda, Graph Theory, Wiley-Interscience, New York, 1970.

11.20. G. Kron, A Set of Principles to Interconnect the Solution of Physical Systems, J. Appl. Phys., Vol. 24, 965—980 (1953).

11.21. G. Kron, Diakoptics: The Piecewise Solution of Large Scale Systems, MacDonald, London, 1963.

11.22. H. H. Happ, Diakoptics and Networks, Academic Press, New York, 1971.

11.23. H. H. Happ, Diakoptics—The Solution of System Problems by Tearing, Proc. IEEE, Vol. 62, 930—940 (1974).

11.24. F. H. Branin, The Relation Between Kron’s Method and the Classical Methods of Network Analysis, Matrix and Tensor Quart, Vol. 12, 69—115 (1962).

11.25. F. H. Branin, A Sparse Matrix Modification of Kron’s Method of Piecewise Analysis, Proc. IEEE Intl. Symp. Circuits and Systems, 1975, pp. 21—23.

11.26. R. Onodera, Diakoptics and Codiakoptics of Electric Network, RAAG Memoirs, Vol. 2, 369—388 (1958).

11.27. J. Ruth, An Application of Algebraic Topology: Kron’s Method of Tearing, Quart. Appl. Math., Vol. 17, 1—24 (1959).

11.28. S. Amari, Topological Foundations of Kron’s Tearing of Electrical Networks, RAAG Memoirs, Vol. 3, 322—350 (1962).

11.29. К U. Wang and T. Chao, An Algebraic Theory of Network Topology, Proc. IEEE Intl. Symp. Circuits and Systems, 1974, pp. 324—328.

11.30. F. F. Wu, Solutions of Large—Scale Networks by Tearing, IEEE Trans. Circuits and Sys., Vol. CAS-23, 706—713 (1976).

11.31. L. О. Chua and L. K- Chen, Nonlinear Diakoptics, Proc. IEEE Intl. Symp. Circuits and Systems, 1975, pp. 373—376.

11.32. L. O. Chua and L. K. Chen, Diakoptic and Generalized Hybrid Analysis, IEEE Trans. Circuits and Sys., Vol. CAS-23, 694—705 (1976).

11.33. L. O. Chua and L. K- Chen, On Optimally Sparse Cycle and Coboundary Basis for a Linear Graph, IEEE Trans. Circuit Theory, Vol. CT-20, 495— 503, (1973).

11.34. L. O. Chua and D. N. Green, Graph-Theoretic Properties of Dynamic Nonlinear Networks, IEEE Trans. Circuits and Sys., Vol. CAS-23, 292—312 (1976).

11.35. T. R. Bashkow, The Л-Matrix—A New Network Description, IRE Trans. Circuit Theory, Vol. CT-4, 117—119 (1957).

11.36. P. R. Bryant, The Explicit Form of Bashkow’s Л-Matrix, IRE Trans. Circuit Theory, Vol. CT-9, 303—306 (1962).

11.37. E. J. Purslow. Solvability and Analysis of Linear Active Networks by Use of the State Equations, IEEE Trans. Circuit Theory, Vol. CT-17, 469—475 (1970).

11.38. O. Tosun and A. Dervisoglu, Formulation of State Equations in Active RLC Networks, IEEE Trans. Circuits and Sys., Vol. CAS-21, 36—38 (1974).

11.39. S. K- Mark and M.N.S. Swamy, The Generalized Tree for State Variables in Linear Networks, Int. J. Circuit Theory and Appl., Vol. 4, 87—92 (1976).

11.40. W. K- Chen and F. N. Chan, On the Unique Solvability of Linear Active Networks, IEEE Trans. Circuits and Sys., Vol. CAS-21, 26—35 (1974).

11.41. J. Bruno and L. Weinberg, Generalized Networks Embedded on a Matroid—Part I, Networks, Vol. 6, 53—94 (1976).

11.42. J. Bruno and L. Weinberg, Generalized Networks: Networks Embedded on a Matroid—Part II, Networks, Vol. 6, 231—272 (1976).

11.43. L. Weinberg, Matroid, Generalized Networks, and Electric Network Synthesis, J. Combinat. Theory B, Vol. 23, 106—126 (1977).

11.44. R. J. Duffin and T. D. Morley, Wang Algebra and Matroids, IEEE Trans. Circuits and Sys., Vol. CAS-25, 755—762 (1978).

11.45. R. J. Duffin, An Analysis of the Wang Algebra of Networks, Trans. Am. Math. Soc., Vol. 93, 114—131 (1959).

11.46. К- T. Wang, On a New Method of Analysis of Electrical Networks, Memoirs 2, Nat. Res. Inst. Eng. Academia Sinica (1934).

11.47. B. Petersen, Investigating Solvability and Complexity of Linear Active Networks by means of Matroids, IEEE Trans. Circuits and Sys., Vol. CAS-26, 330—342 (1979).

11.48. M. Iri and N. Tomizawa, A Unifying Approach to Fundamental Problems in Network Theory by means of Matroids, Electron, and Commun. in Japan., Vol. 58-A, 28-35 (1975).

11.49. R. J. Duffin, Electrical Network Models, in Studies in Graph Theory, Part II, The Mathematical Association of America, 1975, pp. 94—138.

12.1. I. Cederbaum, Applications of Matrix Algebra to Network Theory, IRE Trans. Circuit Theory (special supplement), Vol. CT-6, 127—1-37 (1959).

12.2. L. Weinberg, Network Analysis and Synthesis, McGraw-Hill, New York, 1962.

12.3. E. A. Guillemin, On the Analysis and Synthesis of Single-Element Kind Networks, IRE Trans. Circuit Theory, Vol. CT-7, 303—312 (1960).

12.4. V. V. Bapeswara Rao, The Tree-Path Matrix of a Network and Its Applications., Ph. D. Thesis, Dept, of Electric Engineering, Indian Institute of Technology, Madras, India, 1970.

12.5. F. T. Boesch and D. C. Youla, Synthesis of (n+l)-Node Resistor n-Ports, IEEE Trans. Circuit Theory, Vol. CT-12, 515—520 (1965).

12.6. G. Biorci and P. P. Civalleri, On the Synthesis of Resistive ,/V-Port Networks, IRE Trans. Circuit Theory, Vol. CT-8, 22—28 (1961).

12.7. С. С. Halkias, I. Cederbaum, and W. H. Kim, Synthesis of Resistive n-Port with (/i+1) Nodes, IRE Trans. Circuit Theory, Vol. CT-9, 69—73 (1962)

12.8. E. A. Guillemin, On the Realization of an я-th Order G-Matrix, IRE Trans. Circuit Theory, Vol. CT-8, 318—323 (1961).

12.9. K- R- Swaminathan and I. T. Frisch, Necessary Conditions for the Realiza-bilitv of n-Port Resistive Networks with more than (n+1) Nodes, IEEE Trans. Circuit Theory, Vol. CT-12, 520-527 (1965).

12.10. G. Biorci and P. P. Civalleri, Analysis of Resistive Л'-Port Networks Based on (/t+2) Nodes, in Aspects of Network and System Theory (Eds. R. E. Kalman and N. De Claris), Holt, Rinehart, Winston, New York. 1971.

12.11. P. Subbarami Reddy and K- Thulasiraman, Synthesis of (n+2)-Node Resistive n-Port Networks, IEEE Trans Circuit Theory, Vol. CT-19, 20—25 (1972).

12.12. D. P. Brown, /V-Port Synthesis of Л'-order Positive Entry Resistance Matrices, J. Franklin Inst., Vol. 284, 26—38 (1967).

12.13. C. Eswaran and V. G. K- Murti, Realization of Positive Entry Resistance Matrices, AEU, Vol. 29, 212—216 (1975).

12.14. C. Eswaran and V. G. K- Murti, On a Relationship between Terminal Capacity and Impedance Matrices, IEEE Trans. Circuits and Sys., Vol. CAS-21, 732—734 (1974).

12.15. I. T. Frish and W. H. Kim, n-Port Resistive Networks and Communication Nets, IRE Trans. Circuit Theory, Vol. CT-8, 493—496 (1961).

12.16. I. Cederbaum, On Equivalence of Resistive ./V-Port Networks, IEEE Trans. Circuit Theory, Vol. CT-12, 338—344 (1965).

12.17. P. Subbarami Reddy, V. G. K- Murti, and K. Thulasiraman, Realization of Modified Cutset Matrix and Applications, IEEE Trans. Circuit Theory, Vol. CT-17, 475—486 (1970).

12.18. A. Lempel and I. Cederbaum, Parallel Interconnection of n-port Networks, IEEE Trans. Circuit Theory, Vol. CT-14, 274—279 (1967).

12.19. A. Lempel and I. Cederbaum, Terminal Configurations of n-Port Networks, IEEE Trans. Circuit Theory. Vol. CT-15, 51—53 (1968).

12.20. S. Prigozy and L. Weinberg, Realization of Fourth-Order Singular and Quasi-Singular Resistance and Conductance Matrices, IEEE Trans. Circuits and Sys., Vol. CAS-23, 245—253 (1976).

12.21. M. G. Govihdarajulu Naidu, P. Subbarami Reddy, and K- Thulasiraman, (n+2)-Node Resistive n-Port Readability of F-Matrices, IEEE Trans. Circuits and Sys., Vol. CAS-23, 254—261 (1976).

12.22. W. T. Tutte, An Algorithm for Determining w'hether a Given Binary Matroid is Graphic, Proc. Am. Math. Soc., Vol. 11, 905—917 (1960).

12.23. W. T. Tutte, From Matrices to Graphs, Can. J. Math., Vol. 56, 108—127 (1964).

12.24. W. Mayeda, Necessary and Sufficient Conditions for the Realizability of Cutset and Circuit Matrices, IRE Trans. Circuit Theory, Vol. CT-7, 79—81 (1960).

12.25. W. Mayeda, A Proof of Tutte’s Realizability Condition, IEEE Trans.

Circuit Theory, Vol. CT-17, 506—511 (1970).'

12.26. W. H. Kim and R. T. Chien, Topological Analysis and Synthesis of Communication Networks, Columbia Univ. Press, New York, 1962.

12.27. M.N.S. Swamy and K- Thulasiraman, Realization of the Л-Matrix of RLC Networks, IEEE Trans. Circuit Theory, Vol. CT-19, 515—518 (1972).

12.28. L. O. Chua and D. N. Green, Graph-Theoretic Properties of Dynamic Nonlinear Networks, IEEE Trans. Circuits and Sys., Vol. CAS-23, 292—302 (1976).

12.29. K- Thulasiraman and V. G. K- Murti, Pseudo-Series Combination of n-Port Networks. Proc. IEEE, Vol. 56, 1143—1144 (1968).

13.1. A. C. Aitken, Determinants and Matrices, Intcrscience, New York, 1956.

13.2. N. Balabanian and T. A. Bickart, Electrical Network Theory, Wiley, New York, 1969.

13.3. S. K- Mitra, Analysis and Synthesis of Linear Active Networks, Wiley, New York, 1969.

13.4. G. E. Sharpe and B. Spain, On the Solution of Networks by means of the Equi-Cofactor Matrix, IRE Trans. Circuit Theory, Vol. CT-7, 230— 239 (1960).

13.5. J. L. Bordewijk, Inter-Reciprocity Applied to Electrical Networks, Appl. Csi, Res., Vol. B6, 1—74 (1956).

13.6. S. W. Director and R. A. Rohrer, Automated Network Design—The Frequency Domain Case, IEEE Trans. Circuit Theory, Vol. CT-16, 330—337 (1969).

13.7. В. B. Bhattacharyya and M. N. S. Swamy, Network Transposition and Its Application in Synthesis, IEEE Trans. Circuit Theory, Vol. CT-18, 394 —397 (1971).

13.8. M.N.S. Swamy, C. Bhushan, and В. B. Bhattacharyya, Generalized Duals, Generalized Inverses, and Their Applications, Radio and Electron. Eng.,

Vol. 44, 95—97 (1974).

13.9. M.N.S. Swamy, C. Bhushan, and В. B. Bhattacharyya, Generalized Dual Transposition and Its Applications, J. Franklin Inst., Vol. 301, 465—474 (1976).

13.10. K- Dagget and J. Vlach, Sensitivity-Compensated Active Networks, IEEE Trans. Circuit Theory, Vol. CT-16, 416—422 (1969).

13.11. W. K. Chen, Applied Graph Theory, North-Holland, Amsterdam, 1971.

13.12. S. Seshu and М. B. Reed, Linear Graphs and Electrical Networks, Addison-Wesley, Reading, Mass., 1961.

13.13. S. P. Chan, Introductory Topological Analysis of Electrical Networks, Holt, Rinehart and Winston, New York, 1969.

13.14. W. Mayeda, Graph Theory, Wiley-Interscience, New York, 1972.

13.15. J. Numata and M. Iri, Mixed-Type Topological Formulas for General Linear Networks, IEEE Trans. Circuit Theory, Vol. CT-20, 488—494 (1973).

13.16. P. Penfield, Jr., R. Spence, and S. Duinker, Tellegen’s Theorem and Electrical Networks, М. I. T. Press, Cambridge, Mass., 1970.

13.17. P. Penfield, Jr., R. Spence, and S. Duinker, A Generalized Form of Tellegen’s Theorem, IEEE Trans. Circuit Theory, Vol. CT-17, 302—305 (1970).

13.18. C. A. Desoer, On the Description of Adjoint Networks, IEEE Trans. Circuits and Sys., CAS-22, 585—587 (1975), Erratum, IEEE Trans. Circuits and Sys., CAS-23 , 58 (1976).

13.19. S. W. Director, R. A. Rohrer, On the Design of Resistance n-Port Networks by Digital Computer, IEEE Trans. Circuit Theory, CT-16, 337—346 (1969).

13.20. M.N.S. Swamy, C. Bhushan, and K- Thulasiraman, Bounds on the Sum of Element Sensitivity Magnitudes for Network Functions, IEEE Trans. Circuit Theory, CT-19, 502—504 (1972).

13.21. M.N.S. Swamy, C. Bhushan, and K- Thulasiraman, Sensitivity, IEEE Trans, Circuit Theory, CT-20, 21—24 (1973).

14.1. D. Gries, Compiler Construction fo Digital Computers, Wiley, NewYork, 1971.

14.2. S. Warshall, A Theorem on Boolean Matrices, J. ACM, Vol. 9, 11—12 (1962).

14.3. H. S. Warren, A Modification of Warshall’s Algorithm for the Transitive Closure of Binary Relations, Comm. ACM, Vol. 18, 218—220 (1975).

14.4. Арлазаров В. JI., Диниц Е. А., Кронрод М. А., Фараджев И. А. Экономическое построение транзитивного замыкания ориентированного графа, ДАН, 1970, т. 11, с. 1209—1210.

J4.5. V. Strassen, Gaussian Elimination is Not Optimal, Numerische Math., Vol. 13, 354—356 (1969).

14.6. M. J. Fischer, A. R. Meyer, Boolean Matrix Multiplication and Transitive Closure, Conf. Record. IEEE 12th Annual Symp. on Switching and Automata Theory, 1971, pp. 129—131.

14.7. М. E. Furman, Application of a Method of Fast Multiplication of Matrices in the Problem of Finding the Transitive Clolsure of a Graph, Soviet Math., Dokl., Vol. 11, 1252 (1970).

14.8. I. Munro, Efficient Determination of the Transitive Closure of a Directed Graph, Information Processing Lett., Vol. 1, 56—58 (1971).

14.9. P. E. O’Neil, E. J. O’Neil, A Fast Expected Time Algorithm for Boolean Matrix Multiplication and Transitive Closure, Inform, and Control, Vol. 22, 132—138 (1973).

14.10. J. Eve, R. Kurki-Suonio, On Computing the Transitive Closure of a Relation, Acta Informatika, Vol. 8, 303—314 (1977).

14.11. P. Purdom, A Transitive Closure Algorithm, BIT, Vol. 10, 76—94 (1970).

14.12. C. P. Schnorr, An Algorithm for Transitive Closure with Linear Expected Time, SIAM J. Computing, Vol. 7, 127—133 (1978).

14.13. М. M. Syslo and J. Dzikiewicz, Computational Experience with Some Transitive Closure Algorithms, Computing, Vol. 15, 33—39 (1975).

14.14. A. Pnueli, A. Lempel, and S. Even, Transitive Orientation of Graphs and Identification of Permutation Graphs, Canad. J. Math.., Vol. 23, 160—175 (1971).

14.15. P. C. Gilmore and A. J. Hoffman, A Characterization of Comparability Graphs and of Interval Graphs, Canad. J. Math., Vol. 16, 539—548 (1964).

14.16. S. Even, A. Pnueli, and A. Lempel, Permutation Graphs and Transitive Graphs, J. ACM, Vol. 19, 400—410 (1972).

14.17. S. Even. Algorithmic Combinatorics, Macmillan, New York, 1973.

14.18. C. L. Liu, Introduction to Combinatorial Mathematics, McGraw-Hill, New York, 1968.

14.19. R. E. Tarjan, Depth-First Search and Linear Graph Algorithms, S/AM J. Computing, Vol. 1, 146—160 (1972).

14.20. J. Hopcroft and R. Tarjan, Efficient Algorithms for Graph Manipulation, Comm. ACM, Vol. 16, 372—378 (1973).

14.21. A. V. Aho, J. E. Hopcroft, and J. D. Ullman, On Finding the Least Common Ancestors in Trees, SIAM J. Computing, Vol. 5, 115—132 (1976).

14.22. J. Cocke, Global Common Subexpression Eliminaiton, SIGPLAN Notices, Vol. 5, 20—24 (1970).

14.23. J. D. Ullman, East Algorithms for the Elimination of Common Subexpressions Acta Informatica, Vol. 2, 191—213 (1973).

14.24. K- Kennedy, A Global Flow Analysis Algorithm, Int. J. Computer Math{, Vol. 3, 5—16 (1971).

14.25. M. Schaefer, A Mathematical Theory of Global Program Optimization, Prentice-Hall, Englewood C. Cliffs, N. J., 1973.

14.26. A. V. Aho and J. D. Ullman, The Theory of Parsing, Translation and Compiling, Vol. II—Compiling, Prentice-Hall, Englewood, Cliffs, N.J. 1973. [Имеется перевод: A. Axo, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции: — М.: Мир, 1978.)

14.27. F. Е. Allen, Control Flow Analysis, SIGPLAN Notices, Vol. 5, 1—19 (1970).

14.28. F. E. Allen, Program Optimization, Annua! Review in Automatic Programming, Vol. 5., Pergamon, New York, 1969.

14.29. M. S. Hecht, Flow Analysis of Computer Programs, Elsevier, New York, 1977.

14.30. M. S. Hecht and J. D. Ullman, Flow Graph Reductibility, SIAM J. Computing, Vol. 1, 188—202 (1972).

14.31. J. Cocke, R. E. Miller, Some Analysis Techniques for Optimizing Computer Programs, Proc. 2nd Int. Conf. on System Sciences, Honolulu, Hawaii, 1969.

14.32. J. E. Hopcroft, J. D. Ullman, An nlog ri Algorithm for Detecting Reducible Graphs, Proc. 6th Annual Princeton Conf. on Information Sciences and Systems, Princeton, J. N. 1972, pp. 119—122.

14.33. R. E. Tarjan, Testing Flow Graph Reductibility, Proc. 5th Annual ACM Symp. on Theory of Computing, 1973, pp. 96—107.

14.34. R. E. Tarjan, Testing Flow Graph Reductibility, J. Comput. Sys. Sci., Vol. 9, 355—365 (1974).

14.35. M. S. Hecht and J. D. Ullman, Characterizations of Reducible Flow Graphs, J. ACM, Vol. 21, 367—375 (1974).

14.36. J. M. Adams, J. M. Phelan, and R. H. Stark, A Note on the Hecht-Ullman Characterization of Non-Reducible Flow Graphs, SIAM J. Computing, Vol. 3, 222—223 (1974).

14.37. M. Fischer, Efficiency of Equivalence Algorithms, in Complexity of Computer Computations (R. E. Miller and J. W. Thatcher, Eds.), Plenum Press,

New York, 1972, pp. 153—168.

14.38. J. E. Hopcroft and J. D. Ullman, Set Merging Algorithms, SIAM J. Computing, Vol. 2, 294—303 (1973).

14.39. R. E. Tarjan, On the Efficiency of a Good but Not Linear Set Union Algorithm, J. ACM, Vol. 22, 215—225 (1975).

14.40. Cm. [5.14].

14.41. E. Horowitz and S. Sahni, Fundamentals of Data Structures, Computer Science Press, Potomac, Md., 1976.

14.42. T. Lengauer and R. E. Tarjan, A Fast Algorithm for Finding Dominators in a Flow Graph, Trans, on Prog. Lang. and.sSys., Vol. 1, 121 —141 (1979).

14.43. R. E. Tarjan, Finding Dominators in Directed Graphs, SIAM J. Computing, Vol. 3, 62—89 (1974).

14.44. R. E. Tarjan, Applications of Path Compression on Balanced Trees, J. ACM, Vol. 26, 690—715 (1979).

14.45. A. V. Aho and J. D. Ullman, Principles of Compiler Design, Addison-Wesley, Reading, Mass., 1977.

14.46. P. W. Purdom and E. F. Moore, Algorithm 430: Immediate Predominators in a Directed Graph, Comm. ACM, Vol. 15, 777—778 (1972).

14.47. H. Frank and I. T. Friseh, Communication, Transmission and Transportation Networks, Addison-Wesley, Reading, Mass., 1971.

14.48. Cm. [5.12].

14.49. Cm. [9.31].

14.50. E. L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976.

14.51. Cm. [5.15].

14.52. E. Minieka, Optimization Algorithms for Networks and Graphs, Marchel Dekker, New York, 1978. [Имеется перевод: Э. Майника. Алгоритмы оптимизации на сетях и графах.— М.: Мир, 1981.]

14.53. S. Even, Graph Algorithms, Computer Science Press, Potomac, Md., 1979.

14.54. S. A. Cook, The Complexity of Theorem Proving Procedures, Proc. 3rd ACM Symp. on Theory of Computing 1971, pp. 151 —158. [Имеется перевод: С. А. Кук. Сложность процедур доказательства теорем: Кибернетический сборник. Вып. 18:—М.: Мир, 1981.]

14.55. R. М. Karp, Reducibility among Combinatorial Problems, in Comoicxity of Computer Computations (R. E. Miller and J. W. Thatcher, Eds.) Plenum Press, New York, 1972, pp. 85—104. [Имеется перевод: P. М. Карп. Сводимость комбинаторных задач: Кибернетический сборник. Вып. 13: — М.: Мир, 1981.]

14.56. М. R. Garey and D. S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, Freeman, San Francisco, Ca., 1979.

14.57. E. Horowitz and S. Sahni, Fundamentals of Computer Algorithms, Computer Science Press, Potomac, Md., 1978.

14.58. А. V. Aho, М. R. Garey, and J. D. Ullman, The Transitive Reduction of a Directed Graph, SIAM J. Computing, Vol. 1, 131 —137 (1972).

14.59. H. Priifer, Neuer Beveis eines Satzes liber Permutationen, Arch. Match. Phys., Vol. 27, 742—744 (1918).

15.1. L. R. Ford and D. R. Fullkerson, Flows in Networks, Princeton Univ. Press, Princeton, N- J. 1962. [Имеется перевод: Л. P. Форд, Д. Фалкерсоп. Потоки в сетях: — М.: Мир, 1966.]

15.2. Е. W. Dijkstra, A Note on Two Problems in Connexion with Graphs, N timer ische Math., Vol. 1, 269—271 (1959).

15.3. D. B. Johnson, A Note on Dijkstra’s Shortest Path Algorithm, J. ACM, Vol. 20, 385—388 (1973).

15.4. J. Edmonds and R. M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, J. ACM, Vol. 19, 248—264 (1972).

15.5. S. E. Dreyfus, An Appraisal of Some Shortest-Path Algorithms, Operations Research, Vol. 17, 395—412 (1969).

15.6. Т. C. Hu, A Decomposition Algorithm for Shortest Paths in a Network, Operations Research, Vol. 16, 91 —102 (1968).

15.7. H. Frank and I. T. Frisch, Communication, Transmission and Transportation Networks, Addison-Wesley, Reading, Mass., 1971.

15.8. Cm. [9.31].

15.9. E. L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976.

15.10. P. M. Spira and A. Pan, On Finding and Updating Spanning Trees and Shortest Paths, SIAM J. Comput., Vol. 4, 375—380 (1975).

15.11. D. B. Johnson, Efficient Algorithms for Shortest Paths in Sparse Networks, J. ACM, Vol. 24, 1 — 13 (1977).

15.12. R. A. Wagner, A Shortest Path Algorithm for Edge-Snarse Graphs, J. ACM, Vol. 23, 50—57 (1976).

15.13. R. W. Floyd, Algorithm 97: Shortest Path, Comm. ACM, Vol. 5, 345 (1962).

15.14. Y. Tabourier, All Shortest Distances in a Graph: An Improvement to Dan-tzig’s Inductive Algorithm, Discrete Math., Vol. 4, 83—87 (1973).

15.15. J. Y. Yen, Finding the Lengths of All Shortest Paths in A'-Node, Non-Negative Distance Complete Networks Using A,3/2 Additions and N3 Comparisons, J. ACM, Vol. 19 , 423—424 (1972).

15.16. T. A. Williams and G. P. White, A Note on Yen’s Algorithm for Finding the Length of All Shortest Paths in A'-Node Non-Negative Distance Networks, J. ACM, Vol. 20, 389—390 (1973).

15.17. A. R. Pierce, Bibliography on Algorithms for Shortest Path, Shortest Spanning Tree and Related Circuit Routing Problems (1956—1974), Networks, Vol. 5, 129—149 (1975).

15.18. D. A. Huffman, A Method for the Construction of Minimum Redundancy Codes, Proc. IRE, Vol. 40, 1098—1101 (1952).

15.19. E. N. Gilbert and E. F. Moore, Variable-Length Binary Encodings, Bell Sys. Tech. J., Vol. 38, 933—968 (1959).

15.20. D. E. Knuth, Optimum Binary Search Trees, Acta Informatica, Vol. 1, 14—25 (1971).

15.21. A. Itai, Optimal Alphabetic Trees, SIAM J. Comput., Vol. 5, 9—18 (1976).

15.22. Т. C. Hu and A. C. Tucker, Optimal Computer Search Trees and Variable-Length Alphabetical Codes, SIAM J. Appl. Math., Vol. 21, 514—532 (1971).

15.23. Т. C. Hu, A New Proof of the T-C Algorithm, SIAM J. Appl. Math., Vol. 25, 83—94 (1973).

15.24. Cm. [5.12].

15.25. A. M. Garsia and M. L. Wachs, A New Algorithm for Minimum Cost Binary Trees, SIAM J. Comput., Vol. 6, 622—642 (1977).

15.26. Cm. [5.15].

15.27. M. Miyakawa, Т. Yuba, Y. Sugito, and M. Hoshi, Optimum Sequence Tree’s, SIAM J. Comput., Vol. 6, 201—234 (1977).

15.28. J. Edmonds, Paths, Trees and Flowers, Canad. J. Math., Vol. 17, 449—467 (1965).

15.29. H. N. Gabow, An Efficient Implementation of Edmonds’ Algorithm for Maximum Matching on Graphs, J. ACM, Vol. 23, 221—234 (1976).

15.30. М. I. Balinski, Labelling to Obtain aMaximum Matching, in Combinatorial Mathematics and Its Applications (R. C. Bose and T. A. Dowling, Eds ), Univ. North Carolina Press Chappel Hill, N.C., 1967, pp. 585—602.

15.31. D. Witzgall and С. T. Zahn, Jr., Modification of Edmonds’ Algorithm for Maximum Matching of Graphs, J. Res. Nat. Bur. Std., Vol. 69B, 91—98 (1965).

15.32. T. Kameda and I.Munro, AO(] V| • [/?() Algorithm for Maximum Matching of Graphs, Computing, Vol. 12, 91—98 (1974).

15.33. J. Edmonds, Maximum Matching and a Polyhedron with 0,1 Vertices, J. Res. Nat. Bur. Std., Vol. 69B, 125—130 (1965).

15.34. H. Gabow, An Efficient Implementation of Edmonds’ Maximum Matching Algorithm, Tech. Rep. 31, Stanford Univ. Comp. Science Dept., 1972.

15.35. J. A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan, London, 1976.

15.36. J. E. Hopcroft and R. M. Karp, An nls Algorithm for Maximum Matching in Bipartite Graphs, SIAM J. Comput., Vol. 2, 225—231 (1913).

15.37. S. Even and R. E. Tarjan, Network Flow and Testing Graph Connectivity, SIAM J. Comput., Vol. 4, 507—518 (1975).

15.38. S. Even and O. Kariv, An 0(п/г) Algorithm for Maximum Matching in General Graphs, Proc. 16th Annual Symp. on Foundations of Comp. Science. IEEE, 1975, pp. 100—112.

15.39. A. Itai, M. Rodeh, and S. L. Tanimoto, Some Matching Problems for Bipartite Graphs, J. ACM, Vol. 25, 517—525 (1978).

15.40. H. W. Kuhn, The Hungarian Method for the Assignment Problem, Naval Res. Legist. Quart., Vol. 2, 83—97 (1955).

15.41. J. Munkres, Algorithms for the Assignment and Transportation Problems, J. SIAM, Vol. 5, 32—38 (1957).

15.42. N. Megido, A. Tamir, An 0(N log N) Algorithm for a Class of Matching Problems, SIAM J. Comput., Vol. 7, 154—157 (1978).

15.43. S. Even, A. Itai, A. Shamir, On the Complexity of Time-Table and Multicommodity Flow Problems, SIAM J. Comput., Vol. 5, 691—703 (1976).

15.44. L. R. Ford, D. R. Fulkerson, Maximal Flow through a Network, Canad. J. Math., Vol. 8, 399—404 (1956).

15.45. P. Elias, A. Feinstein, С. E. Shannon, A Note on the Maximum Flow Through a Network, IRE Trans. Inform. Theory, IT-2, 117—119 (1956).

15.46. C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973.

15.47. N. Zadeh, Theoretical Efficiency of the Edmonds-Karp Algorithm for Computing Maximal Flows, J. ACM, Vol. 19, 184—192 (1972).

15.48. Диниц E. А. Алгоритм решения задачи о максимальном потоке в сети с оценкой мощности, ДАН, 1970, т. 11, с. 1277—1280.

15.49. Карзанов А. В. Определение максимального потока в сети методом предикатов, ДАН, 1974, т. 15, с. 434—437.

15.50. V. М. Maihotra, М. Pramodh Kumar, and S. N. Maheswari, An 0(V3) Algorithm for Maximum Flows in Networks, Information Processing Lett., 7, 277—278 (1978).

15.51. S. Even, Graph Algorithms, Computer Press, Potomac, Md. 1979.

15.52. C. Berge, A. Ghouila-Houri, Programming, Games and Transportation Networks, Wiley, New Y'ork, 1962.

15.53. Т. C. Hu, Integer Programming and Network Flows, Addison-Wesley, Reading, Mass., 1969.

15.54. J. Edmonds, Optimum Branchings, J. Res. Nat. Bur. Std., Vol. 71B, 233— 240 (1967).

15.55. R. M. Karp, A Simple Derivation of Edmonds’ Algorithms for Optimum Branchings, Networks, Vol. 1, 265—272 (1972).

15.56. R. E. Tarjan, Finding Optimum Branchings, Networks, 7, 25—35 (1977).

15.57. Y. Chu, T. Liu, On the Shortest Arborescencef of a Directed Graph, Sci-entla Sinica (Peking), Vol. 4, 1396—1400 (1965); Math. Rev., Vol. 33, 1245 (G. W. Walkup).

15.53. F. C. Bock, An Algorithm to Construct a Minimum Directed Spanning Tree in a Directed Network, in Developments in Operati'ons Research, (B. Avi-Itzak, Ed.), Gordon and Breach, New York, 1971, pp. 29—44.

15.59. D. G. Corneil and С. C. Gotlieb, An Efficient Algorithm for Graph Isomorphism J. ACM, Vol. 17, 51—64 (1970).

15.60. L. Weinberg, A Simple and Efficient Algorithm for Determining Isomorphism of Planar Triply Connected Graphs, IEEE Trans. Circuit Theory, Vol. CT-13, 142—148 (1966).

15.61. J. E. Hopcroft and R. E. Tarjan, A V log V Algorithm for Isomorphism of Triconnected Planar Graphs, J. Comput. Syst. Sci., Vol. 7, 323—331 (1973).

15.62. J. E. Hopcroft and J. K- Wong, Linear Time Algorithm for Isomorphism on Planar Graphs, Proc. 6th Annual ACM Symp. on Theory of Computing, 1974, pp. 172—184.

15.63. J. E. Hopcroft and R, E. Tarjan, Efficient Planarity Testing, J. ACM, Vol. 21, 549—568 (1974).

15.64. N. Deo, Note on Hopcroft and Tarjan’s Planarity Algorithm, J. ACM, Vol. 23 , 74—75 (1976).

15.65. J. E. Hopcroft and R. E. Tarjan, Dividing a Graph into Triconnected Components, SIAM J. Comput., Vol. 2, 135—158 (1973).

15.66. D. J. Kleitman, Methods for Investigating the Connectivity of Large Graphs, IEEE Trans. Circuit Theory, Vol. CT-16, 232—233 (1969).

15.67. S. Even, An Algorithm for Determining whether the Connectivity of a Graph is at Least k, SIAM J. Comput., Vol. 4 , 393—396 (1975).

15.68. D. G. Corneil and B. Graham, An Algorithm for Determining the Chromatic Number of a Graph, SIAM J, Comput., Vol. 2, 311—318 (1973).

15.69. C. McDiarmid, Determining the Chromatic Number of a Graph, SIAM J. Comput., Vol. 8, 1—14 (1979).

15.70. D.J.A. Welsh and М. B. Powell, An Upper Bound for the Chromatic Number of a Graph and Its Applications to Timetabling Problems, The Computer J., Vol. 10, 85—86 (1967).

15.71. D. C. Wood, A Technique for Colouring a Graph Applicable to Large Scale Timetabling Problems, The Computer J., Vol. 10, 317—319 (1969).

15.72. D. Matula, G. Marble, and J. Isaacson, Graph Colouring Algorithms, in Graph Theory and Computing (R. C. Read, Ed.), Academic Press, New York, 1972, pp. 109—122.

15.73. D. Brelaz, New Methods to Color the Vertices of a Graph, Comm. ACM, Vol. 22, 251—256 (1979).

15.74. М. C. Pauli and S. H, Unger, Minimizing the Number of States in Incompletely Specified Sequential Switching Functions, IRE Trans. Elect. Comput., Vol. EC-8 , 356—357 (1959).

15.75. C. Bron and J. Kerbosch, Finding All Cliques of an Undirected Graph — Algorithm 457, Comm. ACM, Vol. 16, 575—577 (1973).

15.76. E. A. Akkoyunld, The Enumeration of Maximal Cliques of Large Graphs, SIAM J. Comput., Vol. 2, 1—6 (1973),

15.77. S. Tsukiyama, M. Ide, H. Ariyoshi, and I. Shirakawa, A New Algorithm for Generating All the Maximal Independent Sets, SIAM J. Comput., Vol. 6, 505-517 (1977).

15.78. R. E Tarjan and A. E. Trojanowski, Finding a Maximum Independent Set, SIAM J. Comput., Vol. 6, 537—546 (1977).

15.79. V. Chvatal, Determining the Stability Number of a Graph, SIAM J. Comput., Vol. G, 643—662 (1977).

15.80. J. B. Kruskal, Jr., On the Shortest Spanning Subtree of a Graph and the Travelling Salesman Problem, Proc. Am. Math. Soc., Vol. 7, 48—50 (1956).

15.81. R. C. Prim, Shortest Connection Networks and Some Generalizations, Bell Sys. Tech. J., Vol. 36, 1389—1401 (1957).

15.82. A. Kerschenbaum and R. Van Slyke, Computing Minimum Spanning Trees Efficiently, Proc. 25th Ann. Conf. of the ACM, 1972, 518—527.

15.83. A. C. Yao, An 0(|?|log log|K|) Algorithm for Finding Minimum Spanning Trees, Information Processing Lett., Vol., 4, 21—23 (1975).

15.84. D. Cheriton and R. E. Tarjan, Finding Minimum Spanning Trees, SIAM J. Comput., Vol. 5, 724—742 (1976).

15.85. H. N. Gabow, Two Algorithms for Generating Spanning Trees in Order, SIAM J. Comput., Vol. 6, 139—150 (1977).

15.86. K- P. Esqaran and R. E. Tarjan, Augmentation Problems, SIAM J. Comput., Vol. 5, 653—665 (1976).

15.87. A. Rosenthal and A. Goldner, Smallest Augmentations to Biconnect a Graph, SIAM J. Comput., Vol. 6, 55—66 (1977).

15.88. E. Reghbati and D. G. Corneil, Parallel Computations in Graph Theory, SIAM J. Comput., Vol. 7, 230—237 (1978).

15.89. J. Edmonds, Edge-Disjoint Branching, in Combinatorial Algorithms (R. Rustin, Ed.), Algorithmics Press, New York, 1973, pp. 91—§6.

15.90. D. R. Fulkerson and G. C. Harding, On Edge-Disjoint Branchings, Networks, Vol. 6, 97—104 (1976).

15.91. R. E. Tarjan, Edge-Disjoint Spanning Trees and Depth-First Search, Acta Informatica, Vol. 6, 171—185 (1976).

15.92. L. Lovasz, On Two Minimax Theorems in Graph, J. Combinatorial Theory B, Vol. 21, 96—103 (1976).

15.93. B. L. Golden and T. L. Magnanti, Deterministic Network Optimization: A Bibliography, Networks, Vol. 7, 149—183 (1977).

15.94. M. Fujii, T. Kasami, and K. Ninomiya, Optimal Sequencing of Two Equivalent Processors, SIAM J. Appl. Math., Vol. 17, 784—789 (1969); Erratum, Vol. ?0, 141 (1971).

15.95. E. G. Coffman, Jr., and R. L. Graham, Optimal Scheduling for Two-Processor Systems, Acta Informatica, Vol. 1, 200—213 (1972).

15.96. E. G. Coffman, Jr., and P. J. Denning, Operating System Theory, Prentice Hall, Englewood Cliffs, N.J., 1973.

15.97. R. Sethi, Scheduling Graphs on Two Processors, S/ЛМ J. Comput., Vol. 5, 73—82 (1976).

15.98. R. Sethi, Algorithms for Minimal Length Schedules, in Computers and Job Scheduling Theory (E. G. Coffman, Jr., Ed.), Wiley, New York, 1976, pp. 51—99.

15.99. J. D. Ullman Complexity of Sequencing Problems, in Computer and Job Scheduling Theory (E. G. Coffman, Jr., Ed.), Wiley, New York, 1976, pp. 139—164.

15 100. S. Lam and R. Sethi, Worst Case Analysis of Two Scheduling Algorithms, SIAM J. Comput., Vol. 6, 518—536 (1977).

15.101. D. J. Rose, A Graph-Theoretic Study of Numerical Solutions of Sparse Positive Definite Systems of Linear Equations, in Graph Theory and Computing (R. C. Read, Ed.), Academic Press, New York, 1972, pp. 183—217.

15.102. T. Ohtsuki, A Fast Algorithm for Finding an Optimal Ordering for Vertex Elimination on a Graph, SIAM J. Comput., Vol. 5, 133—145 (1976).

15.103. D. J. Rose, R. E. Tarjan, and G. S. Lueker, Algorithmic Aspects of Vertex Elimination on Graphs, S/ЛУИ J. Comput., Vol. 5, 266—283 (1976).

15.104. R. E. Tarjan, Graph Theory and Gauss Elimination, in Sparse Matrix Computations (J. R. Bunch and D. J. Rose, Eds.), Academic Press, New York, 1976,

15.105. E. Horowitz and S. Sahni, Fundamentals of Computer Algorithms, Computer Science Press, Potcmac, Md., 1978.

15.106. M. R. Garey and D. S. Johnson, Approximation Algorithms for Combinatorial Problems: An Annotated Bibliography, in Algorithms and Complexity: New Directions and Recent Results (J. Traub, Ed.), Academic Press, New York, 1976.

15.107. G. B. Djntzig, All Shortest Routes in a Graph, in Theory of Graphs, Gordon and Breach, New York. 1967, pp. 91—92.

15.108. S. Even, Algorithmic Combinatorics, Macmillan, New York, 1973,