Рассматриваются минимальные реберные k-расширения графов, которые получаются из звездного графа произвольной ориентацией ребер. Ранее было получено полное решение, описывающее минимальные вершинные и реберные k-расширения неориентированных звезд, а также минимальные вершинные k-расширения ориентированных звезд. В этой работе дается полное описание всех минимальных реберных k-расширений для ориентированных и направленных звезд.
Скачать электронную версию публикации
Загружен, раз: 69
- Title Минимальные реберные расширения направленных и ориен-тированных звезд
- Headline Минимальные реберные расширения направленных и ориен-тированных звезд
- Publesher
Tomsk State University
- Issue Прикладная дискретная математика 2(12)
- Date:
- DOI
Ключевые слова
fault tolerance, minimal edge extension, звездные графы, star graph, отказоустойчивость, оптимальная отказоустойчивая реализация, минимальное расширениеАвторы
Ссылки
Абросимов М. Б. Минимальные расширения транзитивных турниров // Вестник Томского госуниверситета. Приложение. 2006. № 17. С. 187-190.
Абросимов М. Б. Минимальные k-расширения предполных графов // Изв. вузов. Математика. 2003. №6(493). С. 3-11.
Абросимов М. Б. Минимальные расширения неориентированных звезд // Теоретические проблемы информатики и ее приложений. Саратов: СГУ, 2006. Вып. 7. С. 3-5.
Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2010. №5(88). С. 643-650.
Sung T. Y., Lin C. Y., Chuang Y. C., and Hsu L. H. Fault tolerant token ring em-bedding in double loop networks // Inform. Process. Lett. 1998. V. 66. P. 201-207.
Harary F. and Hayes J. P. Node fault tolerance in graphs // Networks. 1996. V. 27. P. 19-23.
Киреева А. В. Отказоустойчивость в функциональных графах // Упорядоченные множества и решетки. Саратов, 1995. Вып. 11. С. 32-38.
Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. V.C25. No. 9. P. 875-884.
Harary F. and Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. V. 23. P. 135-142.
Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997.

Минимальные реберные расширения направленных и ориен-тированных звезд | Прикладная дискретная математика. 2011. № 2(12).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 195