Article

Article title THE INTERACTION AT CONSECUTIVE PERIODS
Authors T.A. Magomedov
Section SECTION VII. BRIEF MESSAGES
Month, Year 06, 2012 @en
Index UDC 519.682
DOI
Abstract The purpose of this paper is to analyze the edge coloring of bipartite biregular interval graph. The article considers the interaction of objects in successive time intervals in accordance with the prescribed operations. Interactions between objects belonging to the same proportion, are excluded. The task scheduling problem is formulated as a proper edge coloring of a graph. An efficient polynomial-time algorithm for recognizing interval edged coloring bipartite biregular graph. Relevant search are special cases, when problems are solvable in polynomial time, and the construction of efficient algorithms for the approximate solute.

Download PDF

Keywords Timetable; bipartite graph; proper edge coloring; interval coloring; NP-completeness .
References 1. Визинг В.Г. Об оценке хроматического класса p–графа // Дискретный анализ. Сб. науч. тр.– Новосибирск: Ин-т математики СО АН СССР, 1964. – Вып. 3. – С. 25-30.
2. Гэрри M., Джонсон Д. Вычислительные машины и труднорешаемые задачи / Пер. с англ. – М.: Мир, 1982. – 416 с.
3. Holyer I. The NP-completeness of edge-coloring // SIAM J. Comput. – 1981. – Vol. 10, № 4. – P. 718-720.
4. Асратян А.С., Камалян Р.Р. Интервальные раскраски ребер мультиграфа // Прикладная математика. – Ереван: Изд-во Ереван. ун-та, 1987. – Вып. 5. – С. 25-34.
5. Севастьянов С.В. Об интервальной раскрашиваемости рёбер двудольного графа // Методы дискретного анализа. – 1990. – Т. 50. – C. 61-72.

Comments are closed.