Приведены алгоритмы построения Т-неприводимых расширений (ТНР) для объединения некоторых типов орграфов, а именно для объединения ориентированных цепей, объединения орграфа с его ТНР, а также ТНР для направленных звезд. Каждый из предложенных алгоритмов имеет полиномиальную асимптотическую сложность. Доказана корректность этих алгоритмов.
Скачать электронную версию публикации
Загружен, раз: 62
- Title Т-неприводимые расширения объединений некоторых типов орграфов
- Headline Т-неприводимые расширения объединений некоторых типов орграфов
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 4(22)
- Date:
- DOI
Ключевые слова
TIE for directed stars, union of paths, union of some types digraphs, minimal T-irreducible extension, TIE, T-irreducible extension, направленные звёзды, объединения ориентированных цепей, объединения некоторых типов орграфов, ТНР, минимальные Т-неприводимые расширения, Т-неприводимые расширенияАвторы
Ссылки
Курносова С. Г. Т-неприводимое расширение для симметричных ориентаций цепей // Теоретические проблемы информатики и ее приложений: сб. науч. тр. / под ред. проф. А.А. Сытника. Саратов: Изд-во Сарат. ун-та, 2006. С. 76-81.
Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2010. Т. 88. №5. С. 643-650.
Салий В. Н. Доказательства с нулевым разглашением в задачах о расширении графов // Вестник Томского государственного университета. Приложение. 2003. №6. С. 63-65.
Курносова С. Г. Т-неприводимые расширения для некоторых классов графов // Теоретические проблемы информатики и её приложений: сб. науч. тр. / под ред. проф. А. А. Сытника. Саратов: Изд-во Сарат. ун-та, 2004. С. 113-125.
Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, Физматлит, 1997. 368 с.
Т-неприводимые расширения объединений некоторых типов орграфов | Прикладная дискретная математика. 2013. № 4(22).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 338