Локальные и динамические алгоритмы для анализа граф-моделей систем

• Автор: Турсунбай кызы, Ырысгул
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Новосибирск
• Количество страниц: 92 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.

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

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

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

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

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

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

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. Суммирующая раскраска 1рафов.
ГЛАВА 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. Моделирующая программа.
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Таким образом, объектом исследования диссертации являются локальные и динамические алгоритмы для анализа граф-моделей, типичные для таких областей как распределение частот в беспроводных сетях и сетях мобильной связи, проектирование механизмов маршрутизации, изучение взаимодействия белков в биологии и др. Предметом изучения являются дискретные оптимизационные задачи распознавания, раскраски и нахождения центров и медиан графов в рамках таких динамически меняющихся и распределенных систем. Целью диссертационной работы является разработка и реализация новых локальных и динамических алгоритмов для анализа граф-моделей систем. Исследование и анализ различных классов графов, их свойств и способов представления. Распознавание и представление хордальных и расщепляемых графов, где впервые в качестве добавляемого и удаляемого элемента рассматривается полный г-вершинный граф Кг. Раскраска ™ -совершенных графов, Г-раскраска и суммирующая раскраска графов в рамках локальных вычислений. Проверка эффективности, а также сравнение результатов выработанных алгоритмов применительно к различным классам графов. Нахождение центров и медиан 1рафов в сетях произвольной топологии. При получении результатов диссертации были использованы известные методы комбинаторики, дискретной математики, теории графов и теории множеств, была проведена экспериментальная проверка разработанных алгоритмов путем тестовых программных реализаций. Исследованы основные свойства деревьев клик и деревьев индуцированных подграфов. Приведены основные теоремы, позволяющие распознать и построить деревья отобранных индуцированных подграфов графа (? Изучение основных свойств различных графов и деревьев подграфов позволило разработать новый полностью динамический алгоритм для распознавания и представления семейства хордальных и расщепляемых графов, где впервые в качестве производимых над графом модификаций служит добавление и удаление полного г-вершиниого графа Кг. Разработаны параллельные локальные алгоритмы для раскраски и>-совершенных графов, для Г-раскрасок и суммирующих раскрасок граф-моделей. Показана оптимальность алгоритмов применительно к >у-совершенным, двудольным, полным Л-дольным графам, двойным звездам и двудольным колесам. Предложен локальный асинхронный алгоритм для нахождения центра и медианы графа в произвольной сети, а также реализована моделирующая программа, основанная на данном алгоритме. Алгоритм адаптивен, он может использоваться и для решения других более специфических задач оптимизации. Полученные алгоритмы могут быть использованы на практике при распределении радиочастот в беспроводных сетях и сетях мобильной связи, при составлении рейтинга узлов в социальных и гипертекстовых сетях, сетях цитирования, а также при проектировании механизмов маршрутизации и построении технологий синхронизации в децентрализованных сетях. Основные идеи и конкретные результаты диссертационной работы обсуждались на следующих конференциях и семинарах: конференции-конкурсе «Технологии Microsoft в информатике и программировании» (Новосибирск, ), XLIII Международной научной студенческой конференции «Студент и научно-технический прогресс» (Новосибирск, ), VI Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям (Кемерово, ), XIII Международной конференции студентов, аспирантов и молодых ученых «Ломоносов- (Москва, ), Международной конференции «Развитие вычислительной техники в России и странах бывшего СССР: история и перспективы (SORUCOM )», (Петрозаводск, ), International Andrei Ershov Memorial Conference on Perspectives System Informatics (Novosibirsk, Russia, ), Семинары лаборатории «Конструирования и оптимизации программ», Новосибирск, ИСИ СО РАН, - . Основные результаты диссертационной работы опубликованы в работах, среди которых 7 статей, 2 [2, 0] из них в рецензируемых журналах. Исследования выполнялись в соответствии с планами научно-исследовательских работ ИСИ СО РАН и частично были поддержаны фантами РФФИ (№ 1-моб_снг_ст, № - -1-моб_снг_ст).