автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Локальные и динамические алгоритмы для анализа граф-моделей систем

На правах рукописи

УДК 004.72; 004.75; 519.171; 519.174; 519.178

ТУРСУНБАЙ кызы Ырысгуль

ЛОКАЛЬНЫЕ И ДИНАМИЧЕСКИЕ АЛГОРИТМЫ ДЛЯ АНАЛИЗА ГРАФ-МОДЕЛЕЙ СИСТЕМ

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

- 8 ДЕК 2011

Новосибирск - 2011

005004922

Работа выполнена в Учреждении Российской академии наук Институте систем информатики им. А.П. Ершова СО РАН

Научные руководители:

доктор физико - математических наук, профессор,

Евстигнеев Владимир Анатольевич

доктор физико-математических наук, профессор,

Касьянов Виктор Николаевич,

Официальные оппоненты:

доктор физико - математических наук, профессор,

Попков Владимир Константинович,

кандидат физико - математических наук, Аксенов Валерий Анатольевич,

Ведущая организация: Южный федеральный университет

(г. Ростов-на-Дону)

Защита состоится 28 декабря в 16 ч. 00 мин. на заседании диссертационного совета ДМ 003.032.01 в Институте систем информатики им. А.П. Ершова Сибирского отделения РАН по адресу: 630090, г. Новосибирск, пр. ак. Лаврентьева, 6.

С диссертацией можно ознакомиться в читальном зале ИСИ СО РАН (г. Новосибирск, пр. ак. Лаврентьева, 6).

Автореферат разослан 23 ноября 2011 г.

Ученый секретарь Диссертационного совета,

к.ф.-м.н. N

Мурзин Ф.А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

Цель работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные идеи и конкретные результаты диссертационной работы обсуждались на следующих конференциях и семинарах:

1. International Andrei Ershov Memorial Conference on Perspectives System Informatics on (Novosibirsk, Russia, 2006)

2. XIII Международная конференция студентов, аспирантов и молодых ученых «Ломоносов-2006 (Москва, 2006)

3. Международная конференция «Развитие вычислительной техники в России и странах бывшего СССР: история и перспективы (SORUCOM 2006)», (Петрозаводск, 2006)

4. Конференция-конкурс «Технологии Microsoft в информатике и программировании» (Новосибирск, 2005)

5. ХЫП Международная Научная Студенческая Конференция «Студент и научно-технический прогресс» (Новосибирск, 2005)

6. VI Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (Кемерово, 2005)

7. Семинары лаборатории «Конструирование и оптимизация программ», Новосибирск, ИСИ СО РАН, 2003-2009

Публикации

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

Исследования выполнялись в соответствии с планами научно-исследовательских работ ИСИ СО РАН по проектам 3.1.5 «Методы и средства трансляции и конструирования эффективных и надежных программ», IV.32.2.2 «Методы и технологии конструирования и оптимизации программных систем для суперкомпьютеров и компьютерных сетей» и были частично поддержаны грантами РФФИ (№ 09-01-90901-моб_снг_ст, № 11-01-90901-моб_снг_ст).

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

Граф называется хордапъным, если каждый его цикл длины > 3 содержит хорду, т.е. ребро, соединяющее несмежные вершины простого цикла.

Лемма 1 [3], [4], [5]. Граф б является хордапъным тогда и только тогда, когда он имеет дерево клик.

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

Пусть Сг = (У(С), Е(О)) = (V, Е) является неориентированным графом без петель и кратных ребер. Через Кг обозначим полный г-вершинный граф, где г >3. Введем следующие обозначения:

У(0 п Г(Кг) = р, Е(в) пЕ(Кг) = д, О +КГ = {У(С) + (У(КГ) \р), Е(0) + (Е(КГ) \ д)}, С-Кг = ЩС) - (У(КГ) \р), Е(С) -Е(КГ)}.

Предположим, что (3 - некоторый граф и Т - дерево, вершинами которого являются максимальные клики. Через и, V обозначим названия

вершин и через х, у названия узлов, которые соответствуют максимальным кликам Кх, Ку.

иу-сепаратором графа G называется множество вершин S, после удаления которых вершины и и v оказываются в разных компонентах связности.

Пусть Ij = Kj п N(Kj) - сепаратор графа G, где N(Kj) - множество всех узлов дерева Т, смежных с узлом J, которое называется окрестностью клики Kj.

Построенные алгоритмы опираются на следующие теоремы.

Теорема 2. Пусть G — хордальный граф, не содержащий полный r-вершинник Кг, тогда G + КГ является хордальньш тогда и только тогда, когда выполняются следующие условия:

1. Граф G имеет дерево клик Т, где и, v ер, и еКх, v еКу для некоторых {х,у} еТ.

2. Существует путь х—у в Т такой, что /кг nlj / ^ 0, где Ij сепаратор для всех Kj, содержащихся на этом пути.

Теорема 3. Пусть G — хордальный граф, содержащий полный r-вершинник Кг, тогда G - Кг является хордальным тогда и только тогда, когда выполняются следующие условия:

1. Ребро {и, v} е q кроме Кг содержится только в одной максимальной

клике.

2. В графе G не существует цикла, состоящего из вершин множества Ir = Kr nN(Kr).

Также доказана следующая теорема.

Теорема 4. Если вершины множества Ir = Kr п N(Kr) образуют две или больше различных пути Рь тогда полный г—вершинник Кг является сепаратором графа G.

Граф называется расщепляемым, если для него существует разбиение его вершин на клику К и независимое множество I. Граф является расщепляемым, если граф G и его дополнение G являются хордальными.

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

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

Лемма 5 [6]. Пусть G является графом с последовательностью вершин d,>d2>...>d„ и пусть j=max{i | d,>i-\}. Тогда G является расщепляемым графом тогда и только тогда, когда выполняется равенство:

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

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

Приведем определение локального алгоритма. Вначале сформулируем принцип локальности:

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

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

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

Локальный алгоритм называется параллельным локальным алгоритмом, если один шаг его состоит в одновременном и независимом перевычислении

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

Рассмотрим реализацию локальных алгоритмов на сети процессоров, моделирующих структуру исследуемой граф-модели. Вычислительная система, моделирующая топологию данного графа, есть множество однотипных процессоров, каждый из которых соответствует вершине графа. Каждый процессор имеет локальную память ограниченного объема. Два процессора связаны каналом связи, если соответствующие вершины в графе смежны. Каждый процессор может производить некоторые вычисления, а также посылать и принимать сообщения; он имеет достаточно возможностей для одновременной посылки сообщений всем своим соседям и достаточно памяти, чтобы хранить все поступившие к нему сообщения. О скорости передачи не делается никаких предположений, но наложения одного сообщения на другое на одном звене связи не допускается. Ни центрального процессора, ни общей памяти в любом виде, ни таймера или другой какой синхронизации в такой системе не допускается. Системы подобного типа производят децентрализованную обработку информации, и получаемый результат есть итог взаимодействия процессоров. Окончание вычислений наступает, когда каждая вершина придет в такое состояние, в котором она не посылает сообщений и не воспринимает сигналов и граф становится «мертвым».

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

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

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

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

Представим различные стратегии при организации последовательных раскрасок.

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

• ПН-алгоритмом называется алгоритм, основанный на ПН-упорядочении («последними - наименьшие») вершин, которая строится следующим образом:

а) для и = \v\ в качестве v„ выбирается вершина минимальной степени в графе G;

б) для »= и-1,и-2,...,2,1 в качестве v, выбирается вершина минимальной степени в подграфе

и нахождения по нему раскраски графа G.

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

В настоящей работе рассмотрены следующие модификации локального алгоритма:

1. Локальный ПН-алгоритм для раскраски w — совершенных графов.

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

Одной из важных характеристик, связанных с хроматическим числом, является число Секереша-Вилфа iv(G) = max<5(G') + l, где S(G') = min dG.(x) -

G'cG x eV(G')

минимальная степень графа <7, а dG,(x) - степень вершины л в ff. Важность этой характеристики заключается в том, что, во-первых, w(G) является

довольно нетривиальной верхней оценкой для z(.G)> т.е. класс графов, для которых w{G)=%(G) довольно большой и содержит в себе много практически интересных классов, и, во-вторых, она легко вычисляемая.

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

Для вычисления w(G) применяется ПН-упорядочение вершин графа G.

Применим эвристику последовательного ПН-алгоритма для раскраски w -совершенных графов в классе параллельных локальных алгоритмов.

Теорема 6. Задача раскраски w -совершенных графов ПН-алгоритмом разрешима в классе параллельных локальных алгоритмов.

Лемма 7. Параллельный локальный ПН-алгоритм оптимально или почти оптимально (c{G)~ x{G)< \) красит графы из класса w-совершенных графов не более чем w(G) цветами за время О (Л2 log п).

2. Локальный T-DSATUR алгоритм для Т-раскраски графов.

Задача Г-раскраски графа является обобщением задачи вершинной раскраски графа, которая была представлена в качестве модели назначения частот радио передатчикам.

Функция с:К-> z называется Т-раскраской графа тогда и только тогда, когда с(и) - c(v) t Т для всех {u,v} е Е, где Т — множество запрещенных расстояний.

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

Отметим, что вершинная раскраска и Г-раскраска графа взаимосвязаны, каждая Т-раскраска G является вершинной раскраской G и каждая вершинная раскраска G является его {0}-раскраской.

В данном случае наилучшей эвристикой для Т-раскраски графов является использование алгоритма Г-БЗАНЖ, Г-ББАТиЯ - это применение НПН (В8АТ1Ж)-алгоритма для Г-раскраски графов.

Теорема 8. Задача Т-раскраски графов НПН (ВБАТиК)-алгоритмом разрешима в классе параллельных локальных алгоритмов.

Лемма 9. Параллельный локальный НПН (ОБА Т1Л{)-алгоритм оптимально или почти оптимально красит все двудольные графы для произвольных множеств Т.

3. Локальный обратный НП-алгоритм для суммирующей раскраски графов.

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

где

и с := -> N - правильная вершинная раскраска графа в. Существуют графы, для которых оптимальная суммирующая раскраска требует больше цветов, чем их хроматическое число.

Идея суммирующей раскраски графа параллельно возникла в двух различных областях: теоретической теории графов и в области проектирования СБИС.

Для последней области исследования задача заключается в следующем: Задано множество сетей с двумя терминалами, которые должны быть связаны электрической сетью. Существует основная линия, на которой имеются сети и несколько параллельных горизонтальных равномерно распределенных каналов, расположенных на расстояниях с!=\, 2, 3... от основной линии. Связь двух сетевых терминалов, чьи позиции задаются, должна быть составлена из двух вертикальных сегментов и одного горизонтального сегмента, где горизонтальный сегмент должен лежать на одном из каналов. Отметим, что перекрывающиеся сети не могут быть трассированы через один канал (рис. 1).

I I ■ !■■!!« ■

—»-к—*——

Рис. 1. Пример задачи трассировки

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

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

Для рассматриваемого алгоритма справедлива следующая теорема.

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

Локальный обратный НП-алгоритм оптимально или почти оптимально красит ¿-дольные графы, двудольные колеса и двойные звезды.

Для всех трех вышеописанных алгоритмов доказана их разрешимость в классе параллельных локальных алгоритмов.

Для Г-раскраски и суммирующей раскраски графов рассмотрены основные области их применения.

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

Пусть й - связный граф, а х и у — две его несовпадающие вершины. Длина кратчайшего (х, у) - маршрута называется расстоянием между вершинами хи у я обозначается ¿(х, у). Эксцентриситет вершины е(х) в графе (5 и радиус г (О), соответственно, определяются как е(*) = тах<1(х,у), уеУ и г(£?) = тте(х), хеУ. Центром графа б называется множество С(0) = {хеК| е(х) = г(в)}.

Статус вершины с!(х) и статус графа а (б) определяются, соответственно, как ¿(х) = и сг(<7) = штф). Медианой графа С является множество

М{0) = {х^У\ а{х) = а(С)}.

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

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

Главной особенностью предлагаемого в настоящей работе алгоритма является его асинхронность и применимость к сетям произвольной топологии.

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

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

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

В рамках нашего алгоритма предполагаем, что распределенная система состоит из п идентичных узлов, обозначенных уникальными именами N0, N1, N2..., N3. У каждого узла есть три различных процессора, программа которых составлена из атомарных шагов. Эти три процессора соответствуют трем

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

Потоковый граф процесса для данного алгоритма, показан на рис 2.

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

В заключении перечислены основные результаты работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

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

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

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

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

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

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

ЛИТЕРАТУРА

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

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

3. Tursunbay kyzy Y. A fully dynamic algorithm for recognizing and representing chordal graphs // Perspectives of System Informatics: Proc. / Ed. By A. Voronkov, et al. - Berlin a.o. Springer-Verlag, 2007. P.481-486 -(Lect. Notes Сотр. Sci.; 4378).

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

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

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

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

8. Турсунбай кызы Ы. Динамический распределенный ПН-алгоритм для раскраски w-совершенных графов // Материалы XIII Международной конференции студентов, аспирантов и молодых ученых «Ломоносов-2006»: Секция «Вычислительная математика и кибернетика» / Изд.отдел факультета ВМиК МГУ. - Москва. - 2006. - С. 54-55.

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

10. Турсунбай кызы Ы. Нахождение всех минимальных раскрасок хордального графа // Конференция-конкурс «Технологии Microsoft в информатике и программировании» - Новосибирск, 2005. - С. 137-138.

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

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

Турсунбай кызы Ы.

ЛОКАЛЬНЫЕ И ДИНАМИЧЕСКИЕ АЛГОРИТМЫ ДЛЯ АНАЛИЗА ГРАФ-МОДЕЛЕЙ СИСТЕМ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Автореферат:

Формат 60x84/8. Объём 1,1 усл. печ. л. Подписано к печати 18.11.2011 Тираж 100 экз. Заказ № 1173.

Отпечатано ЗАО РИЦ «Прайс-курьер» ул. Кутателадзе, 4г, т. 330-7202

ВВЕДЕНИЕ.

ГЛАВА 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. Разработан локальный асинхронный алгоритм для нахождения центров и медиан в сетях произвольной топологии. Реализована моделирующая программа, основанная на данном алгоритме.

ЗАКЛЮЧЕНИЕ

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.