Для цитирования:
Комаров Д. Д. Минимальные вершинные 1-расширения пальм // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2014. Т. 14, вып. 2. С. 233-241. DOI: 10.18500/1816-9791-2014-14-2-233-241, EDN: SHHIGN
Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн:
09.06.2014
Полный текст:
(downloads: 202)
Язык публикации:
русский
Рубрика:
УДК:
519.17
EDN:
SHHIGN
Минимальные вершинные 1-расширения пальм
Авторы:
Комаров Дмитрий Дмитриевич, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Аннотация:
Минимальные вершинные 1-расширения графов можно рассматривать как модель оптимальной вершинной 1-отказоустойчивой реализации некоторой системы. Эта работа посвящена вершинным 1-расширениям графов специального класса – класса пальм. Приводится решение задачи нахождения минимального вершинного 1-расширения для двулистных пальм.
Ключевые слова:
Список источников:
- Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. Vol. C.25, № 9. P. 875—884.
- Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Мат. заметки. 2010. Т. 88, № 5. С. 643–650. DOI: 10.4213/mzm8403.
- Абросимов М. Б. Графовые модели отказоустойчивости. Саратов : Изд-во Сарат. ун-та, 2012. 192 с.
- Harary F., Khurum M. One node fault tolerance for caterpillars and starlike trees // Internet J. Comput. Math. 1995. Vol. 56. P. 135—143.
- Абросимов М. Б. О числе дополнительных ребер минимального вершинного 1-расширения сверхстройного дерева // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2012. Т. 12, вып. 2. С. 103–113.
Поступила в редакцию:
10.11.2014
Принята к публикации:
21.04.2014
Опубликована:
30.05.2014
Краткое содержание:
(downloads: 104)
- 1077 просмотров