Теоретико-графовые модели и методы составления расписаний без прерываний тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Лугуев, Тимур Садыкович

• Лугуев, Тимур Садыкович
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Лугуев, Тимур Садыкович

Введение

1 Графовые модели задачи составления расписания без прерываний

1.1 Задача составления расписаний без прерываний.

1.2 Модель интервальной раскраски графа.

1.3 Модель инциденторной раскраски мультиграфа.

2 Составление расписания без прерываний в случае четного числа требований, запланированных на выполнение для каждого прибора

2.1 Задача проверки существования совершенного расписания как задача дефрагментации матрицы.

2.2 Условия дефрагментации матриц.

2.3 Бездефектный поток и его вычисление

2.4 Поиск кратчайших периодических цепей

3 Потоковые алгоритмы, используемые при проверке условий существования расписаний без прерываний

3.1 Алгоритмы иоиска подграфов максимальной плотности

3.2 Потоковые методы, основанные на увеличивающих путях

3.3 Алгоритмы, основанные на проталкивании предпотока

3.4 Случай несбалансированной двудольной сети.

3.5 Результаты численного эксперимента.

4 Некоторые приложения разработанных методов

4.1 Задача оптимизации расписания передачи информации в беспроводных сенсорных сетях.

4.2 Программа проектирования и анализа беспроводных сетей

4.3 Некоторые МР-полные аспекты задач распознавания

Введение диссертации (часть автореферата) на тему «Теоретико-графовые модели и методы составления расписаний без прерываний»

Актуальность темы

Проблема составления расписания возникает в различных областях науки и техники: в работе сетей передачи данных, при распределении процессорного времени между программами, при формировании расписаний учебных занятий, при составлении расписания движения транспорта и во многих других.

Несмотря на многолетние поиски ряда исследователей, для большинства задач теории расписаний не удается найти точные эффективные алгоритмы. На практике, как правило, используют приближенные и эвристические алгоритмы. Объясняется это тем, что большинство задач составления расписаний относится к классу NP-пoлныx задач, для которых не найдены алгоритмы с полиномиальной вычислительной сложностью. Более того, если известная гипотеза Р^ШР верна, такие алгоритмы не существуют. Поэтому актуальным является рассмотрение подзадач, имеющих важное теоретическое и практическое значение и допускающих решение за полиномиальное время.

В наиболее общей формулировке задача составления расписания состоит в следующем. Заданное множество обслуживающих приборов должно выполнить некоторый фиксированный набор требований. В зависимости от области приложения под парой приборы-требования могут пониматься процессоры-программы, учителя-классы, станки-детали и т.д. Цель заключается в том, чтобы запланировать моменты выполнения требований приборами таким образом, чтобы длина расписания была минимальной.

На практике часто возникает задача составления расписаний для систем, в которых необходимо минимизировать количество стартов-остановок выполнения обслуживающими приборами требований. Интерес к ней обусловлен тем, что затраты ресурсов (временных, энергетических и др.) на данные операции часто сравнимы с затратами на собственно полезную работу устройства.

Расписания, составленные так, что каждый обслуживающий прибор выполняет весь набор своих требований без остановок, называют расписаниями без прерываний. Создание корректных и полных математических моделей и эффективных алгоритмов составления расписаний без прерываний является актуальной задачей. Цель работы

Целью работы является разработка и исследование математических моделей и методов составления оптимальных расписаний без прерываний, анализ вычислительной сложности, построение эффективных алгоритмов составления таких расписаний и рассмотрение компьютерных аспектов проблемы. Для достижения поставленной цели решались следующие задачи:

1. исследование математических моделей составления расписаний без прерываний;

2. разработка алгоритмов полиномиальной вычислительной сложности для поиска оптимального расписания при различных ограничениях на свойства приборов и требований;

3. проведение вычислительных экспериментов для сравнения работы предложенных методов в системах с различным ограничениями на назначение требований приборам.

4. создание комплекса программ, реализующего методы составления расписаний без прерываний для различных областей приложений.

Методы исследования

В диссертационной работе использованы методы математического моделирования, теории вычислительной сложности, теории графов, комбинаторного анализа, теории расписаний. Научная новизна результатов

На основе анализа математических моделей интервальной раскраски графа, пнциденторной раскраски и дефрагментации матриц предложена методика построения математических моделей составления расписаний без прерываний.

При разноплановых ограничениях на исходные данные разработаны новые методы поиска оптимальных расписаний, допускающие полиномиальные оценки вычислительной сложности.

Сформулированы необходимые и достаточные условия составления расписания без прерываний для модельного случая, когда число требований, запланированных каждому прибору па выполнение, - четно, а длина расписания равна шести единицам времени.

Разработан комплекс программ, реализующий алгоритмы составления расписаний без прерываний. Вычислительными экспериментами выявлены численные характеристики предложенных потоковых методов в системах с различным ограничениями на назначение требований приборам.

Разработан комплекс программ для проектирования и анализа беспроводных сенсорных сетей.

Предложен новый подход к решению задач сжатия и передачи информации, использующий модель дефрагментации матриц. Практическая значимость

Предложенные в работе модели и разработанные на их основе подходы способствуют дальнейшему развитию аналитического аппарата теории расписаний и теории графов.

Задача составления расписаний без прерываний тесно связана с вопросами теории алгоритмов и ее наиболее интенсивно развиваемого раздела-теории вычислительной сложности, т.к. в общей формулировке является Ш-'-полной. В этой связи, разработанные в данном диссертационном исследовании алгоритмы полиномиальной сложности могут способствовать исследованию других NP-пoлпыx задач.

Предложенные методы составления расписаний могут быть применены при организации и оптимизации работы беспроводных сенсорных (и других) сетей, в которых энергоэффективность и быстродействие относятся к важнейшим характеристикам при передаче информации.

Основные положения и результаты, выносимые на защиту:

1. методика построения математических моделей, основанных на методах интервальной раскраски графов, раскраски инциденторов и дефрагментации матриц, для составления расписаний без прерываний;

2. методы с полиномиальной вычислительной сложностью, предназначенные для поиска расписаний без прерываний при различных характеристиках исходных данных;

3. необходимые и достаточные условия составления расписания без прерываний для модельного случая, когда длительность всех требований, запланированных каждому прибору на выполнение, - четна, а длина расписания равна шести единицам времени;

4. комплекс программ для проведения вычислительных экспериментов по выявлению численными методами характеристик работы предложенных алгоритмов в системах с различными значен им ми основных параметров;

5. комплекс программ для проектирования и анализа беспроводных сенсорных сетей.

Достоверность научных результатов

Достоверность и обоснованность результатов работы обеспечивается строгими математическими доказательствами, верификацией алгоритмов, вычислительными экспериментами, а также корректным использованием в проведенных исследованиях хорошо апробированных методов математического моделирования, теории алгоритмов и вычислительной сложности, теории графов, комбинаторного анализа, теории расписаний.

С целью исследования реальных границ применимости теоретических положений, а также для выявления и анализа потенциальных проблем их реализации, разработан комплекс программ; экспериментальные исследования для определения практической эффективности предложенных методов составления расписаний проведены на системах больших размеров. Апробация работы

Результаты диссертационной работы и материалы исследований представлялись на: XXIII Международной научной конференции „Математические методы в технике и технологиях - ММТТ-23" (Саратов, 2010 г.);

2. Всероссийских научно-практических конференциях с международным участием „Информационные технологии в профессиональной деятельности и научной работе" (Йошкар-Ола, 2008 и 2010 гг.);

3. IV Всероссийской конференции „Проблемы оптимизации и экономические приложения" (Омск, 2009 г.);

4. X региональной научно-практической конференции „Компьютерные технологии в науке, экономике и образовании" (Махачкала, 2009 г.);

5. VI Всероссийской открытой научно-практической конференции „Актуальные задачи математического моделирования и информационных технологий" (Сочи, 2010 г.);

6. научном семинаре отдела математики и информатики Дагестанского научного центра Российской Академии Наук (Махачкала, 08.04.2010);

Публикации

По материалам диссертации опубликовано 11 печатных работ, в том числе три — в ведущих журналах, рекомендованных ВАК РФ. Личный вклад соискателя

Основные результаты, на которых базируется диссертация, принадлежат соискателю. Все работы, за исключением одной, опубликованы без соавторов. В совместной работе с научным руководителем соискателю принадлежит равное участие в выборе направления исследования, получении и интерпретации результатов, а также разработка алгоритма решения задачи; конфликт интересов отсутствует.

Структура и объем диссертации

Диссертация состоит из введения, четырех глав, заключения и списка литературы. Работа изложена на 105 страницах машинописного текста, включая 16 рисунков, 2 таблицы и библиографию, содержащую 94 названия.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Лугуев, Тимур Садыкович

Основные результаты и выводы

Определены наиболее перспективные модели рассмотрения задачи составления расписаний без прерываний: модель раскраски инциденторов, модель интервальной раскраски графа, модель дсфрагментащш матриц.

В связи с тем, что задача составления расписаний без прерываний является в общей формулировке NP-пoлнoй, исследованы подзадачи исходной задачи, имеющие важное теоретическое и практическое значение.

С использованием модели дефрагментатщи матриц сформулированы необходимые и достаточные условия составления расписания без прерываний для случая, когда длительность выполнения всех требований, запланированных для каждого прибора, четна, а длина расписания равна шести квантам. Разработанный для проверки данных условий алгоритм построения бездефектного потока обладает полиномиальной вычислительной сложностью. Показано, что алгоритм вычисления бездефектного потока основывается на поиске чередующихся путей. Эта задача выделена в самостоятельную задачу и найден эффективный алгоритм поиска кратчайших чередующихся путей.

Разработаны комплексы программ для проведения вычислительных экспериментов, позволяющие сравнивать быстродействие различных потоковых методов, используемых при проверке условий существования расписаний без прерываний, а также модификации методов, описанных в литературе. Выполнена интерпретация полученных результатов.

Установлено, что эффективность вычислений гораздо меньше определяется выбором алгоритма той или иной „теоретической" сложности, чем это принято считать. Значительный вклад привносят такие параметры, как память и быстродействие (типы данных, динамические и статические массивы, используются ли указатели). Зачастую сравнение алгоритмов корректно лишь на сетях, размеры которых и пропускные способности дуг находятся в определенных диапазонах. Указаны приложения разработанных методов:

- разработан комплекс программ для анализа и проектирования беспроводных сенсорных сетей, использующий предложенные в данном диссертационном исследовании методы;

- установлена связь задачи дефрагментации матрицы с элементами 0 и 1 с задачей компактного хранения графических образов;

- определена возможность применения алгоритмов нахождения подграфа максимальной плотности при составлении рейтинга сайтов поисковыми системами.

Рассматриваемая задача составления расписаний без прерываний тесно связана с вопросами теории алгоритмической сложности, т.к. в общей формулировке является ^'Р-пол ной. В этой связи, разработанные, в данном диссертационном исследовании полиномиальные алгоритмы могут дать толчок в исследовании других КР-полных задач.

В заключение считаю своим приятным долгом выразить искреннюю признательность и благодарность моему научному руководителю Абдул-кариму Магомедовичу Магомедову за постоянное внимание и неослабевающий интерес к данной работе и ту неоценимую помощь, которую он оказывал в течение всего периода совместной работы.

Выражаю также благодарность коллективам кафедры дискретной математики и информатики Дагестанского государственного университета и отдела математики и информатики Дагестанского научного центра РАН за интерес к теме моего исследования и полезное участие в обсуждении результатов данной диссертационной работы.

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Лугуев, Тимур Садыкович, 2011 год

1. Ахо А. Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979. - 536 с.

2. Алгулиев P.M., Фаталиев Т.Х., Агаев B.C., Алиев Т.С. Сенсорные сети: состояние, решения и перспективы // Телекоммуникации. 2007. - № 4. - С. 27-33.

3. Альратнайда А. Оптимизация мультизадачного графика по временному критерию //Автореферат диссертации на соискание ученой степени кандидата физико-математических наук. Нальчик, 2000. 16 с.

4. Асратян A.C., Камалян P.P. Интервальные раскраски ребер мульти-графа // Прикладная математика. 1987. - № 5. - С. 25-34.

5. Берж К. Теория графов и ее применения.- М.: Наука, 1962. 319 с.

6. Визинг В.Г., Тофт Б. Раскраска инциденторов и вершин неориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. -2001. Т. 8, № 3. - С. 3-14.

7. Визинг В.Г. Жесткая раскраска инциденторов в неориентированных мультиграфах // Дискрет, анализ и исслед. операций. Сер. 1. 2005. -Т. 12, №3. - С. 48-53

8. Визинг В. Г. Об оценках инциденторного хроматического числа взвешенного ориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2006. - Т. 13, № 4. - С. 18-25.

9. Визинг В. Г. О раскраске ипциденторов в гиперграфе // Дискрет, анализ и исслед. операций. Сер. 1. 2007. - Т. 14, № 3. - С. 40-45.

10. Визинг В. Г. О раскраске ипциденторов в частично ориентированном мультиграфе // Дискрет, анализ и исслед. операций. Сер. 1. 2008. -Т. 15, № 1. - С. 17-22.

11. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.- 416с.

12. Камалян P.P. Интервальные реберные раскраски графов // Автореферат диссертации на соискание ученой степени кандидата физико-математических наук. ИМ СО АН СССР, Новосибирск, 1990. 18 с.

13. Карзанов A.B. Нахождение максимального потока в сети методом пред-потоков // ДАН СССР. 1974. - Т. 215, № 1. - С. 49-53.

14. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. - 432с.

15. Магомедов A.M. Раскраска графа с непрерывным спектром. Деп. в ВИНИТИ №478, 1985. Зс.

16. Магомедов A.M. Дефрагментация матриц перестановок с сохранением наборов элементов в линиях // Проблемы теоретической кибернетики. Тез. докладов XIV Международной конференции. М.: Изд-во МГУ, 2005. - С. 130-131.

17. Магомедов A.M. Жесткий директивный срок для многопроцессорного расписания без прерываний и отношений предшествования // Вестник Дагестанского научного центра. 2007. - № 28. - С. 5-11.

18. Магомедов A.M. К вопросу оптимизации расписания // Известия Волгоградского государственного технического университета: межвуз. сб. науч. ст. 2008. - №5 - С.40-43.

19. Магомедов A.M. К вопросу о реберной раскраске двудольного графа // Дискретная математика.- 2009. Т. 21, №. 2. - С. 153-159.

20. Магомедов A.M. Непрерывное расписание для специализированных процессоров без отношения предшествования // Вестник Московского Энерг. Института, сер. Автоматика, выч.техника, информатика. -2009. №5. - С. 14-17.

21. Магомедов A.M. Уплотнение расписания с директивным сроком, кратным количеству занятий каждого преподавателя // Матем. Заметки. 2009. Т. 85, № 1. - С. 65-72.

22. Магомедов A.M. Дефрагментация таблицы перестановок из четырех столбцов // Дискрет, матем. 2009. - Т. 21, №:4. - С. 95-104.

23. Магомедов A.M. О вычислительной сложности частного случая задачи построения расписания // Тез. докл. X Белорусской математической конференции Часть 5. Институт математики НАН Беларуси. Минск, 2008, С. 92.

24. Магомедов A.M. О модификации характеризации Бержа // Тез. докл.

25. XV международной конференции Проблемы теоретической кибернетики. Казань: Отечество. 2008. С. 77.

26. Майская В. Беспроводные сенсорные сети // Электроника: НТВ. 2005. - №2. - С. 18-22.

27. Молчанов Д.А., Кучерявый Е.А. Приложения беспроводных сенсорных сетей // Электросвязь. 2006. - N 6. - С. 20-23.

28. Новиков А. Дискретная математика для программистов. СПб.: Питер, 2003. - 304с.

29. Ope О. Графы и их применение. М.: Мир, 1965. - 174с.

30. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность М.: Мир, 1985. - 112 с. j

31. Пяткин A.B. Некоторые задачи оптимизации расписания передачи сообщений в локальной сети связи // Дискрет, анализ и исслед. операций. Сер. 1. 1995. - Т/2, № 4. - С. 74-79.

32. Пяткин А. В. (к, 1)-ра,скраска инциденторов кубических мультиграфов // Дискрет, анализ и исслед. операций. Сер. 1. 2002. - Т. 9, № 1. - С. 49-53.

33. Пяткин А. В. Некоторые верхние оценки для инциденторного k, 1)-хроматического числа // Дискрет, анализ и исслед. операций. Сер. 1. -2003. Т. 10, № 2. - С. 66-78.

34. Пяткин А. В. Об(1,1)-раскраске инциденторов мулътиграфов степени4 // Дискрет, анализ и исслед. операций. Сер. 1. 2004. - Т. 11, №3. -С. 59-62.

35. Пяткии A.B. Раскраска инциденторов и другие задачи на графах: алгоритмический аспект. Автореферат диссертации на соискание ученой степени доктора физико-математических наук. Институт математики им. СЛ. Соболева СО РАН, Новосибирск, 2009. 31 с.

36. Сачков В.Н. Введение в комбинаторные методы дискретной математики М.: Наука, 1982. - 384 с.

37. Свами М., Тхуласирамап К. Графы, сети и алгоритмы. М.: Мир, 1984. 456 с.

38. Севастьянов C.B. Об интервальной раскрагциваемости ребер двудольного графа // Методы дискретного анализа в решении экстремальных задач, вып. 50. ИМ СО АН СССР, Новосибирск, 1990. - С. 61-72.

39. Севастьянов C.B. Введение в теорию расписаний. Новосибирск, 2003. -173с.

40. Танаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний: Одностадийные системы М.: Наука, 1984. - 381 с.

41. Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. М.: Наука, 1989. 328 с.

42. Танаев В.С, Ковалев М.Я., Шафранский Я.М. Теория расписаний. Групповые технологии Минск: Ин-т техн. Кибернетики HAH Беларуси, 1998. - 290с.

43. Харари Ф. Теория графов. М.: Мир, 1973. - 300с.

44. Якубов А.З. Некоторые задачи дискретного разбиения и дефрагмента-ции и методы их решения // Автореферат диссертации на соискание ученой степени кандидата физико-математических наук. Саратовский гос. ун-т, Саратов, 2003. 15 с.

45. Aliuja R.K., Orlin J.В., Stein С., and Tarjan R.E. Improved algorithms for bipartite network flow problems. To appear in SI AM Journal on Computing. 1994. - V. 23, N 8. - P. 906-933.

46. Akyildiz I.F. et.al. A survey on wireless multimedia sensor networks// Computer networks. 0ct.2007. - P.75-84.

47. Alt H., Blum N., Mehlhorn K., Paul M. Computing a maximum cardinality matching in a bipartite graph in time 0{n1,b\f(mjlogn)) // Information Processing Letters. 1991. - V. 37, N 4. - P. 237-240.

48. Anderson R.J., and Setubal J.C. Parallel and sequential implementations of maximum-flow algorithms // In Dimacs Implementation Challenge Workshop: Algorithms for Network Flows and Matching. DIMACS Technical Report 92-4. 1992.

49. Asano Т., Asano Y. Recent developments in maximum flow algorithms // Journal of the operations research Society of Japan. 2000. - №43(1). - P. 2-31.

50. Asratian A.S., and Kamalian R.R. Investigation on interval edge-colorings of graphs // J. Combin. Theory. Ser. B. 1994. - V. 62, N 1. - P. 34-43.

51. Asratian A.S., and Casselgren C.J. On interval edge colorings of (o;,/3)-biregular bipartite graphs // Discrete Mathematics. 2007. - V.307. - P. 1951-1956.

52. Asratian A.S., Casselgren C.J., Vandenbussche J., and West D.B. Proper path-factors and interval edge-coloring of (3,4)-biregular bigraphs //J. Graph Theory. 2009. - V. 61. - P. 88-97.

53. Bast H., Mehlhorn K., Schafer G., Tamaki H. Matching algorithms are fast in sparse random graphs // Theory of Computing Systems. 2006. - V.39, N 1. - P. 3-14.

54. Booth K.S. PQ Tree Algorithms. Doctoral Thesis, Dept. of Electrical Engineering and Computer Science, University of California, Berkley C.A. 1975.

55. Booth K.S., Lueker G.S. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms //J. Comput. Systems Sci. 1976. - V. 13, N 3. - P. 335-379.

56. Casselgren CJ., Some results on interval edge colorings of bipartite graphs. Master's Thesis, Linkoping University, Linkoping, Sweden. 2005.

57. Charikar M. Greedy approximation algorithms for finding dense components in a graph // In APPROX, 2000. P. 84-95.

58. Chen Z., Khokhar A. TDM A based Energy Efficient MAC Protocols for Wireless Sensor Networks // IEEE SECON 2004, October 2004. P. 223228.

59. Cook S.A. The complexity of theorem-proving procedures // Proc. 3rd Ann. ACM Symp. on Theory of Computing, Association for Computing Machinery, New York, 1971. P. 151-158.

60. Derigs U., and Meier W. Implementing Goldberg's Max-Flow Algorithm-A Computational Investigation // ZOR-Methods and Models of Operations Research. 1989. - V. 33. - P. 383-403.

61. Dijkstra E.W. A note on two problems in connexion with graphs // Numerische Mathematik.- 1959. N 1. - P. 269-271.

62. Dinic E.A. Algorithm for solution of a problem of maximum flow in networks with power estimation // Soviet Math. Doklady. 1970. - N 11. -P. 1277-1280.

63. Edmonds J., and Karp R.M. Theoretical improvements in algorithmic efficiency for network flow problems // Journal of the ACM. 1972. - V. 19. - P. 248-264.

64. Even S., Itai A., and Shamir A. On the Complexity of Timetable and Multicommodity Flow Problems // SIAM J. on Computing. 1976. - V. 5, N 4. - P. 691-703.

65. Feige U., Kortsarz G., and Peleg D. The dense k-subgraph problem // Algorithmica. 1997. - V.29. - P. 410-421.

66. Ford L.R., Ji. and Fulkerson D.R. Maximal flow through a network // Canad. J. ath. 1956. - N 8. - P. 399-404.

67. Gallo G., Grigoriadis M.D., and Tarjan R.E. A fast parametric maximumflow algorithm and applications // SIAM J. Comput. 1989. - V. 18, N 1. - P. 30-55.

68. Gibson D., Kumar R., and Tomkins A. Discovering large dense subgraphs in massive graphs // In VLDB '05, 2005. P. 721-732.

69. Giaro K., and Kubale M. Consecutive edge-colorings of complete and incomplete Cartesian products of graphs // Proc. 28th Southeastern Int. Conf. Combin., Graph Theory and Computing (Boca Raton, FL, 1997). Congr. Numer. 1997. - V. 128. - P. 143-149.

70. Giaro K. The complexity of consecutive D-coloring of bipartite graphs: 4 is easy, 5 is hard // Ars Combin. 1997. - V. 47. - P.287-298.

71. Giaro K., and Kubale M. Compact scheduling of zero-one time operations in multi-stage systems // Discrete Appl. Math. 2004. - V. 145. - P. 95-103.

72. Goldberg A.V. Finding a Maximum Density Subgraph // Technical Report Identifier: CSD-84-171

73. Goldberg A.V., and Tarjan R.E. A new approach to the maximum How problem // Journal of ACM. 1988. - V. 35. - P. 921-940.

74. Gusfield D., Marl,el C., and Fernandez-Baca D. Fast algorithms for bipartite network flow // SIAM J. Comput. 1987. - V. 16, N 2. - P. 237-251.

75. Gusfield D. Computing the strength of a graph // SIAM J. Comput. 1991. - V. 20, N 4. - P. 639-654.

76. Hajiaghayi M.T., Ganjali Y. A note on the Consecutive Ones Submatrix problem // Information Processing Letters 83. 2002. - P. 163-166.

77. Hansen H. M. Scheduling with minimum waiting periods (in Danish) // Master's Thesis, Odense University, Odense, Denmark, 1992.

78. Hanson D., and Loten C.O.M. A lower bound for interval colouring bi-regular bipartite graphs // Bull. Inst. Combin. Appl. 1996. - V. 18, N 1. - P. 69-74.

79. Hanson D., Loten C.O.M., Toft B. On interval colourings of bi-regular bipartite graphs // Ars Combinat. 1998. - V. 50. - P. 23-32.

80. Hohlt B., Doherty L., Brewer E. Flexible power scheduling for sensor networks // 3rd International Symposium on Information Processing in Sensor Networks, IPSN 2004, April 2004.

81. Hopcroft J. E., and Karp R. M. An n2 5 algorithm for maximum matching in bipartite graphs // SIAM Journal on Computing. 1973. - V. 2, N 2 -P. 225-231.

82. Hoylcr I. The NP-completeness of edge-coloring // SIAM J. Comput. -1981. V. 10, N4. - P. 718-720.

83. LAN MAN Standards Committee of the IEEE Computer Society. Wireless LAN medium access control (MAC) and physical layer (PLIY) specification n// Std. 802.11. NY. - 1997.

84. Lovasz L., Plummer M. D. Matching theory. Budapest: Akadcmiai Kiado, 2009. - 547 c.

85. Melnikov L.S., Vizing V.G. The edge-chromatic number of a directed/mixed multigraph // J. Graph Theory. 1999. - V. 23, № 4. - P. 267-273.

86. Page L., Brin S., Motwani R., and Winograd T. The pagerank citation ranking: Bringing order to the web // Technical report, Stanford University, 1998.

87. Petersen J. Die Theorie der regulären Graphen // Acta Math. 1891. - V. 15. - P. 193-220.

88. Picard J.-C. and Qucyranne M. A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory // Networks. 1982. - V. 12. - P. 141-159.

89. Pottie G.J. Wireless sensor networks // Information Theory Workshop. -1998. P. 139-140.

90. Pyatkin A.V. The incidentor coloring of multigraphs and its applications // Discrete Applied Math. 2002. - V. 120, № 1-3. - P. 209-217.

91. Pyatkin A.V. Interval coloring of (3, 4)-biregular bipartite graphs having large cubic subgraphs // J. Graph Theory. 2004. - V. 47. - P. 122-128.

92. Sahni S. Computationally related problems // SIAM J. Comput. 1974. -V.3, N 2. - P. 262-279.

93. Vishnevskiy V.M. One approach to wireless multimedia sensor network design // International conferences Proceeding, Barcelona, Information and telecommunication's technologies in intelligent systems, Mallorea Spain, 2007. P.8-11.

94. Ullman J.D. Complexity of sequencing Problems // Computer and Job Shop Theory, Coffman G.F., ed. New York: John Wiley, 1976. - P. 139164.