Algorithm for constructing T-irreducible extension of polygonal digraphs
Directed graphs are mathematical models of discrete systems. T-irreducible extensions are widely used in cryptography and diagnosis of discrete systems. A polygonal graph is a digraph obtained from a circuit by some orientation of its edges. An algorithm is proposed to construct a T-irreducible extension for a polygonal graph. Correctness of the algorithm is proved.
Download file
Counter downloads: 322
Keywords
многоугольный орграф, отказоустойчивость дискретных систем, Т-неприводимое расширение, polygonal graph, fault tolerance, T-irreducible extensionAuthors
| Name | Organization | |
| Gavrikov A. V. | alexandergavrikov1989@gmail.com |
References
Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, Физматлит, 1997. 326 c.
Курносова С. Г. Т-неприводимые расширения для некоторых классов графов //Теоретические проблемы информатики и её приложений: сб. науч. тр. / под ред. проф. А. А. Сытника. Саратов: Изд-во Сарат. ун-та, 2004. С. 113-125.
Hayes J. P. A graph model for fault-tolerant computing systems //IEEE Trans. Comput. 1976. V. С-26. No. 9. P. 875-884.
Абросимов М. Б. Некоторые вопросы о минимальных расширениях графов // Известия Саратовского университета. Сер. Математика. Механика. Информатика. 2006. Т. 6. Вып. 1/2. С. 86-91.
Салий В. Н. Доказательства с нулевым разглашением в задачах о расширениях графов // Вестник Томского государственного университета. Приложение. 2003. №6. С. 63-65.
Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2010. Т. 88. №5. С. 643-650.
Салий В. Н. Упорядоченное множество связных частей многоугольного графа //Известия Саратовского университета. 2013. Т. 13. Вып. 2. С. 44-51.
