ГлавнаяАрхивО минимальных вершинных 1-расширениях ориентаций цепей

О минимальных вершинных 1-расширениях ориентаций цепей | Прикладная дискретная математика. 2017. № 38. DOI: 10.17223/20710410/38/6

Исследуются верхняя и нижняя оценки числа дополнительных дуг ec{Pn) минимального вершинного 1-расширения ориентации цепи Pn. Если ориентация цепи iPn имеет концы разного типа и отлична от гамильтоновой, то \{и + 1)/6] +2 ^ ^ ec(Pn) ^ и + 3. Если ориентация цепи ~Pn имеет концы одинакового типа, то Г(и + 1)/4] +2 ^ ec(Pn) ^ и + 3.
  • Title О минимальных вершинных 1-расширениях ориентаций цепей
  • Headline О минимальных вершинных 1-расширениях ориентаций цепей
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 38
  • Date:
  • DOI 10.17223/20710410/38/6
Ключевые слова
минимальное вершинное 1-расширение, вершинная отказоустойчивая реализация, ориентация цепи, minimal vertex extension, node fault tolerance, path orientation
Авторы
Ссылки
Hayes J.P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. V.C.25. No. 9. P.875-884.
Harary F. and Hayes J. P. Node fault tolerance in graphs // Networks. 1996. V. 27. P. 19-23.
Harary F. and Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. V. 23. P. 135-142.
Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2010. №5(88). С. 643-650.
Киреева А. В. Отказоустойчивость в функциональных графах // Упорядоченные множества и решетки. Саратов : Изд-во Сарат. ун-та, 1995. Вып. 11. С. 32-38.
Sung T. Y., Lin C. Y., Chuang Y. C., and Hsu L. H. Fault tolerant token ring embedding in double loop networks // Inform. Process. Lett. 1998. V.66. P.201-207.
Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997. 368 с.
Абросимов М. Б. Графовые модели отказоустойчивости. Саратов: Изд-во Сарат. ун-та, 2012. 192с.
Абросимов М. Б. Минимальные вершинные расширения направленных звезд // Дискретная математика. 2011. Т. 23. №2. С. 93-102.
Абросимов М. Б., Моденова О. В. Характеризация орграфов с малым числом дополнительных дуг минимального вершинного 1-расширения // Изв. Сарат. ун-та. Нов. сер. 2013. Т. 13. Сер. Математика. Механика. Информатика. Вып. 2. Ч.2. С. 3-9.
Абросимов М. Б., Моденова О. В. Характеризация орграфов с тремя дополнительными дугами в минимальном вершинном 1-расширении // Прикладная дискретная математика. 2013. №3. С. 68-75.
О минимальных вершинных 1-расширениях ориентаций цепей | Прикладная дискретная математика. 2017. № 38. DOI: 10.17223/20710410/38/6
О минимальных вершинных 1-расширениях ориентаций цепей | Прикладная дискретная математика. 2017. № 38. DOI: 10.17223/20710410/38/6