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

• Турсунбай кызы, Ырысгул
• кандидат физико-математических наук
• 2011

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

ВВЕДЕНИЕ.

ГЛАВА 1. ДИНАМИЧЕСКИЕ АЛГОРИТМЫ ДЛЯ РАСПОЗНАВАНИЯ И ПРЕДСТАВЛЕНИЯ КЛАССОВ ГРАФОВ.

1.1. Деревья клик хор дальнего графа и деревья подграфов в теории графов.

1.1.1. Деревья клик.

1.1.2. Деревья подграфов.

1.1.3: Строгие деревья подграфов.18.

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

1.2.1. Добавление полного г-вершинника Кг.

1.2.2. Удаление полного г-вершинника Кг.

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

Выводы.

ГЛАВА 2. РАСКРАСКА ГРАФ-МОДЕЛЕЙ В КЛАССЕ ПАРАЛЛЕЛЬНЫХ ЛОКАЛЬНЫХ АЛГОРИТМОВ.

2.1. Локальные алгоритмы.

2.2. Модель вычислений.

2.3. Алгоритм жадной раскраски в контексте локальных алгоритмов.

2.4. Обзор распределенных алгоритмов раскраски графов.

2.5. Локальный алгоритм для раскраски м>- совершенных графов.

2.6. Разновидности раскраски графов.

2.6.1. Т-раскраска графов.

2.6.2. Суммирующая раскраска графов.

Выводы.

ГЛАВА 3. ЛОКАЛЬНЫЙ АЛГОРИТМ ДЛЯ НАХОЖДЕНИЯ ЦЕНТРОВ И МЕДИАН ГРАФОВ.

3.1. Центральность.

3.2. Минимаксные и минисуммные задачи размещения.

3.3. Распределенные системы.

3.4. Модель вычислений.

3.5. Новый алгоритм нахождения центров и медиан.

3.6. Базовые алгоритмы и их модификации.

3.6.1. Проверка связности.

3.6.2. Алгоритм нахождения кратчайших расстояний.

3.6.3. Выбор лидера.

3.6.4. Модификации алгоритмов.

3.7. Моделирующая программа.

Выводы.

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

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

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

Основным предметом изучения в диссертации являются различные задачи из теории графов, каждая из которых является по-своему актуальной. Во многих приложениях, графы подчинены дискретным изменениям, таким как добавление или удаление вершин или ребер. В последние десятилетия возрос интерес к динамически меняющимся графам, было разработано много алгоритмов и структур данных для динамических графов. Имеются теоретические и практические причины изучать специальные классы графов и возможно чрезвычайно полезно исследовать проблемы графовых алгоритмов вначале на специальных классах графов. Это приводит к важной проблеме распознавания, когда относительно каждого типа X интересуются: принадлежит ли данный граф типу ХР. В диссертации впервые рассматривается задача распознавания и представления хордальных и расщепляемых графов, когда элементом добавления или удаления служит полный г-вершинный граф Кг. Данная задача возникла при исследовании соавторских связей [104] и была сформулирована Евстигнеевым В.А. Важную роль в исследуемой задаче играет понятие «центральности», которое будет рассмотрено далее.

Другой интересной задачей в теории графов является раскраска графов. Поскольку задача определения хроматического числа принадлежит классу ЫР-полных задач, исследования в этой области ведутся в разных направлениях, среди которых большое место занимает изучение зависимости хроматического числа X(G) от различных характеристик графа таких, как плотность <p(G), вырожденность (число Секереша-Вилфа) co(G), а также выявление и исследование классов графов, для которых задача раскраски полиномиально разрешима.

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

В применении задачи нахождения центров и медиан графов возникают два интересующих нас направления: первое направление связано с понятием «центральности» графа, которое находит свое применение в социальных сетях, сетях цитирования, гипертекстовых и других сетях при составлении рейтинга узлов. Например, модель случайного блуждания показывает себя эффективной применительно к поведению пользователя, путешествующего по связям-ссылкам гипертекстовой сети. Она заложена в популярной поисковой системе Google, в ее методе получения рейтинга страниц Всемирной Паутины. Узлы (вэб-страницы), принадлежащие центру или медиане - это "авторитеты", в которые сеть чаще всего приводит путешественников.

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

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

Цель работы

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

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

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

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

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

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

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

Научная новизна

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

Разработаны параллельные локальные алгоритмы для раскраски несовершенных графов, для Г-раскрасок и суммирующих раскрасок граф-моделей. Показана оптимальность алгоритмов применительно к несовершенным, двудольным, полным А:-дольным графам, двойным звездам и двудольным колесам.

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

Практическая ценность

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

Апробация работы

Основные идеи и конкретные результаты диссертационной работы обсуждались на следующих конференциях и семинарах: конференции-конкурсе «Технологии Microsoft в информатике и программировании» (Новосибирск, 2005), XLIII Международной научной студенческой конференции «Студент и научно-технический прогресс» (Новосибирск, 2005), VI Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям (Кемерово, 2005), XIII Международной конференции студентов, аспирантов и молодых ученых «Ломоносов-2006 (Москва, 2006), Международной конференции «Развитие вычислительной техники в России и странах бывшего СССР: история и перспективы (SORUCOM 2006)», (Петрозаводск, 2006), International Andrei Ershov Memorial Conference on Perspectives System Informatics (Novosibirsk, Russia, 2006), Семинары лаборатории «Конструирования и оптимизации программ», Новосибирск, ИСИ СО РАН, 2003 - 2009.

Публикации

Основные результаты диссертационной работы опубликованы в 12 работах, среди которых 7 статей, 2 [112, 110] из них в рецензируемых журналах.

Исследования выполнялись в соответствии с планами научно-исследовательских работ ИСИ СО РАН и частично были поддержаны грантами РФФИ (№ 09-01-90901-мобснгст, № 11-01-90901-мобснгст).

Объем и структура диссертации. Диссертационная работа состоит из введения, трех глав и списка литературы. Объем диссертации - 92 стр. Список литературы содержит 126 наименований.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Турсунбай кызы, Ырысгул

Основные результаты, полученные в ходе диссертационной работы.

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

- - - ~ ~реализоватьновью локальные и динамические алгоритмы для их анализа.

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

3. Разработаны и реализованы алгоритмы для вершинной раскраски графов в рамках локальной модели вычислений:

ПН-алгоритм для раскраски ^--совершенных графов. Данный алгоритм оптимально или почти оптимально красит графы из класса ^-совершенных графов.

ВБАТТЖ (НПН)-алгоритм для Г-раскраски графов, который оптмально красит все двудольные графы для произвольных множеств Т.

Обратный НП-алгоритм для суммирующей раскраски графов. Показано, что данный алгоритм оптимально или почти оптимально красит А>дольные графы, двудольные колеса и двойные звезды.

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

ЗАКЛЮЧЕНИЕ

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

1. Acharya B.D., Las Vergnas M. Hypergraphs with cyclomatic number zero, triangulated graphs, and an inequality. - Journal of Combinatorial Theory (Series B), 1982. - Vol.33. - P. 52-56.

2. Allen S. M., Smith D. H., Hurley S. Lower bounding techniques forfrequencyassignment, Discrete Mathematics, 1999. - Vol. 197-198. - P.4152.

3. Arnborg S., Lagergren J. Easy problems for tree decomposable graphs. J. of Algorithms, 1991. - Vol.12. - P. 308-340.

4. Averbuch B. A new distributed depth-first-search algorithm // Inf. Process. Lett. 1985. - Vol.20, N 3. - P.147-150.

5. Barbosa V.C. An introduction to distributed algorithm. MIT Press, Cambridge, MA, 1996.

6. Bar-Noy A., Bellare M., Halldorsson M. M., Shachnai H., Tamir T. On chromatic sums and distributed resource allocation. Information and computing. - 1998. - Vol.140. - P. 183-202.

7. Barrett W.W., Johnson C.R., Lundquist M. Determinantal formulae for matrix completions associated with chordal graphs. Linear Algebra Appl, 1989.-Vol.121.-P. 265-289.

8. Battiti R., Bertossi A.A., Bonuccelli M.A. Assigning codes in wireless networks. Wireless Networks, 1999. N.5. - P. 195-209.

9. Bellare M., Goldreich O., Sudan M. Free bits, PCPs and non-approximability towards tight results. - SIAM J. Сотр., 1998. - Vol.27. -P.804-915.

10. Bernstein P.A., Goodman N. Power of natural semijoints. SIAM. J. Comput., 1981.-Vol.10.-P. 751-771.

11. Berry A., Heggernes P., Villanger Y. A vertex incremental approach for dynamically maintaining chordal graphs. Discrete Mathematics, 2006. -Vol. 3063.-P. 318-336.

12. Bertsekas D.P., Tsitsiklis J.N. Parallel and distributed computation.1. McGraw-Hill, 1996^

13. Branstadt A., Dragan F.F., Chepoi V.D., Voloshin V.I. Dually chordal graphs. SIAM J. Discrete Mathematics, 1998. - Vol.11. - P. 437-455.

14. Brelaz D. New methods to color the vertices of a graph. Communications of the ACM. 1979. - V.22.N.4. - P.251 - 256.

15. Brin S., Page L. The anatomy of a large-scale hypertextual Websearch engine. Proc. of the 7-th WWW Conference. - Brisbane, Australia, 1998. -P. 107-117.

16. Bruell S. C., Ghosh S., Karaata M. H., Pemmaraju S. V. Self-stabilizing algorithms for finding centers and medians of trees. SIAM Journal on Computing, 1999 - Vol. 29. - P.600-614.

17. Buneman P. A characterization of rigid circuit graphs. Discrete Math, 1974. - Vol. 9.-P. 205-212.

18. Chandy K.M., Mistra J. Distributed computation on graphs: shortest path algorithms // Com. ACM. 1982. - Vol. 25, N 11. - P. 833-837.

19. Chang E.G. Decentralized algorithms in distributed systems. Tech. Rep. CCRG-103. - Computer Systems Research Group, University of Toronto, 1979.

20. Chang E.J.H. Echo-algorithms: depth parallel operations on general graphs // IEEE Trans. On Software Eng. 1982. - Vol. SE-8, N 4. - P. 391-401.

21. Chelnokov V.M., Zephyrova V.L. Collective phenomena in hypertext networks. Proc. of the Hypertext'97 Conference (Southampton, UK). -ACM, 1997.-P. 220-221.

22. Chelnokov V.M., Zephyrova V.L. Hypertext macrodynamics. Lecture Notes Comput. Sci. - Berlin: Springer-Verlag, 1995 - Vol. 1015. - P. 105120.

23. Cole R., Vishkin U. Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking. Inf. Control, 1986. - Vol.70. N.l. - P.32-53.- — -25CostaD. ,Onthe use of some known methods for T-colorings of graphs.

24. Annals of Operations Research, 1993. - Vol.41. N.4. - P.343-358.

25. Cozzens M. B., Roberts F. S. T-colorings of graphs and the channel assignment problem. Congressus Numerantium, 1982. - Vol.35. - P. 191-208.

26. Deng X., Hell P., Huang J. Recognition and representation of proper circular arc graphs. Proc. of the 2nd Integer Pogramming and Combinatorial Optimization (IPCO). - Carnegie Mellon University, Pittsburg, PA, 1992. - P. 114-121.

27. Djastra E.W., Scholton C.S. Termination detection for diffusing computations // Inf. Process. Lett. 1980. - V. 11, N 1. - P. 1-4.

28. Dragan F.F., Voloshin V.I. Incidence graphs of biacyclic hypergraphs. -Discrete Applied Mathematics, 1996. Vol.68. N.3 - P. 259-266.

29. Erdos P., Kubika E., Schwenk A. Graphs that require many colors to achieve their chromatic sum. Congressus Numerantium, 1990. - Vol.71. -P. 17-28.

30. Farber M. Characterization of strongly chordal graphs. Discrete Math, 1983.-Vol.43.-P. 173-189.

31. Foldes S., Hammer P.L. Split graphs. Proc. of the 8th Southeastern Conference on Combinatorics, 1977. - Vol.19. - P. 311-315.

32. Gavril F. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. -SIAM J.Computing, 1972. Vol. 1. N.2. - P. 180-187.

33. Gavril F. The intersection graphs of subtrees in trees are exactly the chordal graphs. J.Combinatorial Theory, 1974. - P. 47-56.

34. Giaro K., Janczewski R., Malafiejski M. A polynomial algorithm for finding T-span of generalized cacti. Discrete Applied Mathematics, 2003. -Vol.129. N.2-3. - P.371-382.

35. Giaro K., Janczewski R., Malafiejski M. The complexity of the T-coloring problem for graphs with small degree. Discrete Applied Mathematics, 2003.r^ol.,129. N.2-3^-P.361-369.

36. Goldberg A. V., Plotkin S. A. Parallel A+l-Coloring of Constant-degree Graphs. Information Processing Letters, 1987. - N.25. - P.241-245.

37. Goldberg A., Plotkin S., Shannon G. Parallel symmetry-breaking in sparse graphs. Proc. of the 19th Annual ACM Conference on Theory of Computing (STOC), 1987.-P. 315-324.

38. Golumbic M.C., Goss C.F. Perfect elimination and chordal bipartite graphs. J.Graph Theory, 1978. - Vol.2. - P. 155-163.

39. Grable D. A., Panconesi A. Fast Distributed Algorithms for Brooks-Vizing Colorings. Proc. of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1998. - P. 473-480.

40. Grable D.A., Panconesi A. Fast distributed algorithms for Brooks-Vizing colorings. J. Algorithms, - 2000. - Vol.37. - P. 85-120.

41. Hale W.K. Frequency assignment: theory and applications. Proc. of the IEEE, 1980. - Vol.68. N.12. - P.1497-1514.

42. Hammer P.L., Simone B. The splittance of a graph. Combinatorica, 1981. -Vol.1.-P. 275-284.

43. Hansen J., KubaleM., Kuszner L., Nadolski A. Distributed Largest-first algorithm for graph coloring. Proc. of EuroPar. - Lect. Notes Comput. Sci. -Springer-Verlag, 2004. Vol. 3149. - P. 527-539.

44. Hell P., Shamir R., Sharan R. A fully dynamic algorithm for recognizing and representing proper interval graphs. Proc. of the 7th Annual European Symposium on Algorithms. - Lect. Notes Comput. Sci. - Springer-Verlag, 1999.-Vol.1643.-P. 527-539.

45. Herman T., Chandy K.M. On distributed search // Inf. Process. Lett. 1985. -v.21,N8.-c. 666-677.

46. Hsu W.-L. A simple test for interval graphs. Proc. of the 18 International Workshop (WS'92), Wiesbaden-Naurod. - Springer-Verlag, Berlin, 1992. -P. 11-16.

47. Hsu W.-L., Ma T.N. Substitution decomposition on chordal graphs and applications. ISA'91 Algorithms. - Lect. Notes Comput. Sei. - SpringerVerlag, Berlin, 1991. - Vol.557. - P. 52-60.

48. Huson D., Nettles S., Warnow T. Obtaining highly accurate topology estimates of evolutionary trees from very short sequences. Proc. RECOMB'99. - Lyon (France), 1999. - P. 198-207.

49. Ibarra L. Fully dynamic algorithms for chordal graphs. Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99). -SIAM, Philadelphia, 1999. - P.923-924.

50. Jansen K. Approximation results for the optimum cost chromatic partition problem. Automata, languages and programming, 1997. - Lect. Notes Comput. Sei.-Vol. 1256. - P.727-737.

51. Janssen J., Narayanan L. Approximation algorithms for the channel assignment problem. Theoretical Computer Science, 2001. - Vol.262. -P.649-667.

52. Janssen J., Wentzell T., Fitzpatrick S. Lower bounds from tile covers for the channel assignment problem. SIAM Journal of Discrete Mathematics, 2005,- Vol.18. N.4.- P.679-696.

53. Jennings E. Distributed Algorithm for Finding a Core of a Tree Network. -Proc. of the 22nd Seminar on Current Trends in Theory and Practice of Informatics, 1995. -Lect. Notes Comput. Sci. Vol. 1012. - P. 385-390.

54. Johansson O. Simple distributed A+l- coloring of graphs. Inf. Process. Letters, 1999. Vol. 70. - P. 229-232.

55. Klein P. Efficient parallel algorithms for" chordal^ graphs. SI AM J.Computing, 1996. - Vol. 25. N.4. - P.797-827.

56. Kleinberg J.M. Authoritative sources in a hyperlinked environment. J. of the ACM, 1999. - Vol.46. N.5. - P. 604-632.

57. Korach E., Rotem D., Santoro N. Distributed algorithms for finding centers and medians in networks. ACM Trans. Program. Lang. Syst, 1984. - Vol. 6, N. 3.-P. 380-401.

58. Kosowski A., Kuszner L. On greedy graph coloring in the distributed model Proc. of EuroPar. - Lect. Notes Comput. Sci. - Springer-Verlag, 2006. - Vol. 4128. - P. 592-601.

59. Kubika E. The chromatic sum of a graph: Ph.D dissertation. Western Michigan University, 1989.

60. Kubika E., Schwenk A.J. An introduction to chromatic sums. Proc. of the seventeenth Annual ACM Comp. Sci. Conf. - ACM press, 1989. - P. 39-45.

61. Lauritzen S.L., Spiegelhalter D.J. Local computations with probabilities on graphical structures and their applications to expert systems. J. Royal Statist. Soc. Ser. B (50), 1988. — P. 157-224.

62. Lelann G. Distributed systems: Towards a formal approach. Proc. Information Processing '77. - North-Holland, 1977. - P. 155-160.

63. Lin L.-J., McKee T.A., West D.B. Leafage of chordal graph. Discuss. Math. Graph Theory, 1998. - Vol.18. - P. 23-48.

64. Lundquist M. Zero patterns, chordal graphs, and matrix completions: PhD thesis. Dept. of Mathematical Sciences, Clemson University, 1990.

65. Lynch N.A. Distributed algorithms. San Francisco, Morgan Kaufmann, 1997.

66. Malpani N., Welch J., Vaidya N. Leader election algorithms for mobile ad --hoc—networks. —-Proc. of~the-4th—International Workshop on Discrete

67. Algorithms and Methods for Mobile Computing & Communication, 2000. -Lect. Notes Comput. Sci. P. 96-103.

68. Matula D.W., Bleck L.L. Smallest-last ordering and dustering and graph coloring algorithms. J. Assoc. Comput. Math, 1983. - Vol.30. N.3. - P.417o427.

69. McKee T.A. How chordal graphs work. Bull. Inst. Combin. Appl, 1993. -Vol. 9— P. 27-39.

70. Montemanni R. Upper and lower bounds for the fixed spectrum frequency assignment problem: PhD thesis. Division of Mathematics and Statistics, School of Technology, University of Glamorgan, UK, 2001.

71. Nakano K., Olariu S. Randomized leader election protocols in radio networks with no collision detection. International Symposium on Algorithms and Computation, 2000. - Lect. Notes Comput. Sci. - Vol. 1969. -P. 362-373.

72. Neopolitan R.E. Probabilistic reasoning in expert systems. Theory and Algorithms, 1990.

73. Nicolosco S., Sarrafzadeh M., Song X. On the sum coloring problem on interval graphs. Algorithmica, 1999. - Vol.23. - P. 109-126.

74. Nikolopoulos S.D. Constant-time parallel recognition of split graphs. -Information Processing Letters, 1995. Vol. 54. - P.1-8.

75. Panconesi A., Rizzi R. Some Simple Distributed Algorithms for Sparse Networks. Distributed Computing, 2001. -Vol.14. N.2. P.97-100.

76. Panconesi A., Silvestri R. Experimental Analysis of Simple, Distributed Vertex Coloring Algorithms. Proc. of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2002. P. 606-615.

77. Roberts F. S. T-colorings of graphs: Recent results and open problems. -Discrete Mathematics, 1991. Vol.93. N.2-3. - P.229-245.

78. Rose D.J., Tarjan R.E., Lueker G,S. Algorithmic aspects of vertex elimination on graphs. SIAM J. Computing, 1976. - Vol.5. N.2. - P. 266283.

79. Simon H. U. Approximation algorithms for channel assignment in cellular radio networks. In Fundamentals of Computation Theory. - SpringerVerlag, 1989. -Lect. Notes Comput. Sei. - Vol. 380. - P. 405-415.

80. Simon H. U. Approximation algorithms for channel assignment in cellular radio networks. In Fundamentals of Computation Theory. - Springer-Verlag, 1989. - Lect. Notes Comput. Sei. - Vol. 380. - P. 405-415.

81. Smith D. H., Hurley S., Allen S. M. A new lower bound for the channel assignment problem. IEEE Transactions on Vehicular Technology, 2000. -Vol.49. N.4.- P.1265-1272.

82. Supowit K.J. Finding a maximum planar subset of nets in a channel // IEEE Trans, on Computer Aided Design (CAD). 1987. - V.6.N. 1. - P. 93-94.

83. Szekeres G.,Wilf H.S. An inequality for the chromatic number of a graph. J. Combin. Theory, 1964. - Vol.4. - P. 1-3.

84. Tajibnapis W. D. A correctness proof of a topology information maintenance protocol for a distributed computer network. CACM, 1977. -Vol.20. N. 7. -P.477-485.

85. Tajibnapis W. D. The design of a topology information maintenance scheme for a distributed computer network. Proc. ACM Conference, 1974. - Vol.1. -P. 358-364.

86. Tarjan R.E., Yannakakis M. Simple linear time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic-hypergraphs. SIAM-J:Computing, 1984. - Voll. 13. Nr3—Pr566-576.--

87. Tesman B. A. Set T-colorings. Congressus Numerantium, 1990. - N.77. -P.229-242.

88. Tesman B. A. Set T-colorings. Congressus Numerantium, 1990. - N.77. -P.229-242.

89. Tursunbay kyzy Y. A fully dynamic algorithm for recognizing and representing chordal graphs. Perspectives of System Informatics. - Lect. Notes Сотр. Sci. - Springer-Verlag, 2007. - Vol.4378 - P. 481-486.

90. Wall D. W., Owicki S. Center-based Broadcasting: Computer Systems Lab. Technical Report TR189. Stanford University, 1980.

91. Walter J.R. Representations of chordal graphs of a tree. J.Graph Theory, 1978.-Vol. 2. - P.265-267.

92. Zotenko E., Guimaraes K.S., Jothi R., Przytychka T.M. Decomposition of overlapping protein complexes: a graph theoretical method for analyzing static and dynamic protein associations. Algorithms for Molecular Biology, 2006.-Vol. 1, N.7.

93. Волошин В.И. Свойство триангулированных графов // Исслед. операций и программирования. Мат.наук. Кишинев, 1982. - С.24-32.

94. Евстигнеев В.А. Граф-модели систем и основные принципы их исследования: Диссертация докт. физ.-мат. наук: 05.13.16. — Новосибирск, 1990. — С.218-224.

95. Евстигнеев В.А. Локальные алгоритмы и распределенные вычисления // "Проблемы теоретической кибернетики". Тез. докл. VIII Всес. конф. -Горький, 1988.-с. 113-114.

96. Евстигнеев В. А. Локальные алгоритмы на графах и проблема децентрализованной обработки информации // II Всес. конф. по прикладной логике. Тез. докл. Новосибирск, 1988. - с. 75-77.

97. Евстигнеев В.А. Локальные вычислительные алгоритмы и нахождение вершин с наибольшей степенью в неориентированном графе //

98. Комбинаторно-алгебраические методы—в прикладной математике. ---

99. Горький, Изд-во ГГУ, 1981. с. 60-66.

100. Евстигнеев В.А. Локальный алгоритм отыскания бикомпонент в ориентированном графе. ЖВМ, 1978, Т. 18, № 5, с. 1345-1349.

101. Евстигнеев В.А. Методы теории графов в наукометрии: исследование структуры пространства журналов и незримых коллективов в программировании. М., 1987. - 26 с. - (Препринт / АН СССР. Институт точной механики и вычисл.техники. Новосиб.фил.; № 4).

102. Евстигнеев В.А. О некоторых свойствах локальных алгоритмов на графах // Комбинаторно-алгебраические методы в прикладной математике. Горький, Изд-во ГГУ, 1983. - с. 72-105.

103. Евстигнеев В.А. Применение теории графов в программировании. М.: Наука, 1985.- 352 с.

104. Евстигнеев В.А. Теоретико-графовые модели систем сетевой структуры // Труды ВЦ СО РАН. Информатика, 1. Новосибирск, 1994. - С.78-121.

105. Евстигнеев В.А. Хордальные графы и их свойства // Проблемы систем информатики и программирования. Новосибирск, 1999. - С.33-64.

106. Евстигнеев В.А. Хордальные графы и их свойства // Проблемы систем информатики и программирования. Новосибирск, 1999. - С.33-64.

107. Евстигнеев В.А., Турсунбай кызы Ы. Анализ локальных алгоритмов для раскраски графов, использующих стратегию жадного алгоритма // Вестник Кыргызско-Российского Славянского университета. 2011. -Т.П. №7 - С. 148-153.

108. Евстигнеев В.А., Турсунбай кызы Ы. Динамический распределенный ПН-алгоритм для раскраски w-совершенных графов // Методы иинструменты конструирования программ. / РАН, Сиб.отд-е, Ин-т систем информатики. Новосибирск, 2007. - С. 24-31.

109. Евстигнеев В.А., Турсунбай кызы Ы. О раскраске графов в классе параллельных локальных алгоритмов // Сиб. журн. вычисл. математики. -Новосибирск, 2011.-Т. 14. №3 -С. 231-243.1Л З.-Емеличев-В.А.,-Мельников О.Ит, Сарванов -В.И., -Тышкевич Р.И.-------

110. Лекции по теории графов. М.: Наука, 1990.

111. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.

112. Журавлев Ю.И. Алгоритмы построения минимальных дизъюнктивных нормальных форм для функций алгебры логики. В кн.: Дискретная математика и математические вопросы кибернетики, T.l, М., Наука, 1974, с. 67-98.

113. Журавлев Ю.И. Локальные алгоритмы вычисления информации. 1. -Кибернетика, 1965, №1, с. 12-19.

114. Маркосян С.Е., Гаспарян Г.С. w-совершенные графы // Ученые записки. Ереван.гос.универ-т, 1987. №3 - С.9-15.

115. Таненбаум Э.С. Компьютерные сети. СПб.: Питер, 2003. - 992 с.

116. Тель Ж. Введение в распределенные алгоритмы. МЦНМО, 2009. - 616 с.

117. Турсунбай кызы Ы. Алгоритмы раскраски графов в распределенной модели вычислений // Вестник Иссык-Кульского государственного университета. -2010. Т. 26. №1 - С. 107-114.

118. Турсунбай кызы Ы. Деревья клик хордального графа и деревья подграфов в теории графов // Конструирование и оптимизация параллельных программ / РАН, Сиб.отд-е, Ин-т систем информатики. -Новосибирск, 2008. С. 314-321.

119. Турсунбай кызы Ы. Деревья подграфов в теории графов // Материалы XLIII Международной Научной Студенческой Конференции «Студент инаучно-технический прогресс»: Математика / Новосиб.гос.ун-т. -Новосибирск, 2005. С. 215.

120. Турсунбай кызы Ы. Динамический алгоритм для распознавания и представления хордальных графов // VI Всероссийская конференция молодых ученых по математическому моделированию и-информационным -тех-нологиям1—Кемерово:-изд-во-КемГУ, 2005т О;—71.72.

121. Турсунбай кызы Ы. Нахождение центров и медиан в сетях произвольной топологии // Вестник Иссык-Кульского государственного университета. -2010. Т. 26. №1 - С. 82-87.

122. Турсунбай кызы Ы. О раскраске графов // Материалы международной конференции «Развитие вычислительной техники в России и странах бывшего СССР: история и перспективы (БСЖиСОМ 2006)». В 2 ч. -Петрозаводск, 2006. 4.2 - С. 125-126.