ГлавнаяАрхивИнтервальная на одной доле правильная реберная 5-раскраска двудольного графа

Интервальная на одной доле правильная реберная 5-раскраска двудольного графа | Прикладная дискретная математика. 2011. № 3(13).

Пусть в двудольном графе G = (X, Y, E) степень каждой вершины в X равна 2,наибольшая степень вершины в Y равна 5. Найдены условия существования пра-вильной реберной 5-раскраски графа G, интервальной на множестве X.
  • Title Интервальная на одной доле правильная реберная 5-раскраска двудольного графа
  • Headline Интервальная на одной доле правильная реберная 5-раскраска двудольного графа
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 3(13)
  • Date:
  • DOI
Ключевые слова
NP-полнота, двудольный граф, рёберная раскраска, bipatite graph, edge-coloring, NP-completeness
Авторы
Ссылки
Магомедов А. М. Об одной специальной реберной 2-раскраске // Научно-технические ведомости СПбГПУ. Cер. Информатика. Телекоммуникации. Управление. Раздел «Математическое моделирование: методы, алгоритмы, технологии». 2011. №2(120). С. 156-159.
Магомедов А. М. Два частичных паросочетания в двудольном графе специального вида // Материалы X Междунар. семинара «Дискретная математика и ее приложения» (Москва, МГУ, 1-6 февраля 2010 г.) / под ред. О.М. Касим-Заде. М.: Изд-во мехмата МГУ, 2010. С. 312-313.
Goldberg A. V. Finding a maximum density subgraph. Berkeley: University of California / Technical Report UCB/CSD 84/171, CA. 1984.
Asratian A. S. and Casselgren C. J. Some results on interval edge colorings of (a, в)-biregular bipartite graphs // Department of Mathematics, Linkoping University S-581 83. Linkoping, Sweden, 2007.
Pyatkin A. V. Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs // J. Graph Theory. 2004. V. 47. No. 2. P. 122-128.
Jensen T.R. and ToftB. Graph coloring problems. New York: Wiley-Interscience series in discrete mathematics and optimization, 1995.
Hanson D., Loten C. O. M., and Toft B. On interval colourings of bi-regular bipartite graphs // Ars Combinat. 1998. V.4. P. 23-32.
Hansen H. M. Scheduling with minimum waiting periods (in Danish) // Master Thesis. Odense University. Odense, Denmark, 1992.
Магомедов А. М., Рашайда А. Матрица расписания с двумя ненулевыми элементами в строке // Вестник Дагестанского госуниверситета. 1999. Вып. 4. C. 12-15.
Giaro K. The complexity of consecutive Д-coloring of bipartite graphs: 4 is easy, 5 is hard // Ars Combin. 1997. V. 47. P. 287-298.
Магомедов А. М. Непрерывное расписание для специализированных процессоров без отношения предшествования // Вестник Московского энергетического института. 2009. №5. С. 14-17.
Асратян А. С., Камалян Р. Р. Интервальные раскраски ребер мультиграфа // Прикладная математика. Ереван: Изд-во Ереван. ун-та, 1987. Вып. 5. С. 25-34.
Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии: пер. с англ. М.: Мир, 1998.
Holyer J. The NP-completeness of edge-colorung // Siam J. Comput. 1981. V. 10. No. 4. P. 718-720.
Garey M. R. and Johnson D. S. Computers and Intractability. San Francisco: W. H. Freeman and Company, 1979.
Tait P. G. Remarks on the previous communication // Proc. Roy. Soc. Edin. 1880. V. 10. P. 729.
Tait P. G. Note on a theorem in the geometry of position // Trans. Roy. Soc. Edin. 1880. V. 29. P. 657-660.
Визинг В. Г. Об оценке хроматического класса р-графа // Дискретный анализ. Новосибирск: Институт математики СО АН СССР, 1964. Вып. 3. С. 25-30.
Свами М., Тхуласираман K. Графы, сети и алгоритмы. М.: Мир, 1984.
Интервальная на одной доле правильная реберная 5-раскраска двудольного графа | Прикладная дискретная математика. 2011. № 3(13).
Интервальная на одной доле правильная реберная 5-раскраска двудольного графа | Прикладная дискретная математика. 2011. № 3(13).
Полнотекстовая версия