Предложен полиномиальный алгоритм построения одного из Т-неприводимых расширений для многоугольного орграфа. Приведено доказательство корректности алгоритма.
Скачать электронную версию публикации
Загружен, раз: 167
- Title Алгоритм построения Т-неприводимого расширения для многоугольных орграфов
- Headline Алгоритм построения Т-неприводимого расширения для многоугольных орграфов
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 7 (Приложение)
- Date:
- DOI
Ключевые слова
многоугольный орграф, отказоустойчивость дискретных систем, Т-неприводимое расширение, polygonal graph, fault tolerance, T-irreducible extensionАвторы
Ссылки
Салий В. Н. Упорядоченное множество связных частей многоугольного графа //Известия Саратовского университета. 2013. Т. 13. Вып. 2. С. 44-51.
Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2010. Т. 88. №5. С. 643-650.
Салий В. Н. Доказательства с нулевым разглашением в задачах о расширениях графов // Вестник Томского государственного университета. Приложение. 2003. №6. С. 63-65.
Абросимов М. Б. Некоторые вопросы о минимальных расширениях графов // Известия Саратовского университета. Сер. Математика. Механика. Информатика. 2006. Т. 6. Вып. 1/2. С. 86-91.
Hayes J. P. A graph model for fault-tolerant computing systems //IEEE Trans. Comput. 1976. V. С-26. No. 9. P. 875-884.
Курносова С. Г. Т-неприводимые расширения для некоторых классов графов //Теоретические проблемы информатики и её приложений: сб. науч. тр. / под ред. проф. А. А. Сытника. Саратов: Изд-во Сарат. ун-та, 2004. С. 113-125.
Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, Физматлит, 1997. 326 c.
Алгоритм построения Т-неприводимого расширения для многоугольных орграфов | Прикладная дискретная математика. 2014. № 7 (Приложение).
Скачать полнотекстовую версию
Загружен, раз: 1916