Задачи теории экстремальных графов и их применение при разработке и исследовании алгоритмов синтеза топологической структуры сетей ЭВМ
Диссертация
Практическая ценность. Разработанные в диссертационной работе алгоритмы генерации двусвязных графов с диаметром, не превосходящим 3, а также полученные нижние оценки числа ребер в графах с ограничениями на диаметр и связность, предназначены для решения задачи синтеза топологии сети с ограничениями на надежность. Задача синтеза топологии сети является важной частью практической задачи общей… Читать ещё >
Список литературы
- Белоцерковский Д.Л. Об одной задаче перечисления экстремальных графов // Дискрет, анализ и исслед. операций. Сер. 1. 1998. Т.5, N2. С. 3 — 27.
- Белоцерковский Д.Л. Об одной задаче определения минимального числа ребер в экстремальных графах // Дискрет, анализ и исслед. операций. Сер. 1. 1997. Т.4, N4. С. 98 99.
- Белоцерковский Д.Л., Вишневский В. М. Новый алгоритм генерации остовных двусвязных подграфов для оптимизации топологии сетей передачи данных //
- Автоматика и телемеханика. 1997. N1. С. 108 — 120.
- Белоцерковский Д.Л. Об одной задаче теории экстремальных графов // Сб. труд. 13 школы — семинара по теории массового обслуживания
- BWWQT-97). Минск. 1997. С. 11.
- Белоцерковский Д.Л. Характеризация некоторых экстремальных графов с диаметром, не больше трех // Тез. докл. Второй Сиб. конгресс ИНПРИМ — 96. Новосибирск: Ин — т математики СО РАН. 1996. С. 113.
- Белоцерковский Д.Л. О характеризации некоторых экстремальных графов с диаметром не превосходящим 3 // Проблемы теоретической кибернетики. Тез.докл. XI Междунар.конф. Москва: ГК РФ по ВО. 1996. С. 23 24.
- Вишневский В.М., Савинецкий А. Б., Федотов Е. В. Анализ и реализация одного метода повышения производительности сети пакетной коммутации // АиВТ. 1987. N 2. С. 24 30.
- Вишневский В.М., Талалай А. И. Об одном методе топологического проектирования сети связи // Теория и техника автоматизированных систем массового ослуживания / МДНТП. М., 1982. С. 77 81.
- Вишневский В.М., Федотов Е. В. Оптимизация топологической структуры информационно — вычислительных сетей / / Распределенные автоматизированные системы массового обслуживания. Кишинев: Картямолдавенянскэ. 1987. С. 91 — 93.
- Вишневский В.М., Федотов Е. В. Топологическое проектирование сетей пакетной коммутации // ИППИ РАН. Москва. 1992.
- Диниц Е.А., Зайцев М. А. О генерации помеченных деревьев и разделительных сетей // Алгоритмические исследования в комбинаторике.
- М.: Наука. 1978. С. 100−107.
- Жожикашвили В.А., Вишневский В. М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. М.: Радио и связь. 1988.
- Зайченко Ю.П. Задачи проектирования структуры распределенных вычислительных сетей // АиТ. 1981. N 4. С. 27 40.
- Зыков А.А. Теория конечных графов. Т.1. — Новосибирск: Наука, 1969. — 543с.
- Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979.
- Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.- 321с.
- Макаров А.В. Разработка методов и комплекса программ для проектирования топологии базовых вычислительных сетей с учетом структурной надежности в распределенных АСУ: Автореф. дисс. на соис. уч.ст.канд.техн.наук. М., 1986.- 24с.
- Ope О. Теория графов. М.: Наука, 1968. — 352с.
- Рейнгольд Э., Нивергельдт Ю., Део М. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. — 476с.
- Фараджев И.А. Генерирование неизоморфных графов с заданным распределением степеней вершин // Алгоритмические исследования в комбинаторике. М.: Наука. 1978. С. 11 — 19.
- Федотов Е.В. Алгоритм генерации помеченных графов с заданными свойствами // II — я Всесоюзная школа — семинар по выислительным сетям. Научный совет по комплексной проблеме «Кибернетика» АН СССР. М., 1986. С. 52 54.
- Федотов Е.В. Разработка и исследование алгоритмов синтеза топологической структуры сетей передачи данных автоматизированных систем массового-254обслуживания // ИПУ РАН. Москва. 1988.
- Харари Ф. Теория графов. М.: Мир, 1973.
- Харари Ф., Палмер Э. Перечисление графов. — М.: Мир, 1977.
- Шувиков В.И. Минимальное число ребер в двусвязных графах с заданным диаметром // Принципы построения устройств распределения информации. М.: Наука. 1978. С. 87 90.
- Agrawal D.P. Graph theoretical analysis and design of multistage interconnection networks // IEEE Trans. Comput. 1983. Vol. C-32. P. 637−648.
- Ahlswede R., Gargano L. and others. Fault-tolerant minimum broadcast networks. Networks. 1996. Vol.27, No.4. P. 293 307.
- Ball M.O. Complexity of network reliability computations // Networks. 1980. Vol.10. P. 153−165.
- Ball M.O., Colbourn C.J., Provan J.S. Network reliability // M.O. et al., Eds., Handbooks in OR & MS. 1995. Vol.7, Chapter 11. P. 673−762.
- Belozerkovskii D.L. About a problem of extremal graphical enumeration with diameter at most 3 // International Conference in Informational Networks and Systems ICINAS-96. St. Petersburg. 1996. P. 411−422.
- Belotserkovskii D.L. Characterization of some extremal graphs with diameter no greater than three // Discrete Math. Appl. 1997. Vol.7, No.2. P. 163−176.
- Bermond J.-C., Bollobas B. The diameter of graphs- a survey // Proc. 12-th Southeastern Conference. Congressus Num. 1981. Vol.32. P. 3−27.
- Bermond J.-C., Bond J., Djelloub S. Dense bus networks of diameter 2 // Interconnect. Networks and Mapp. Schedul. Parall. Comput.: DIMACS Workshop.1995. P. 9−18.
- Bermond J.-C., Bond J., Paoli M., Peyrat C. Graphs and interconnection networks: diameter and vulnerability. In surveys in combinatorics: Proc. 9-th British Combinatorial Conference. London Math. Soc., Lec. Notes Ser .1983. Vol.82. P. 1- 30.
- Bremond J.-C., Homobono N., Peyrat C. Large fault-tolerant interconnection networks // Graphs and Combinatorics. 1989. Vol.5. P. 107−123.
- Boesch F.T. Graph theoretic models for network reliability studies // Technical Report 8010, Electrical Engineering and Computer Science Department, Stevens1.st. Tech. Hoboken, New Jersey. 1983.
- Boesch F.T. Large-scale networks: theory and design. New York: IEEE Press. 1976. — 483 p.
- Bollobas В. A problem in the theory of communications networks // Acta Mathematica Acad. Sci. Hung. 1968. Vol.19. P. 75−80.
- Bollobas B. Extremal graph theory. London: Acsd. Press, 1978. — 488p.
- Bollobas B. Graphs of given diameter // Proceedings of Colloquium Held at Tihany. 1968. P. 36−39.
- Bollobas B. Graphs with given diameter and maximal valency // Comb. Math. Appl. D.J.A. Welsh, Ed. Academic Press. New York, N.J. 1969. P. 25−37.
- Bollobas B. Graphs with given diameter and minimal degree // Ars combinatoria. 1976. Vol.2. P. 3−9.
- Bollobas B. Strongly two connected graphs // Congr. Numerantium XYII. Proc. Seventh Southeastern Conf. Combinatorics, Graph Theory, Comput. Baton Rouge, La. F. Hoffman et al., Eds. Utilitas Math. Winnipeg, Manitoba, Canada. 1976. P. 161−170.
- Bollobas B., Eldridge S.E. On graphs with diameter 2 // J. Comb. Theory (B). 1976. Vol.21. P. 201−205.
- Bollobas B., Harary F. Extremal graphs with given diameter and connectivity // Ars Combinatoria. 1976. Vol.1. P. 281−296.
- Bond J., Peyrat C. Diameter vulnerability in networks // Proc. of Kalamazoo Colloquium. 1984. Graph theory and its applications to algorithms and computerscience. P. 123−149. New York, Wiley 1985.
- Bondy J.A., Murty U.S.R. Extremal graphs of diameter 2 with prescribed minimum degree // Stud. Sci. Math. Hung. 1972. Vol.7. P. 239−241.
- Bondy J.A., Murty U.S.R. Graph theory with applications. Macmillan, London, England, 1976.
- Bondy J.A., Murty U.S.R. Graph theory with applications. North-Holland, New York, 1980. — 44p.
- Boorstyn R.R., Frank H. Large-scale network topological optimization // IEEE Trans, on Commun. 1977. Vol.25, No.l. P. 29−47.
- Bukowski J.V. On the determination of large scale system reliability // IEEE Trans. Syst. Man Cybern. 1982. Vol. SMC-12. P. 538−548.
- Caccetta L. Characterization of extremal graph of diameter 4 II // Ars combinatoria. 1979. Vol.7. P. 301−317.
- Caccetta L. Extremal graphs of diameter 3 // J. Austral. Math. Society. 1979. Vol. A28, No. 1. P. 63−84.
- Caccetta L. Extremal graphs of diameter 4 // J. Combinatorial Theory. 1976. Vol. B21, No. 1. P. 104−115.
- Caccetta L. On extremal graphs with given diameter and connectivity // Annals of New York Acad, of Sci. Topics in graph theory. 1979. Vol.328. P. 76−94.
- Caccetta C. On extremal graphs // Proc. Eighth Southeastern Conf. Comb. Graph
- Theory and Comput., Baton Rouge, La., F. Hoffman et al., Eds. Utilitas Mathematica Publishing. 1977. P. 125−137.
- Caccetta C., Haggkvist R. On diameter critical graphs // Discrete Math. 1979. Vol.28. P. 223−229.
- Caccetta C., Kraetzl M. Blocking probabilities of certain classes of channel graphs // V.R. Kulli (ed.), Advances in Graph Theory. Vishwa International, Deily. 1991. P. 70−103.
- Chartrand G. A graph theoretic approach to a communications problem // SIAM J. Appl.Math. 1966. Vol.14. P.778−781.
- Chudnovsky D.V., Chudnovsky G.V., Denneau M.M. Regular graphs with small diameter as models for interconnection networks // 3rd Int. Conf. on Supercomputing Boston. 1988. P. 232−239.
- Chung F.R.K. Diameter of communication networks // Proceedings of Symposia in Applied Mathematics. 1986. Vol.34. P. 1−18.
- Chung F.R.K. Graphs with small diameter after edge deletion. 1988. Preprint.
- Colbourn C.J., Lomonosov M.V. Renewal networks: connectivity and reliability on atime interval // Probab. Engrg. Inf. Sci. 1991. Vol.5. P. 361−368.
- Doty K.W. New designs for dense processor interconnection networks // IEEE Trans, on Comput. 1984. Vol. C-33, No.5. P. 447−450.
- Erdos P., Renyi A. Assymmetric graphs // Acta Math. Acad. Sci. Hungar. 1963. Vol.14, P. 295−315.
- Erdos P., Fajtlowicz, Hoffman A.J. Maximum degree in graphs of diameter 2 // Networks. 1980. Vol.10. P. 87−90.
- Esfahanian A.H. Lower-bounds on the connectivities of a graph //J. Graph Theory.1985. Vol.9. P. 503−511.
- Esfahanian A.H., Hakimi S.L. On computing the connectivities of graphs and digraphs // Networks. 1984. Vol.14. P. 355−366.
- Myrvold W.J., K.H. Cheung, L. Page and J. Perry. Uniformly relliable graphs donot always exist // Networks. 1991. Vol.21. P. 417−419.
- Frank H., Chou W. Routing in computer networks // Networks. 1971. Vol.1, No.l. P. 99−122.
- Frank H., Frish I.T., Chou W. Topological considerations in the design of the ARPA computer network // AFIPS Conf. (Montvale, New Jersey, 1970). New York: AFIPS Press. 1970. Vol.36. P. 581−587.
- Gerla M. Approximations and bounds for the topological design of distributed computer networks // 4 th Data Commun. Sym. New York. 1975. P. 4/9−4/15.
- Gerla M., Kleinrock L. On the design of distributed computer networks //IEEE-257
- Trans. on Commun. 1977. Vol.25, No.l. P. 48−53.
- Glivjak F. On the impossibility to construct diametrically critical graphs by extensions //Arch. Math. (Brno). 1975. Vol.11. P. 131−137.
- Goemans M.X., Coldberg A.V., Plotkin S. and others. Improved approximation algorithms for network design problems // Proc. 5th Annu. ACM-SIAM symp. Discrete Algorithms, Arlington. 1994. P. 223 232.
- Goldsmith D.L. On the N-th order edge-connectivity of a graph // Congressus Numerantium. 1981. Vol.32. P. 375−382.
- Goldsmith D.L., Entringer R.C. A sufficient condition for equality of edge-connectivity and the minimum degree of a graph //J. Graph Theory. 1979. Vol.3. P. 251−255.
- Goldsmith D.L., White A.T. On graphs with equal edge-connectivity and minimum degree // Discrete Math. 1978. Vol.23. P. 31−36.
- Imase M., Soneoka T., Okada K. Connectivity of directed regular graphs with small diameter // IEEE Trans, on Comput. 1985. Vol. C-34. P.267−274.
- Kel’mans A.K. The graph with the maximum probability of remaining connected depends on the edge-removal probability//Graph Theor Newslett. 1979. Vol.9.P.2−3.
- Lomonosov M.V., Polesskii V.P. Lower bound of network reliability // Probl. Inf. Transm. 1972. Vol.8. P. 118−123.
- Madhumangal Pal, Bhattacharjee G.P. A data structure on interval graphs and its applications //J. Circuits, Systems and Computers. 1997. Vol.7, No.3. P. 165−175.
- Murty U.S.R. Critical graphs of diameter 2 // Math. Mag. 1968. Vol.41. P. 138−140.
- Murty U.S.R. «Extremal Graph Theoretic Problems with Applications». Ph.D.Thesis. Calcutta. 1966.
- Murty U.S.R. Extremal nonseparable graphs of diameter 2 // Proof Techniques in Graph Theory. (F. Harary, Ed.). Academic Press, New York, 1969.
- Murty U.S.R. On some extremal graphs // Acta Mathematica Acad. Sci. Hung. 1968. Vol.19. P. 67−74.
- Peyrat C. Diameter vulnerability of graphs // Discrete Appl. Math. 1984. Vol.9. P. 245−250.
- Plesniak J. Critical graphs of given diameter // Acta. Fac. Rerum Natur. Univ. Comenian Math. 1975. Vol.30. P. 71−93.
- Plesniak J. The complexity of designing a network with minimum diameter // Networks. 1981. Vol.11. P. 77−85.
- Provan J.S. Bounds on the reliability of networks // IEEE Trans. Reliab. 1986. Vol. R-35. P. 260−268.
- Qiao Li, Yi Zhang. Restricted connectivity and restricted fault diameter of someinterconnection networks // Interconnect. Networks and Mapp. Schedul. Parall. Comput.: DIMACS Workshop. 1995. P. 267−273.
- Schumacher U. An algorithm for construction of a k-connected graph with minimum number of edges and quasiminimal diameter // Networks. 1984. Vol.14. P. 63−74.
- Steiglitz K., Weiner W., Kleitman D.J. The design of minimum cost survivable networks // IEEE Trans. Circuit Theory. 1969. Vol. CN-16, No.4. P. 445−460.
- Toueg S., Streiglitz K. The design of small-diameter networks by local search // IEEE Nrans. Comput. 1979. Vol. C-28. P. 537−542.
- Usami Y. Extremal graphs of diameter at most G after deleting onvy vertex //J. Graph Theory. 1985. Vol.9, No.2. P. 221−234.
- Usami Y. Extremal graphs of diameter at most 8 after any vertex // Utilitas Mathematica. 1986. Vol.3. P. 153−180.
- Vijay an K., Murty U.S.R. On accessibilityin graphs//Saukhya. 1964. Vol.26. Ser.A. P. 279−302.
- Vishnevsky V.M., Belotserkovski D.L. On an algorithm of topological optimization of data networks // Proceedings of the International Conference DCCN. Theoryand Applications. Tel-Aviv (Israel). 1996. P. 131−138.
- Vishnevsky V., Fedotov E. Generation of biconnected graphs with given properties// 16th IFIP Conference on System Modelling and Optimizition, Compiegne (France). 1993. Vol.2. P. 553−557.
- Wang D.L., Kleitman D.L. On the existence of n-connected graphs with prescribeddegrees (n > 2) // Networks. 1973. Vol.3, No.2. P. 225−239.
- Wittie L.D. Communication structures for large networks of microcomputers //
- EE Trans. Comput. 1981. Vol. C-30. P. 264−273.