Локальные и динамические алгоритмы для анализа граф-моделей систем
Вторым интересующим направлением являются минимаксные и минисуммные задачи размещения, которые имеют место при проектировании механизмов маршрутизации, построении технологий синхронизации в децентрализованных сетях и др. Существуют несколько локальных алгоритмов нахождения центров и медиан, но все они имеют собственные ограничения, например, ограничиваются специфической топологией сети полный… Читать ещё >
Содержание
- ГЛАВА 1. ДИНАМИЧЕСКИЕ АЛГОРИТМЫ ДЛЯ РАСПОЗНАВАНИЯ И ПРЕДСТАВЛЕНИЯ КЛАССОВ ГРАФОВ
- 1. 1. Деревья клик хор дальнего графа и деревья подграфов в теории графов
- 1. 1. 1. Деревья клик
- 1. 1. 2. Деревья подграфов
- 1. 1. 3. Строгие деревья подграфов
- 1. 2. Полностью динамический алгоритм для распознавания и представления хордальных графов
- 1. 2. 1. Добавление полного г-вершинника Кг
- 1. 2. 2. Удаление полного г-вершинника Кг
- 1. 3. Полностью динамический алгоритм для распознавания и представления расщепляемых графов
- 1. 1. Деревья клик хор дальнего графа и деревья подграфов в теории графов
- Выводы
- ГЛАВА 2. РАСКРАСКА ГРАФ-МОДЕЛЕЙ В КЛАССЕ ПАРАЛЛЕЛЬНЫХ ЛОКАЛЬНЫХ АЛГОРИТМОВ
- 2. 1. Локальные алгоритмы
- 2. 2. Модель вычислений
- 2. 3. Алгоритм жадной раскраски в контексте локальных алгоритмов
- 2. 4. Обзор распределенных алгоритмов раскраски графов
- 2. 5. Локальный алгоритм для раскраски м>— совершенных графов
- 2. 6. Разновидности раскраски графов
- 2. 6. 1. Т-раскраска графов
- 2. 6. 2. Суммирующая раскраска графов
- 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) от различных характеристик графа таких, как плотность.
Последовательные алгоритмы, использующие стратегию жаднойраскраски, имеютважноепрактическое значение из-за числа классов графов, для которых они всегда дают оптимальные или почти оптимальные результаты. Поэтому естественно сформулировать задачу построения локальных алгоритмов раскраски с аналогичными свойствами. В настоящей работе исследуются разновидности локального алгоритма раскраски применительно к классу 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−90 901-мобснгст, № 11−01−90 901-мобснгст).
Объем и структура диссертации. Диссертационная работа состоит из введения, трех глав и списка литературы. Объем диссертации — 92 стр.
Список литературы
содержит 126 наименований.
Основные результаты, полученные в ходе диссертационной работы.
1. Проведены комплексные теоретические исследования в области изучения граф-моделей систем и их свойств, позволившие разработать и.
— - - ~ ~реализоватьновью локальные и динамические алгоритмы для их анализа.
2. Разработаны полностью динамические алгоритмы для распознавания и представления семейства хордальных и расщепляемых графов. Впервые в качестве производимых модификаций рассмотрено добавление и удаление полного г-вершинного графа Кг.
3. Разработаны и реализованы алгоритмы для вершинной раскраски графов в рамках локальной модели вычислений:
ПН-алгоритм для раскраски ^—совершенных графов. Данный алгоритм оптимально или почти оптимально красит графы из класса-совершенных графов.
ВБАТТЖ (НПН)-алгоритм для Г-раскраски графов, который оптмально красит все двудольные графы для произвольных множеств Т.
Обратный НП-алгоритм для суммирующей раскраски графов. Показано, что данный алгоритм оптимально или почти оптимально красит А>дольные графы, двудольные колеса и двойные звезды.
4. Разработан локальный асинхронный алгоритм для нахождения центров и медиан в сетях произвольной топологии. Реализована моделирующая программа, основанная на данном алгоритме.
ЗАКЛЮЧЕНИЕ
.
Список литературы
- 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.
- Allen S. M., Smith D. H., Hurley S. Lower bounding techniques forfrequencyassignment, Discrete Mathematics, 1999. — Vol. 197−198. — P.4152.
- Arnborg S., Lagergren J. Easy problems for tree decomposable graphs. J. of Algorithms, 1991. — Vol.12. — P. 308−340.
- Averbuch B. A new distributed depth-first-search algorithm // Inf. Process. Lett. 1985. — Vol.20, N 3. — P.147−150.
- Barbosa V.C. An introduction to distributed algorithm. MIT Press, Cambridge, MA, 1996.
- 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.
- 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.
- Battiti R., Bertossi A.A., Bonuccelli M.A. Assigning codes in wireless networks. Wireless Networks, 1999. N.5. — P. 195−209.
- Bellare M., Goldreich O., Sudan M. Free bits, PCPs and non-approximability towards tight results. — SIAM J. Сотр., 1998. — Vol.27. -P.804−915.
- Bernstein P.A., Goodman N. Power of natural semijoints. SIAM. J. Comput., 1981.-Vol.10.-P. 751−771.
- Berry A., Heggernes P., Villanger Y. A vertex incremental approach for dynamically maintaining chordal graphs. Discrete Mathematics, 2006. -Vol. 3063.-P. 318−336.
- Bertsekas D.P., Tsitsiklis J.N. Parallel and distributed computation.1. McGraw-Hill, 1996^
- Branstadt A., Dragan F.F., Chepoi V.D., Voloshin V.I. Dually chordal graphs. SIAM J. Discrete Mathematics, 1998. — Vol.11. — P. 437−455.
- Brelaz D. New methods to color the vertices of a graph. Communications of the ACM. 1979. — V.22.N.4. — P.251 — 256.
- 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.
- 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.
- Buneman P. A characterization of rigid circuit graphs. Discrete Math, 1974. — Vol. 9.-P. 205−212.
- Chandy K.M., Mistra J. Distributed computation on graphs: shortest path algorithms // Com. ACM. 1982. — Vol. 25, N 11. — P. 833−837.
- Chang E.G. Decentralized algorithms in distributed systems. Tech. Rep. CCRG-103. — Computer Systems Research Group, University of Toronto, 1979.
- 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.
- Chelnokov V.M., Zephyrova V.L. Collective phenomena in hypertext networks. Proc. of the Hypertext'97 Conference (Southampton, UK). -ACM, 1997.-P. 220−221.
- Chelnokov V.M., Zephyrova V.L. Hypertext macrodynamics. Lecture Notes Comput. Sci. — Berlin: Springer-Verlag, 1995 — Vol. 1015. — P. 105 120.
- 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.
- Annals of Operations Research, 1993. — Vol.41. N.4. — P.343−358.
- Cozzens M. B., Roberts F. S. T-colorings of graphs and the channel assignment problem. Congressus Numerantium, 1982. — Vol.35. — P. 191−208.
- 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.
- Djastra E.W., Scholton C.S. Termination detection for diffusing computations // Inf. Process. Lett. 1980. — V. 11, N 1. — P. 1−4.
- Dragan F.F., Voloshin V.I. Incidence graphs of biacyclic hypergraphs. -Discrete Applied Mathematics, 1996. Vol.68. N.3 — P. 259−266.
- Erdos P., Kubika E., Schwenk A. Graphs that require many colors to achieve their chromatic sum. Congressus Numerantium, 1990. — Vol.71. -P. 17−28.
- Farber M. Characterization of strongly chordal graphs. Discrete Math, 1983.-Vol.43.-P. 173−189.
- Foldes S., Hammer P.L. Split graphs. Proc. of the 8th Southeastern Conference on Combinatorics, 1977. — Vol.19. — P. 311−315.
- 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.
- Gavril F. The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Combinatorial Theory, 1974. — P. 47−56.
- 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.
- 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.
- Goldberg A. V., Plotkin S. A. Parallel A+l-Coloring of Constant-degree Graphs. Information Processing Letters, 1987. — N.25. — P.241−245.
- 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.
- Golumbic M.C., Goss C.F. Perfect elimination and chordal bipartite graphs. J. Graph Theory, 1978. — Vol.2. — P. 155−163.
- 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.
- Grable D.A., Panconesi A. Fast distributed algorithms for Brooks-Vizing colorings. J. Algorithms, — 2000. — Vol.37. — P. 85−120.
- Hale W.K. Frequency assignment: theory and applications. Proc. of the IEEE, 1980. — Vol.68. N.12. — P.1497−1514.
- Hammer P.L., Simone B. The splittance of a graph. Combinatorica, 1981. -Vol.1.-P. 275−284.
- 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.
- 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.
- Herman T., Chandy K.M. On distributed search // Inf. Process. Lett. 1985. -v.21,N8.-c. 666−677.
- 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.
- 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.
- 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.
- 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.
- 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.
- Janssen J., Narayanan L. Approximation algorithms for the channel assignment problem. Theoretical Computer Science, 2001. — Vol.262. -P.649−667.
- 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.
- 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.
- Johansson O. Simple distributed A+l- coloring of graphs. Inf. Process. Letters, 1999. Vol. 70. — P. 229−232.
- Klein P. Efficient parallel algorithms for" chordal^ graphs. SI AM J. Computing, 1996. — Vol. 25. N.4. — P.797−827.
- Kleinberg J.M. Authoritative sources in a hyperlinked environment. J. of the ACM, 1999. — Vol.46. N.5. — P. 604−632.
- 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.
- 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.
- Kubika E. The chromatic sum of a graph: Ph. D dissertation. Western Michigan University, 1989.
- 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.
- 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.
- Lelann G. Distributed systems: Towards a formal approach. Proc. Information Processing '77. — North-Holland, 1977. — P. 155−160.
- Lin L.-J., McKee T.A., West D.B. Leafage of chordal graph. Discuss. Math. Graph Theory, 1998. — Vol.18. — P. 23−48.
- Lundquist M. Zero patterns, chordal graphs, and matrix completions: PhD thesis. Dept. of Mathematical Sciences, Clemson University, 1990.
- Lynch N.A. Distributed algorithms. San Francisco, Morgan Kaufmann, 1997.
- Malpani N., Welch J., Vaidya N. Leader election algorithms for mobile ad --hoc—networks. —-Proc. of~the-4th—International Workshop on Discrete
- Algorithms and Methods for Mobile Computing & Communication, 2000. -Lect. Notes Comput. Sci. P. 96−103.
- 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.
- McKee T.A. How chordal graphs work. Bull. Inst. Combin. Appl, 1993. -Vol. 9— P. 27−39.
- 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.
- 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.
- Neopolitan R.E. Probabilistic reasoning in expert systems. Theory and Algorithms, 1990.
- Nicolosco S., Sarrafzadeh M., Song X. On the sum coloring problem on interval graphs. Algorithmica, 1999. — Vol.23. — P. 109−126.
- Nikolopoulos S.D. Constant-time parallel recognition of split graphs. -Information Processing Letters, 1995. Vol. 54. — P.1−8.
- Panconesi A., Rizzi R. Some Simple Distributed Algorithms for Sparse Networks. Distributed Computing, 2001. -Vol.14. N.2. P.97−100.
- 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.
- Roberts F. S. T-colorings of graphs: Recent results and open problems. -Discrete Mathematics, 1991. Vol.93. N.2−3. — P.229−245.
- 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. 266 283.
- 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.
- 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.
- 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.
- 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.
- Szekeres G., Wilf H.S. An inequality for the chromatic number of a graph. J. Combin. Theory, 1964. — Vol.4. — P. 1−3.
- 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.
- 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.
- 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.--
- Tesman B. A. Set T-colorings. Congressus Numerantium, 1990. — N.77. -P.229−242.
- Tesman B. A. Set T-colorings. Congressus Numerantium, 1990. — N.77. -P.229−242.
- 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.
- Wall D. W., Owicki S. Center-based Broadcasting: Computer Systems Lab. Technical Report TR189. Stanford University, 1980.
- Walter J.R. Representations of chordal graphs of a tree. J. Graph Theory, 1978.-Vol. 2. — P.265−267.
- 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.
- Волошин В.И. Свойство триангулированных графов // Исслед. операций и программирования. Мат.наук. Кишинев, 1982. — С.24−32.
- Евстигнеев В.А. Граф-модели систем и основные принципы их исследования: Диссертация докт. физ.-мат. наук: 05.13.16. — Новосибирск, 1990. — С.218−224.
- Евстигнеев В.А. Локальные алгоритмы и распределенные вычисления // «Проблемы теоретической кибернетики». Тез. докл. VIII Всес. конф. -Горький, 1988.-с. 113−114.
- Евстигнеев В. А. Локальные алгоритмы на графах и проблема децентрализованной обработки информации // II Всес. конф. по прикладной логике. Тез. докл. Новосибирск, 1988. — с. 75−77.
- Евстигнеев В.А. Локальные вычислительные алгоритмы и нахождение вершин с наибольшей степенью в неориентированном графе //
- Комбинаторно-алгебраические методы—в прикладной математике. ---
- Горький, Изд-во ГГУ, 1981. с. 60−66.
- Евстигнеев В.А. Локальный алгоритм отыскания бикомпонент в ориентированном графе. ЖВМ, 1978, Т. 18, № 5, с. 1345−1349.
- Евстигнеев В.А. Методы теории графов в наукометрии: исследование структуры пространства журналов и незримых коллективов в программировании. М., 1987. — 26 с. — (Препринт / АН СССР. Институт точной механики и вычисл.техники. Новосиб.фил.- № 4).
- Евстигнеев В.А. О некоторых свойствах локальных алгоритмов на графах // Комбинаторно-алгебраические методы в прикладной математике. Горький, Изд-во ГГУ, 1983. — с. 72−105.
- Евстигнеев В.А. Применение теории графов в программировании. М.: Наука, 1985.- 352 с.
- Евстигнеев В.А. Теоретико-графовые модели систем сетевой структуры // Труды ВЦ СО РАН. Информатика, 1. Новосибирск, 1994. — С.78−121.
- Евстигнеев В.А. Хордальные графы и их свойства // Проблемы систем информатики и программирования. Новосибирск, 1999. — С.33−64.
- Евстигнеев В.А. Хордальные графы и их свойства // Проблемы систем информатики и программирования. Новосибирск, 1999. — С.33−64.
- Евстигнеев В.А., Турсунбай кызы Ы. Анализ локальных алгоритмов для раскраски графов, использующих стратегию жадного алгоритма // Вестник Кыргызско-Российского Славянского университета. 2011. -Т.П. № 7 — С. 148−153.
- Евстигнеев В.А., Турсунбай кызы Ы. Динамический распределенный ПН-алгоритм для раскраски w-совершенных графов // Методы иинструменты конструирования программ. / РАН, Сиб. отд-е, Ин-т систем информатики. Новосибирск, 2007. — С. 24−31.
- Евстигнеев В.А., Турсунбай кызы Ы. О раскраске графов в классе параллельных локальных алгоритмов // Сиб. журн. вычисл. математики. -Новосибирск, 2011.-Т. 14. № 3 -С. 231−243.1Л З.-Емеличев-В.А.,-Мельников О. Ит, Сарванов -В.И., -Тышкевич Р.И.-------
- Лекции по теории графов. М.: Наука, 1990.
- Емеличев В.А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990.
- Журавлев Ю.И. Алгоритмы построения минимальных дизъюнктивных нормальных форм для функций алгебры логики. В кн.: Дискретная математика и математические вопросы кибернетики, T. l, М., Наука, 1974, с. 67−98.
- Журавлев Ю.И. Локальные алгоритмы вычисления информации. 1. -Кибернетика, 1965, № 1, с. 12−19.
- Маркосян С.Е., Гаспарян Г.С. w-совершенные графы // Ученые записки. Ереван.гос.универ-т, 1987. № 3 — С.9−15.
- Таненбаум Э.С. Компьютерные сети. СПб.: Питер, 2003. — 992 с.
- Тель Ж. Введение в распределенные алгоритмы. МЦНМО, 2009. — 616 с.
- Турсунбай кызы Ы. Алгоритмы раскраски графов в распределенной модели вычислений // Вестник Иссык-Кульского государственного университета. -2010. Т. 26. № 1 — С. 107−114.
- Турсунбай кызы Ы. Деревья клик хордального графа и деревья подграфов в теории графов // Конструирование и оптимизация параллельных программ / РАН, Сиб. отд-е, Ин-т систем информатики. -Новосибирск, 2008. С. 314−321.
- Турсунбай кызы Ы. Деревья подграфов в теории графов // Материалы XLIII Международной Научной Студенческой Конференции «Студент инаучно-технический прогресс»: Математика / Новосиб.гос.ун-т. -Новосибирск, 2005. С. 215.
- Турсунбай кызы Ы. Динамический алгоритм для распознавания и представления хордальных графов // VI Всероссийская конференция молодых ученых по математическому моделированию и-информационным -тех-нологиям1—Кемерово:-изд-во-КемГУ, 2005 т О-—71.72.
- Турсунбай кызы Ы. Нахождение центров и медиан в сетях произвольной топологии // Вестник Иссык-Кульского государственного университета. -2010. Т. 26. № 1 — С. 82−87.
- Турсунбай кызы Ы. О раскраске графов // Материалы международной конференции «Развитие вычислительной техники в России и странах бывшего СССР: история и перспективы (БСЖиСОМ 2006)». В 2 ч. -Петрозаводск, 2006. 4.2 — С. 125−126.