Минимальные рёберные расширения графов можно рассматривать как модель оптимальной рёберной отказоустойчивой реализации некоторой системы. Работа посвящена верхней оценке количества дополнительных рёбер минимальных рёберных 1-расширений для графов специального вида - сверхстройных деревьев. Приводятся две схемы построения рёберного 1-расширения для сверхстройного дерева произвольного вида и соответствующий алгоритм на основе этих схем.
Скачать электронную версию публикации
Загружен, раз: 292
- Title Верхняя оценка количества дополнительных рёбер минимальных рёберных 1-расширений сверхстройных деревьев
- Headline Верхняя оценка количества дополнительных рёбер минимальных рёберных 1-расширений сверхстройных деревьев
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 4(30)
- Date:
- DOI
Ключевые слова
графы, минимальные расширения графов, сверхстройное дерево, отказоустойчивость, graphs, minimal extensions of graphs, fault tolerance, starlike treesАвторы
Ссылки
Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2010. Т. 88. №5. С. 643-650.
Абросимов М. Б. О нижней оценке числа ребер минимального реберного 1-расширения сверхстройного дерева // Изв. Сарат. ун-та. Нов. сер. Математика. Механика. Информатика. 2011. Т. 11. Вып. 3. Ч.2. С. 111-117.
Harary F. and Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. No. 23. P. 135-142.
Абросимов М. Б. Графовые модели отказоустойчивости. Саратов: Изд-во Сарат. ун-та, 2012. 192 с.
Абросимов М. Б., Комаров Д. Д. Минимальные реберные расширения сверхстройных деревьев с малым числом вершин. Саратов, 2010. 27с. Деп. в ВИНИТИ 18.10.2010 №589-В2010.
Верхняя оценка количества дополнительных рёбер минимальных рёберных 1-расширений сверхстройных деревьев | Прикладная дискретная математика. 2015. № 4(30).
Скачать полнотекстовую версию
Загружен, раз: 774