Разработка алгоритмов комбинаторной оптимизации для анализа графовых и гиперграфовых сетей
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1 Поиск кратчайшего пути в нестационарной метрической сети . . . 15
1.1 Постановка задачи о кратчайшем пути в нестационарной
метрической сети с уcловием FIFO . . . . . . . . . . . . . . . . . 16
1.2 Обзор подходов к решению задачи TDSP . . . . . . . . . . . . . . 19
1.3 Модифицированный алгоритм ALT . . . . . . . . . . . . . . . . . 23
1.4 Выводы по главе 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2 Алгоритм RevTree приближенного решения задачи о кратчайшем
пути в ресурсоограниченной сети . . . . . . . . . . . . . . . . . . . 36
2.1 Постановка задачи о кратчайшем пути в ресурсоограниченной
сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.2 Обзор подходов к решению задачи RCSP . . . . . . . . . . . . . . 39
2.3 Приближенный алгоритм RevTree . . . . . . . . . . . . . . . . . . 41
2.4 Выводы по главе 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3 Задачи перечислительного типа на гиперграфах . . . . . . . . . . . 48
3.1 Постановка задач перечислительного типа на гиперграфах . . . . 49
3.2 Обзор подходов к решению перечислительных задач на графах и
гиперграфах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.3 Алгоритм HFindMCS для решения задачи поиска всех
максимально полных подматриц (0, 1)-матрицы инцидентности
гиперграфа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.4 Алгоритм HFindMIB для решения задачи поиска всех
максимальных индуцированных биклик гиперграфа . . . . . . . . 60
3.5 Выводы по главе 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4 Программные средства и результаты их применения . . . . . . . . . 69
4.1 Комплекс программ, реализующий разработанные алгоритмы . . 70
4.2 Анализ результативности модифицированного алгоритма ALT . . 70
4.3 Анализ результативности алгоритма RevTree . . . . . . . . . . . . 72
4.4 Анализ результативности алгоритмов HFindMCS и HFindMIB . . 74
4.5 Анализ дорожных сетей . . . . . . . . . . . . . . . . . . . . . . . 75
4.6 Выводы по главе 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
Список таблиц . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
Список иллюстраций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
Приложение А. Акт о внедрении результатов в учебный процесс СФУ . 94
Приложение Б. Акт об использовании результатов в производственно-
технологическом процессе ООО «Ар Ди Сайнс» . . . . . . . . . . . 95
Во введении к диссертации дается описание работы, раскрывается ак- туальность темы исследования, приводится обзор работ других авторов по изучаемой тематике, формулируются цели и задачи исследования, излагает- ся методология исследования, обосновывается теоретическая и практическая значимость диссертации, а также научная новизна результатов исследования.
В первой главе рассматривается задача о кратчайшем пути в нестаци- онарной метрической сети с условием FIFO. Основным результатом первой главы является модифицированный алгоритм ALT, для которого сформули- рована и доказана теорема о сложности. Данные результаты опубликованы в работах [1, 2, 6, 9–11].
Пусть задан ориентированный граф G = (V, E) без кратных дуг и петель. Для всякой дуги (x, y) ∈ E графа G заданы lxy ≥ 0 — расстояние между x и y, vxy(t) > 0—скорость движения по дуге (x,y), и определены
весовая функция wxy(t) = lxy ≥ 0 и функция прибытия Fxy(t) = t + wxy(t). vxy (t)
Говорят, что функция прибытия Fxy удовлетворяет условию FIFO, если она
является монотонной, т. е. для любых моментов времени 0 < t1 ≤ t2 верно
Fxy(t1) ≤ Fxy(t2). Тогда граф G = (V,E) с весовыми функциями wxy(t) и
монотонными функциями прибытия Fxy(t) называется нестационарной мет-
рической сетью, удовлетворяющей условию FIFO. Пусть задан путь P от вер-
шины s до вершины d, при этом отправление из вершины s осуществлено в
момент времени ts. Величина w(P, ts) отражает время прибытия в вершину d k−1
и вычисляется как w(P, ts) = ts + wxixi+1 (ti), где t0 = ts, ti+1 = Fxixi+1 (ti). i=0
Величина dist(s,d,ts) отражает самое раннее время прибытия в вершину d, при движении по кратчайшему пути,
dist(s,d,ts) = min{w(P,ts): s P d}, P
где s P d множество всех возможных путей P из вершины s в вершину d. 8
Задача о кратчайшем пути в нестационарной метрической сети с услови- ем FIFO (Time-Dependent Shortest Path, TDSP) ставится следующим образом.
Заданы: нестационарная метрическая сеть G = (V,E) с условием FIFO, (s, d, ts)-запрос.
Требуется: найти значение dist(s, d, ts) для кратчайшего (s, d, ts)-пути и по- следовательность вершин, образующих этот путь.
В работе предлагается модифицированный алгоритм ALT, основанный на при- менении потенциальных функций для ориентиров. Пусть L ⊆ V — непустое множество вершин сети, в которых установлены ориентиры. Для всякой вер- шины l ∈ L вычисляются потенциальные функции, определяемые через ве-
∇ lxy
са дуг vmax = max max[vxy(t)] > 0, где wxy = . Для всякой дуги
(x,y)∈E t∈T vmax
(x,y) ∈ E и любого t ∈ T верна оценка w∇ ≤ wxy(t). Для кратчайшего
xy
(s, d, ts)-пути справедлива оценка dist∇(s, d) ≤ dist(s, d, ts), где
dist∇(s, d) = min{w∇(P ) : s P d}. В работе вводится определение потен- P
циальных функции для нестационарной метрической сети с условием FIFO. Определение 1.1. Величина πL = max πl (x) называется потенциаль-
l∈L
ной функцией вершины x относительно множества ориентиров L. Для каж-
дой вершины x ∈ V и всякого ориентира l ∈ L определены следующие функции: πl+(x) = dist∇(l, d) − dist∇(l, x), πl−(x) = dist∇(x, l) − dist∇(d, l), πl(x) = max{0, πl+(x), πl−(x)}.
Для корректной работы модифицированного алгоритма ALT требуется, чтобы потенциальные функции обладали свойствами допустимости и преем- ственности. В работе сформулировано и доказано достаточное условие допу- стимости и преемственности потенциальной функции в виде теоремы 1.1.
Tеорема 1.1 (Достаточное условие допустимости и преемственности по- тенциальной функции). Если для нестационарной сети G = (V,E) выпол- няется неравенство треугольника dist∇(x, y) + dist∇(y, z) ≥ dist∇(x, z), то потенциальная функция πL(x) вершины x относительно множества ориен- тиров L удовлетворяет условиям
– допустимости πL(x) ≤ dist∇(x, d) ≤ dist(x, d, ts); – преемственности πL(s) ≤ dist(s, x, ts) + πL(x).
На рис. 1 представлена схема модифицированного алгоритма ALT.
G
Расстановка ориентиров Вычисление πL
ALT
Выполнение (s, d, ts)-запроса Обновление ориентиров Если i = ∆ Обновление статистики
AdaHeuris
Кратчайший (s, d, ts)-путь
Рисунок 1 — Схема модифицированного алгоритма ALT Модифицированный алгоритм ALT состоит в применении потенциаль-
ных функций πL = maxπl(x), вычисленных для каждой вершины и каждо- l∈L
го ориентира, и адаптивной эвристики расстановки ориентиров ADAHEURIS. Суть эвристики ADAHEURIS состоит в следующем. Перед выполнением пер- вого (s,d,ts)-запроса выполняется случайная расстановка заданного числа K = |L| ориентиров в вершинах графа G Далее выбранное множество ориен- тиров L периодически обновляется через каждые ∆ > 0 запросов. Во время выполнения (s, d, ts)-запроса ориентир считается эффективным, если он пред- ложил наилучшее значение πl. Наименее эффективный ориентир подлежит замене после выполнения ∆ запросов. Вычислительная сложность модифи- цированного алгоритма ALT установлена в следующей теореме.
Tеорема 1.2 (О сложности модифицированного алгоритма ALT). Мо- дифицированный алгоритм ALT находит точное решение задачи TDSP для последовательности σ, состоящей из конечного числа (s, d, ts)-запросов, в графе G = (V,E) за время O |σ|·|V|2 .
Во второй главе рассматривается задача поиска кратчайшего пути в ре- сурсоограниченной сети. Основным результатом второй главы является при- ближенный алгоритм REVTREE нахождения кратчайшего пути в сети с одним ресурсом. Сформулированы и доказаны теоремы о точности и сложности дан- ного алгоритма. Данные результаты опубликованы в работах [3, 7, 12–17, 22].
Задан ориентированный граф G = (V, E) без кратных дуг и петель.
Для всякой дуги e ∈ E заданы весовая функция w(e) > 0 и ресурсные функ-
ции ri(e) > 0, где i = 1,k. Если для вершин s,d ∈ V существует путь P,
тогда вес пути вычисляется как w(P) = w(e), а ресурсные потребности e∈P
пути как ri(P) = ri(e), где i = 1,k. Ресурсные возможности рассматрива- e∈P
емой сети определяются заданными величинами Ri ∈ R+, i = 1,k. Допу- стимым называется (s,d)-путь P, который удовлетворяет ресурсным ограни-
чениям ri(e) ≤ Ri, i = 1, k. Оптимальным (s, d)-маршрутом называется e∈P
допустимый (s, d)-путь P минимальной стоимости w(P ). Задача поиска крат- чайшего пути в ресурсоограниченной сети (Resource Constrained Shortest Path, RCSP) ставится следующим образом.
Заданы: граф G = (V, E), на дугах которого определены положительные вещественнозначные функции w(e), ri(e), величины Ri, i = 1, k, и (s, d)-запрос.
Требуется: найти в G = (V, E) оптимальный (s, d)-маршрут.
Во второй главе задача RCSP рассматривается в теоретико-графовой по- становке. Также известна постановка задачи RCSP в терминах целочисленно- го линейного программирования для нахождения точного решения. Формули- ровка задачи RCSP в терминах целочисленного линейного программирования приведена в параграфе 4.3 диссертации.
Основным результатом второй главы является алгоритм REVTREE, ко- торый является двухфазной модификацией алгоритма Дейкстры для задачи RCSP с одним ресурсным ограничением (рис. 2). В этом случае для сети G = (V,E) задана одна ресурсная функция r(e) для всех дуг e ∈ E, с ре- сурсным ограничением R. На первой фазе, исходя из функций r(e), вычисля- ется дерево минимального веса с корнем в вершине d. Это дерево определяет для всякой вершины u ∈ V такой (u,d)-путь, вес которого указывает ми- нимальный ресурс для прохождения (u,d)-пути и обозначается как π(u). На второй фазе выполняется алгоритм Дейкстры с усеченными окрестностями вершин Γ(v). Усечение происходит согласно условию r(P1) + r(e) + π(u) ≤ R, e = (v, u) ∈ E, где P1 — найденный пусть от стартовой вершины s до текущей вершины v.
G
Treer(d)
Вычисление π(u) Первая фаза
Алгоритм Дейкстры
Окрестности Γ(v) Вторая фаза
Допустимый (s, d)-путь
Рисунок 2 — Схема алгоритма REVTREE
Для алгоритма REVTREE сформулированы и доказаны теоремы о точно- сти и о сложности.
Tеорема 2.1 (О сложности алгоритма REVTREE). Алгоритм REVTREE требует O |V |2 времени и O (|V |) памяти для решения задачи RCSP с одним ресурсным ограничением.
Tеорема 2.2 (О точности решения алгоритма REVTREE). Алгоритм
REVTREE находит ε-приближенное решение задачи RCSP с одним ресурсным
ограничением, если оно существует для вершин s и d. Точность решения опре-
деляется как ε =
r(e) λmax = max > 0.
λmax λmin
−1, где λmin = min e∈E
r(e) w(e)
> 0,
e∈E w(e)
В третьей главе рассматриваются задачи перечислительного типа для сетей, представленных гиперграфом. Предложены алгоритмы решения задач нахождения всех максимально полных подматриц (0,1)-матрицы и нахож- дения всех максимальных индуцированных биклик гиперграфа, а также их теоретические оценки сложности. Данные результаты опубликованы в рабо- тах [4, 5, 8, 18–21].
Задан (n,m)-гиперграф H = (X,U) и (0,1)-матрица инцидентности I, где X — конечное множество вершин и |X| = n, U — конечное семейство ги- перребер гиперграфа и |U| = m. Множество X(u) содержит все вершины, инцидентные гиперребру u ∈ U. Множество U(x) содержит все гиперреб- ра, инцидентные вершине x ∈ X. Считается, что задан лексикографический порядок как для множества вершин X, так и для множества гиперребер U в гиперграфе H = (X,U). Одним из способов задания гиперграфа являет- ся (0,1)-матрица инцидентности I, где 1 ставится в случае, когда гиперребро содержит вершину, и 0 в противном случае. Будем называть степенью гипер- ребра u ∈ U мощность множества |X(u)|. Полной подматрицей (0, 1)-матрицы называется подматрица, все без исключения элементы которой равны 1. Мак- симально полной подматрицей называется полная подматрица, не содержащая никакой другой максимально полной подматрицы.
Подгиперграфом, индуцированным множеством вершин X′, называется H′ =(X′,U′),гдеU′ ={u′:X(u′)=X(u)∩X′ ̸=⊘,u∈U}.Вработеисполь- зуется ослабленное определение двудольности. Подгиперграф H′ = (X′,U′), индуцированный множеством вершин X′, является двудольным, если суще- ствует разбиение S0∪S1 = X′ и S0∩S1 = ⊘, такое, что для любого гиперребра u′ ∈U′ выполнено|S0 ∩X(u′)|≤1и|S1 ∩X(u′)|≤1.
Вершинным графом гиперграфа H = (X, U ) называется граф L2(H) = (X,E), множество вершин которого совпадает с множеством вер- шин X гиперграфа H, при этом две вершины графа L2(H) смежны тогда и только тогда, когда смежны соответствующие им вершины гиперграфа H.
Сформулирована и доказана теорема об эквивалентности индуцирован- ных двудольных подгиперграфов гиперграфа H и двудольных подграфов вер- шинного графа L2(H).
Tеорема 3.1 (Об эквивалентности индуцированных двудольных подги- перграфов гиперграфа H и двудольных подграфов вершинного графа L2(H)). Подгиперграф H′ = (X′,U′) является двудольным тогда и только тогда, когда в вершинном графе L2(H) гиперграфа H существует двудольный под- граф, индуцированный множеством вершин X′.
Двудольный граф называется полным двудольным графом (бикликой), если всякая вершина одной доли соединена со всеми вершинами второй доли. Подгиперграф H′ = (X′,U′), индуцированный множеством вершин X′, такой, чтоS0∪S1 =X′,S0∩S1 =⊘иU′ ={u:s0,s1 ∈X(u),s0 ∈S0,s1 ∈S1} называется полным двудольным индуцированным подгиперграфом исходного гиперграфа H. Максимальная биклика — это биклика, которая не может быть расширена путем включения дополнительных смежных вершин, или, что эк- вивалентно, для максимальной биклики не существует другой биклики, кото- рая полностью включает данную.
Задача поиска всех максимальных индуцированных биклик гиперграфа (Maximal Induced Bicliques Generation Problem for Hypergraphs, MIBGP for Hypergraphs) имеет следующий вид.
Задан: гиперграф H = (X, U ) без кратных гиперребер.
Требуется: найти множество всех максимальных индуцированных биклик.
Продемонстрируем связь между задачей нахождения максимальных ин- дуцированных биклик в гиперграфе и задачей поиска максимально полных подматриц (0, 1)-матрицы.
Для двудольного подгиперграфа H′ = (X′,U′) запишем его эквивалент- ное представление в виде (0, 1)-матрицы смежности вершинного графа L2(H′). Обозначим S0, S1 — доли подгиперграфа H′, мощности которых равны c и d, соответственно. Поскольку вершинный граф L2(H′) тоже является двудоль- ным, его матрица смежности представима в виде:
′ Oc B′
A= B′T O , (1)
d
где Oc, Od — нулевые матрицы порядка c и d, соответственно, а B′ матрица размера c × d, которая отражает смежность вершин между долями S0 и S1.
Таким образом, для поиска индуцированных биклик в гиперграфе H требуется найти такие полные подматрицы B′ матрицы смежности A вершин- ного графа L2(H), для которых будет существовать подматрица вида (1), что приводит к задаче поиска всех максимально полных подматриц (maximally complete submatrices) исходной (0, 1)-матрицы. Задача поиска всех максималь- но полных подматиц (0,1)-матрицы инцидентности гиперграфа (Maximally Complete Submatrices Problem for Hypergraph, MCSP for Hypergraph) имеет следующую постановку.
Задан: гиперграф H = (X, U ) без кратных гиперребер с (0, 1)-матрицей инцидентности I.
Требуется: найти множество всех максимально полных подматриц (0, 1)-матрицы инцидентности I.
Для решения задачи MCSP for Hypergraph в работе предлагается алго- ритм HFINDMCS поиска всех максимально полных подматриц (0, 1)-матрицы инцидентности гиперграфа (рис. 3). Полным l-уровнем (0, 1)-матрицы называ- ется множество всех ее полных подматриц с числом строк равным l. Всякую полную подматрицу инцидентности гиперграфа H = (X,U) с числом строк равным l можно описывать как подгиперграф H′ = (X′,U(X′)), где X′ ⊆ X — множество вершин, при этом |X′| = l, а U(X′) ⊆ U — множество гиперребер. Следовательно, l-уровень в терминах гиперграфов описывается следующей системой множеств Pl = {H′ = (X′, U(X′)) : |X′| = l, X′ ⊆ X}.
H
Инициализация
∆ = Deg(H)
Exit
H = HT , если ∆ = maxX(u)
u∈U
Генерация
GenerateCombinations(H ,1) P1 . .
. . GenerateCombinations(H ,∆) P∆
MCS
∀ Y′,U(Y′) Add Y,U(Y)
U(Y)̸=U(Y′)
Y,U(Y) ∆−1
P = Pl,
l=1 MCS = P∆
Фильтрация
Рисунок 3 — Схема алгоритма HFINDMCS
Алгоритм HFINDMCS решает задачу в три этапа. На этапе инициализа- ции происходит определение степени гиперграфа ∆ и переход к двойственно- му гиперграфу при необходимости. На этапе генерации для гиперграфа H и соответствующей матрицы инцидентности выполняется генерация l-уровней. На этапе фильтрации происходит очистка всех сгенерированных l-уровней для получения максимально полных подматриц (0, 1)-матрицы инцидентности ги- перграфа H.
Для решения задачи MIBGP for Hypergraphs в работе предлагается алго- ритм HFINDMIB поиска всех максимальных индуцированных биклик гипер- графа (рис. 4). Гиперграф Φ задается матрицей смежности вершинного графа L2(H). Подгиперграф Φ′ индуцированный множеством вершин S0 ⊆ XΦ и множеством гиперребер S1 ⊆ UΦ, удовлетворяющий виду (1) и S0 ∩ S1 = ⊘,
l-уровни
называется бикликой и обозначается (S0, S1). Множество всех биклик (S0, S1), где |S0| = l, будем называть l-уровнем гиперграфа Φ.
Генерация
GenerateCombinations(Φ,1) L2(H) Φ .
GenerateCombinations(Φ,∆)
′′ (S0,S1) ∆ Compare (S0,S1),(S0,S1) P =
Инициализация
P1 . P∆
H
l=1
Pl
(S0, S1) ̸⊑ (S0′ , S1′ ) Add(S0, S1)
(S0′ , S1′ ) ⊑ (S0, S1) Delete(S0′ , S1′ )
MBC(Φ) MBC(H)
Фильтрация
Рисунок 4 — Схема алгоритма HFINDMIB
Алгоритм HFINDMIB решает задачу в три этапа. На этапе инициали- зации происходит переход от исходного гиперграфа H к вершинному графу L2(H). На этапе генерации для матрицы смежности графа L2(H), представ- ленной в виде гиперграфа Φ, выполняется генерация l-уровней. На этапе фильтрации происходит очистка всех сгенерированных l-уровней для получения максимальных индуцированных биклик гипергра- фа H.
Tеорема 3.2 (О сложности алгоритма HFINDMCS). Алгоритм HFINDMCS корректно решает задачу нахождения всех максимальных ин- дуцированных биклик гиперграфа H = (X,U) со степенью ∆ за время не превышающее
O log |MCS| ·|U|2 ·∆·2∆ ·log 2∆ ·|U| .
Tеорема 3.3 (О сложности алгоритма HFINDMIB). Алгоритм HFINDMIB корректно решает задачу нахождения всех максимальных ин- дуцированных биклик гиперграфа H = (X,U) со степенью ∆ за время не
l-уровни
∀(S0′ , S1′ )
превышающее
O 22∆ · ∆ · |MBC| + ∆3 · log(22∆) + |X|2 .
В четвертой главе разработан комплекс программ, реализующий пред- ложенные алгоритмы. Алгоритмы тестировались на случайных графах и ги- перграфах и на реальных данных применительно к дорожным сетям. Данные результаты опубликованы в работах [8, 20–22].
Комплекс состоит из четырех модулей:
1. ModALT — реализует модифицированный алгоритм ALT. Находит ре- шение задачи о кратчайшем пути в нестационарной сети;
2. RevTree — реализует алгоритм RevTree. Находит решение задачи о кратчайшем пути в ресурсоограниченной сети;
3. HFindMCS — реализует алгоритм HFindMIB. Находит все максималь- но полные подматрицы (0, 1)-матрицы инцидентности сети;
4. HFindMIB — реализует алгоритм HFindMCS. Находит все максималь- ные индуцированные биклики сети.
Предлагаемые в работе алгоримы REVTREE, HFINDMIB и модифици- рованный алгоритм ALT применялись для анализа дорожных сетей. В каче- стве рассматриваемых сетей были взяты дорожные карты следующих городов: Красноярск (KJA), Томск (TOF), Новосибирск (NSK), Баку (GYD). Результаты работы каждого алгоритма представлены в табл. 1.
Таблица 1 — Результаты работы алгоритмов ALT, REVTREE, HFINDMIB
Дорожная n m сеть
TOF 3840 9639
KJA 4362 6005
NSK 7357 19106 27,838 0,680
GYD 12458 28936 69,052 0,539
ALT
REVTREE
HFINDMIB
5 4084 26,527
Время, с.
Доля вы- полнынных запросов
Время, с.
∆
MBC
Время, с.
8,151 9,030
0,483 0,849
1,708
7,286
12,212 6 7927 103,115 15,998 6 11844 252,244
5 4823 36,898
На рис. 5а) представлена тепловая карта сети KJA для решений зада- чи TDSP, где дорога обозначена красным цветом в случае, если она была более востребована в процессе маршрутизации и синим цветом в обратном случае, черным цветом обозначены ребра, которые не встретились ни в одном кратчайшем пути. Аналогичная тепловая карта представлена по результатам решения задачи RCSP для сети KJA на рис. 5б). На основе полученных алго- ритмом HFINDMIB результатов, сделаны выводы о возможной интерпретации элементов дорожной сети согласно размеру биклики.
Основываясь на информации о наиболее востребованных ребрах в се- ти можно выполнять реорганизацию дорожной сети и моделировать новые
а) тепловая карта сети KJA по результатам ре- шения задачи TDSP
б) тепловая карта сети KJA по результатам ре- шения задачи RCSP
в) карта сети KJA с бикликами размера (2, 1)
Рисунок 5 — Анализ дорожной сети KJA на основе найденных решений
объездные дороги.
В заключении диссертации сформулированы основные результаты и
выводы, полученные на основе настоящей диссертационной работы.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ
1. Разработан и теоретически обоснован модифицированный алгоритм ALT для решения задачи поиска кратчайшего пути в нестационарной метри- ческой сети, удовлетворяющей условию FIFO (теоремы 1.1 и 1.2). В алгоритме используется новая графовая модель с двумя весами. С использованием этой модели вычисляются потенциальные функции для алгоритма ALT.
2. Разработан и теоретически обоснован алгоритм REVTREE для при- ближенного решения задачи поиска кратчайшего пути в ресурсоограниченной сети с одним ресурсом (теоремы 2.1, 2.2). Алгоритм позволяет определить точность найденного решения исходя из параметров сети.
3. Сформулирована и доказана теорема об эквивалентности индуциро- ванных двудольных подгиперграфов гиперграфа и двудольных подграфах вер- шинного графа гиперграфа (теорема 3.1).
г) карта сети KJA с бикликами размера (2, 2)
4. Разработан и теоретически обоснован алгоритм HFINDMCS для по- иска всех максимально полных подматриц (0, 1)-матрицы инцидентности ги- перграфа (теорема 3.2).
5. Разработан и теоретически обоснован алгоритм HFINDMIB для по- иска всех максимальных индуцированных биклик гиперграфа (теорема 3.3). Алгоритм основан на теореме 3.1 и использует метод генерации максималь- ных биклик для каждого l-уровня гиперграфа.
6. Создан комплекс программ, реализующий разработанные алгоритмы, для проверки их результативности на случайных графах и гиперграфах и на реальных данных применительно к дорожным сетям.
Актуальность темы исследования.
В настоящее время графы и гиперграфы используются для представления
сетей из различных предметных областей. Графовые модели используются
для представления дорожных, мультисервисных и телекоммуникационных се-
тей [40, 57, 65, 68, 77, 78, 88]. Гиперграфы являются расширением классической
теории графов на случай, когда ребро графа может содержать число вершин,
отличное от двух [11]. Традиционно гиперграфы нашли практическое приме-
нение в комбинаторной химии и разработке реляционных баз данных [18, 69].
Возможность объединения нескольких вершин одним ребром дает сильный
инструмент для исследования и анализа процессов в различных сетях. В на-
стоящее время гиперграфы активно применяются при моделировании дорож-
ных и телекоммуникационных сетей, а также для построения семантических
сетей при обработке текстов на естественном языке [20, 54, 55, 59, 71, 73, 80,
89, 90]. Актуальным направлением исследований является анализ, проектиро-
вание и реструктуризация таких сетей. Значительная часть задач анализа гра-
фовых и гиперграфовых сетей сводится к проблемам определения различных
конфигураций [35]. Под конфигурацией понимается любая система подмно-
жеств конечного множества. Особо интересными конфигурациями являются
кратчайшие пути и максимальные биклики, поскольку они позволяют опреде-
лять узкие места сети, основные магистрали, выполнять предобработку для
разбиения исходной сети на подсети. Задача поиска кратчайшего пути в гра-
фе — хорошо известная задача теории графов, имеющая многие реальные при-
ложения, такие как маршрутизация в коммуникационных сетях, логистическая
оптимизация. Существует множество алгоритмов решения задачи маршрути-
зации без дополнительных ограничений на сеть [10, 13, 14]. Однако в случае,
когда на сеть накладываются дополнительные ограничения, классические ал-
горитмы для построения кратчайших путей не применимы. Помимо этого,
на производительность используемых алгоритмов существенное влияние ока-
зывает увеличение размерности анализируемых графовых и гиперграфовых
сетей. Это связано с тем, что классические алгоритмы либо не способны нахо-
дить точное решение поставленных задач, либо находят его за неприемлемое
время [49, 51, 57]. В свою очередь, задача поиска всех максимальных биклик
является труднорешаемой задачей, поскольку число биклик может экспонен-
циально зависеть от размеров исходной сети [16, 20, 72].
Задачи маршрутизации возникают в дорожных и телекоммуникационных
сетях, при этом часто приходится иметь дело с различными расширениями
задачи о кратчайшем пути, которые могут значительно повысить сложность
решения [12, 40, 47, 51, 77, 81, 86]. Более того, в дорожных сетях логистические
задачи могут решаться для отдельного района, города, края или целой стра-
ны. Большинство современных телекоммуникационных сетей являются муль-
тисервисными, поскольку предоставляют пользователям множество разнооб-
разных услуг, касающихся проводной телефонии, сотовой связи, кабельного
телевидения и передачи данных. Качество обслуживания (Quality of Service,
QoS) в мультисервисных сетях определяется параметрами, такими как полоса
пропускания, задержка, вариация задержки, стоимость и надежность передачи
данных [78, 86]. Таким образом, задача анализа качества обслуживания в те-
лекоммуникационной сети может моделироваться задачей поиска кратчайших
путей в ресурсоограниченной сети, где всякий запрос пользователя на оказа-
ние услуги предполагает определение некоторого (желательно оптимального
по затратам, например, времени или стоимости) маршрута между двумя уз-
лами с учетом ресурсных возможностей этой сети. Задачи перечислительного
типа используются в дорожных и телекоммуникационных сетях в основном
для анализа структурных элементов или выделения подсетей [20]. Задача мо-
делирования адресного пространства в телекоммуникационных сетях связана
с задачей поиска максимальных индуцированных биклик [59]. Например, мак-
симальная индуцированная биклика может определять подсеть с топологией
«звезда». Для анализа структуры дорожной сети можно использовать задачу
перечисления всех максимальных индуцированных биклик.
В анализе семантических сетей востребованы задачи перечислительного
типа, поскольку нахождение всех возможных конфигураций позволяет выде-
лять скрытые знания и взаимосвязи из таких сетей [3, 55, 71]. Учитывая, что
подобные сети представляются как гиперграф, так и (0, 1)-матрица, то по-
иск различных конфигураций можно осуществлять методами теории матриц
и теории гиперграфов. Так, наиболее часто в анализе семантических сетей ис-
следуются максимально полные подматрицы (0, 1)-матрицы и максимальные
индуцированные биклики. При этом задача выделения всех максимальных ин-
дуцированных биклик гиперграфа сводится к задаче построения конфигура-
ций — полных единичных подматриц. Заметим, что задачи поиска таких кон-
фигураций являются #P -полными [16, 72].
В настоящее время активно разрабатываются новые, модифицируются из-
вестные алгоритмы для решения задач анализа, маршрутизации и проекти-
рования дорожных, телекоммуникационных и семантических сетей, а также
исследуются подходы, повышающие производительность существующих ал-
горитмов.
Степень разработанности темы исследования.
В задачу анализа сетей входит определение эффективности сети, нахож-
дение узких мест, решение задачи о кратчайших путях, выделение подсетей
и основных магистралей и др. Предъявление дополнительных ограничений
к анализу сетей влечет за собой решение расширений задачи о кратчайшем
пути, а также решение задачи определения различных конфигураций в сети.
Задача о кратчайшем пути в нестационарной сети была исследована в ра-
боте K. L. Cooke, E. Halsey [43]. В данной работе предложена модель поиска
оптимального времени прибытия. В работе S. E. Dreyfus [49] рассмотрена
возможность применения классического алгоритма Дейкстры для нахождения
кратчайшего пути в нестационарной сети. Дальнейшие исследования включа-
ют усовершенствование алгоритма Дейкстры, выполнение предобработки ис-
ходной сети, использование новых подходов к решению задачи о кратчайшем
пути в нестационарной сети. Значительный вклад в это направление внесли
H. D. Sherali [81], D. Wagner [87], M. M. Nejad [77], D. Delling [46], Э. Х. Ги-
мади [8].
Задача о кратчайшем пути в ресурсоограниченной сети является расши-
рением классической задачи о кратчайшем пути с дополнительными ресурс-
ными функциями для каждой дуги. Задача о ресурсоограниченном кратчай-
шем пути была рассмотрена в работе H. Joksch [66]. В данной работе задача
рассматривалась в терминах целочисленного линейного программирования и
теоретико-графовой постановке, для которой был предложен алгоритм, осно-
ванный на методе динамического программирования. В работе G. Handler,
I. Zang [60] был предложен двойственный алгоритм решения для задачи о
ресурсоограниченном кратчайшем пути в терминах целочисленного линейно-
го программирования. Значительный вклад в развитие подходов к решению
задачи о кратчайшем пути в ресурсоограниченной сети внесли M. Dror [50],
I. Dumitrescu [51], K. Mehlhorn [75], M. Jepsen [65], M. Horvarth [63],
R. Hassin [61], G. Xue [88], W. Zhang [89].
Задачи поиска максимально полных подматриц и максимальных биклик яв-
ляются задачами перечисления и поиска конфигураций в сети. Такие задачи
применяются во многих прикладных областях. Поиск всех максимально пол-
ных подматриц используется в анализе формальных понятий. Его основные
идеи и сведения задачи поиска формальных понятий к задаче поиска макси-
мально полных подматриц были введены в следующих работах [16, 55, 72].
Развитие подходов к решению задачи активно исследуется российскими уче-
ными С. О. Кузнецовым, С. А. Объедковым, Д. И. Игнатовым [16, 70–72],
В. В. Быковой, Ч. М. Монгуш [3, 76]. Задача поиска максимальных индуциро-
ванных биклик связана с поиском максимально полных подматриц. Практиче-
ское применение максимальных индуцированных биклик в телекоммуникаци-
онных сетях исследовано в работе R. L. Graham, H. O. Pollak [59]. В других
областях знаний максимальные биклики исследовались Е. В. Константино-
вой [69], Инной и Игорем Зверович [92], В. Б. Поповым [20].
Все рассматриваемые в работе задачи в большинстве случаев решаются
применительно, к сетям представленным графами или гиперграфами, поэтому
эти задачи носят комбинаторный характер. Развитие дорожных и телекомму-
никационных сетей влечет за собой увеличение их сложности и размерности.
Вследствие чего актуальна разработка новых и усовершенствование существу-
ющих алгоритмов комбинаторной оптимизации для данных задач, способных
находить решение за реальное время. Именно данное направление исследует-
ся в настоящей диссертационной работе.
Цель и задачи исследования. Целью диссертационной работы является
разработка алгоритмов комбинаторной оптимизации для анализа графовых и
гиперграфовых сетей.
Для достижения цели были поставлены и решены следующие задачи.
1. Разработать и теоретически обосновать модификацию алгоритма ALT
решения задачи поиска кратчайшего пути в нестационарной метрической се-
ти, удовлетворяющей условию FIFO.
2. Разработать и теоретически обосновать приближенный алгоритм реше-
ния задачи поиска ресурсоограниченного кратчайшего пути в графе с одним
ресурсом.
3. Разработать и теоретически обосновать алгоритм решения задачи поиска
всех максимальных индуцированных биклик для графов и гиперграфов.
4. Создать комплекс программ, реализующий разработанные алгоритмы,
для проверки результативности алгоритмов на случайных графах и гипергра-
фах и на реальных данных применительно к дорожным сетям.
Научная новизна результатов, представленных в диссертации.
1. Разработана модификация алгоритма ALT для задачи поиска кратчайше-
го пути в нестационарной метрической сети, удовлетворяющей условию FIFO.
В отличие от классического алгоритма ALT, в модификации используется но-
вая графовая модель, в которой всякая дуга сети определяется статическим и
динамическим весами, интерпретируемыми как расстояние и скорость в сети.
Предложенная модификация алгоритма ALT позволяет находить точное ре-
шение задачи поиска кратчайшего пути в нестационарной метрической сети,
удовлетворяющей условию FIFO.
2. Разработан новый алгоритм R EV T REE приближенного решения задачи
поиска ресурсоограниченного кратчайшего пути в сети с одним ресурсом.
Алгоритм отличается от ранее существующих алгоритмов тем, что позволяет
получить оценку точности решения на основе параметров исходной сети.
3. Разработан новый алгоритм HF IND MIB решения задачи поиска всех
максимальных индуцированных биклик. Алгоритм отличается от ранее су-
ществующих алгоритмов тем, что в процессе генерации биклик использует
новый гиперграфовый подход. Алгоритм находит и перечисляет в лексикогра-
фическом порядке все максимальные индуцированные биклики в графовых и
гиперграфовых сетях.
Методология и методы исследования. Для решения поставленных в дис-
сертационной работе задач был применен аппарат теории графов и гипергра-
фов, теории алгоритмов, комбинаторной оптимизации, а также методы объ-
ектно-ориентированного программирования. Комплекс программ для предло-
женных алгоритмов реализован на языке С++.
Теоретическая значимость работы. Результаты диссертации представля-
ют теоретический интерес и вносят заметный вклад в изучение задач марш-
рутизации и задач перечислительного типа для графов и гиперграфов. Новые
представления графовой модели и потенциальных функций для задачи о крат-
чайшем пути в нестационарной сети с условием FIFO могут быть использова-
ны для моделирования других нестационарных сетей с различными ограниче-
ниями. Предложенный алгоритм для нахождения ресурсоограниченного пути
может быть расширен на случай многих ресурсов. Метод оценки полученно-
го решения может быть развит в общий подход для задач маршрутизации с
несколькими весовыми функциями. Подход генерации максимальных инду-
цированных биклик может использоваться для развития методов генерации
k-дольных клик гиперграфа.
Практическая значимость работы. Разработанные в диссертационной ра-
боте алгоритмы используются в Федеральном государственном автономном
образовательном учреждении высшего образования «Сибирский федеральный
университет» при подготовке бакалавров по специальностям 01.03.01 — Ма-
тематика, 01.03.02 — Прикладная математика и информатика, 02.03.01 — Ма-
тематика и компьютерные науки, при изучении дисциплин «Комбинаторные
алгоритмы», «Технологии хранения и обработки больших данных», а также
в научно-исследовательской работе магистрантов по направлению подготов-
ки 01.04.02.06 — Прикладная математика и информатика в гуманитарных и
социально-экономических науках.
Разработанные в работе алгоритмы и комплекс программ ориентированы
на эффективное применение в различных прикладных областях. В работе это
продемонстрировано на примере реальных дорожных сетей городов, в част-
1. Разработан и теоретически обоснован модифицированный алгоритм ALT
для решения задачи поиска кратчайшего пути в нестационарной метри-
ческой сети, удовлетворяющей условию FIFO (теорема 1.1). В алгоритме
используется новая графовая модель с двумя весами. С использованием
этой модели вычисляются потенциальные функции для алгоритма ALT.
2. Разработан и теоретически обоснован приближенный алгоритм R EV T REE
для решения задачи поиска кратчайшего пути в ресурсоограниченной се-
ти с одним ресурсом (теоремы 2.1, 2.2). Алгоритм позволяет определить
точность найденного решения исходя из параметров сети.
3. Сформулирована и доказана теорема об эквивалентности индуцирован-
ных двудольных подгиперграфов гиперграфа и двудольных подграфах
вершинного графа гиперграфа (теорема 3.1).
4. Разработан и теоретически обоснован алгоритм HF IND MCS для поис-
ка всех максимально полных подматриц (0, 1)-матрицы инцидентности
гиперграфа (теорема 3.2). Алгоритм HF IND MCS позволяет эффективно
находить решение для гиперграфа с малой степенью и квадратной раз-
реженной (0, 1)-матрицей инцидентности.
5. Разработан и теоретически обоснован алгоритм HF IND MIB для поиска
всех максимальных индуцированных биклик гиперграфа (теорема 3.3).
Алгоритм основан на теореме 3.1 и использует метод генерации макси-
мальных биклик для каждого l-уровня гиперграфа.
6. Создан комплекс программ, реализующий разработанные алгоритмы, для
проверки их результативности на случайных графах и гиперграфах и на
реальных данных применительно к дорожным сетям.
1. Блюмин С. Л. Полные гиперграфы. Спектры лапласианов. Мультиагент-
ные системы / С. Л. Блюмин // Управление большими системами. — 2010. —
№30. — С. 5–23.
2. Быкова В. В. Адаптивное размещение ориентиров при маршрутизации в
нестационарных сетях / В. В. Быкова, А. А. Солдатенко // Supplementary
Proceedings of the 9th International Conference on Discrete Optimization
and Operations Research and Scientific School (DOOR 2016) — Vladivostok,
Russia, September 19-23, 2016. — Published online on the CEUR-Workshop
web site, V. 1623. — P. 367–372.
3. Быкова В. В. Декомпозиционный подход к исследованию формальных кон-
текстов / В. В. Быкова, Ч. М. Монгуш // Прикладная дискретная математи-
ка. — 2019. — № 44. — С. 113–126.
4. Быкова В. В. Маршрутизация по ориентирам в нестационарных сетях /
В. В. Быкова, А. А. Солдатенко // Доклады Седьмой Международной науч-
ной конференции «Танаевские чтения», Минск, Беларусь. — 2016. — С. 40–
44.
5. Быкова В. В. Об оптимальной маршрутизации в мультисервисных теле-
коммуникационных сетях / В. В. Быкова, А. А. Солдатенко // Optimization
Problems and Their Applications (OPTA-2018): тезисы докладов VII Меж-
дународной конференции: памяти проф. А. А. Колоколова — Омск: Изд-во
Ом. гос. ун-та, 2018. — С. 26.
6. Быкова В. В. Об оценке ресурсных возможностей мультисервисных сетей /
В. В. Быкова, А. А. Солдатенко // Информационные технологии и матема-
тическое моделирование (ИТММ-2018): Материалы XVII Международной
конференции имени А.Ф. Терпугова. — Томск: Изд-во НТЛ, 2018. — C. 230–
235.
7. Быкова В. В. Оптимальная маршрутизация по ориентирам в нестационар-
ных сетях / В. В. Быкова, А. А. Солдатенко // Прикладная дискретная ма-
тематика. — 2017. — № 37. — С. 114–123.
8. Гимади Э. Х. Математические модели и методы принятия решений /
Э. Х. Гимади, Н. И. Глебов. — Новосибирск: Издательство НГУ, 2008. —
162 с.
9. Гэри М. Вычислительные машины и труднорешаемые задачи / М. Гэри,
Д. Джонсон // М.: Мир, 1982. — 416 с.
10. Емеличев В. А.Лекциипотеорииграфов/В. А. Емеличев,
О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. — М.: Книжный дом
«Либроком», 2012. — 390 с.
11. Зыков А. А.Гиперграфы/А. А. Зыков//УМН. — 1974. — Т. 29. —
№6(180). — С. 89–154.
12. Карим П. Х. Численные исследования пропускной способности транс-
портного протокола с механизмом прямой коррекции ошибок в меж-
сегментном пространстве / П. Х. Карим, П. А. Михеев, В. В. Поддубный,
С. П Сущенко // Вестн. Том. гос. ун-та. Управление, вычислительная тех-
ника и информатика. — 2020. — № 50. — С. 89–96.
13. Кормен Т. Х.Алгоритмы.Построениеианализ/Т. Х. Кормен,
Ч. И. Лейзерсон, Р. Л. Ривест, К. Штайн. — М.: Вильямс, 2016. — 1328 с.
14. Корте Ф. Комбинаторная оптимизация. Теория и алгоритмы / Ф. Корте,
Й. Фиген // М.:МЦНМО. — 720 с.
15. Кофман А. Введение в прикладную комбинаторику / А. Кофман // М.: На-
ука, 1975. — 480 с.
16. Кузнецов С. О. Интерпретация на графах и сложностные характеристи-
ки задач поиска закономерностей определенного вида / С. О. Кузнецов //
Научно-техническая информация (НТИ). — 1989. — Сер. 2. — № 1. — С. 23–
28.
17. Маркус М. Обзор по теории матриц и матричных неравенств / М. Маркус,
Х. Минк // М.: Наука, 1972. — 232 с.
18. Мейер Д. Теория реляционных баз данных / Д. Мейер // М.: Мир, 1987. —
608 с.
19. Миллер Р. Последовательные и параллельные алгоритмы: Общий подход /
Р. Миллер, Л. Боксер // М.: БИНОМ. Лаборатория знаний, 2009. — 406 с.
20. Попов В. Б. Экстремальная нумерация вершин гиперграфа и задача
объектно-признаковой кластеризации / В. Б. Попов // Динамические си-
стемы. — 2010. — №28. — С. 99–112.
21. Рассел С. Искусственный интеллект. Современный подход / С. Рассел,
П. Норвиг. — М.: Вильямс, 2007. — 1410 с.
22. Семенова Д. В. Анализ формальных понятий на языке гиперграфов /
Д. В. Семенова, А. А. Солдатенко // Математика, ее приложения и мате-
матическое образование МПМО’20 Материалы VII Международной кон-
ференции. — Улан-Удэ: Изд-во ВСГУТУ. — 2020. — С. 186–188.
23. Солдатенко А. А. Адаптивный алгоритм поиска оптимального маршрута
в нестационарной сети / А. А. Солдатенко // Программные продукты и
системы. — 2018. — № 2. — С. 321–329.
24. Солдатенко А. А. Алгоритм оптимальной маршрутизации в мультисервис-
ных телекоммуникационных сетях / А. А. Солдатенко // Прикладная дис-
кретная математика. Приложение. — 2018. — № 11. — С. 122–127.
25. Солдатенко А. А. Алгоритм HGFC нахождения формальных понятий /
А. А. Солдатенко, Д. В. Семенова // Информационные технологии и мате-
матическое моделирование (ИТММ-2020) материалы XIX Международ-
ной конференции имени А. Ф. Терпугова. — Томск: Изд-во НТЛ. — 2020. —
С. 478–482.
26. Солдатенко А. А. Верхнее оценивание стоимости оптимального маршрута
в сети с ограничением / А. А. Солдатенко // Информационные технологии
и математическое моделирование (ИТММ-2019) материалы XVIII Между-
народной конференции имени А. Ф. Терпугова. — Томск: Изд-во НТЛ. —
2019. — Часть 2. — С. 47–52.
27. Солдатенко А. А. Двухфазный алгоритм маршрутизации в нестационар-
ных сетях / А. А. Солдатенко // Прикладная дискретная математика. При-
ложение. — 2017. — № 10. — С. 168—171.
28. Солдатенко А. А. О нахождении максимально полных подматриц и их свя-
зи с бикликами в гиперграфе / А. А. Солдатенко, Д. В. Семенова // Вест-
ник Томского государственного университета. Управление, вычислитель-
ная техника и информатика. — 2021. — № 56. — С. 90—99.
29. Солдатенко А. А. О решении задачи TDSP двухфазным алгоритмом на
больших сетях / А. А. Солдатенко // Материалы республиканской научно-
практической конференции «СТАТИСТИКА и ее применения – 2017»,
Ташкент. — Ташкент, НУУз, 2017. — С. 84–91.
30. Солдатенко А. А. Полиномиальный алгоритм поиска приближенного ре-
шения в графе с ограничением / А. А. Солдатенко // Труды республикан-
ской научно-практической конференции СТАТИСТИКА и ее применения-
2019. — Ташкент, Филиал МГУ. — 2019. — С. 178–183.
31. Солдатенко А. А. Приближенный алгоритм поиска оптимального маршру-
та в сети с ограничением / А. А. Солдатенко // Прикладная дискретная
математика. Приложение. — 2019. — № 12. — С. 186–191.
32. Солдатенко А. А. Программа HFindMCS выделения максимально полных
подматриц (0, 1)-матрицы. Свидетельство о государственной регистрации
программы для ЭВМ № 2021662444. Зарегистрировано в Реестре про-
грамм для ЭВМ от 11 августа 2021 г.
33. Солдатенко А. А. Программа HFindMIB выделения максимальных инду-
цированных биклик гиперграфа. Свидетельство о государственной реги-
страции программы для ЭВМ № 2021662445. Зарегистрировано в Реестре
программ для ЭВМ от 11 августа 2021 г.
34. Солдатенко А. А. Программа RevTree для поиска ресурсоограниченного
пути в сети. Свидетельство о государственной регистрации программы
для ЭВМ № 2019616547. / А. А. Солдатенко. Зарегистрировано в Реестре
программ для ЭВМ от 24 мая 2019 г.
35. Тараканов В. Е.Комбинаторныезадачии(0,1)-матрицы/
В. Е. Тараканов // М.: Наука, 1985. — 195 с.
36. Харари Ф. Теория графов / Ф. Харари // URSS, 2018. — 304 с.
37. Acuna V. Solving the maximum edge biclique packing problem on unbalanced
bipartite graphs / V. Acuna, C. E. Ferreira, A. S. Freire, E. Moreno // Discrete
Applied Mathematics. — 2014. — V. 164, Part 1. — P. 2–12.
38. Alexe G. Consensus algorithms for the generation of all maximal bicliques /
G. Alexe, S. Alexe, Y. Crama, S. Foldes, P. L. Hammer, B. Simeone // Discrete
Applied Mathematics. — 2004. — V. 145. — P. 11–21.
39. Beineke L. Topics in Algebraic Graph Theory / L. Beineke, R. J. Wilson //
Mathematical Sciences Faculty Publications, 2008.
40. Bejerano Y. Algorithms for computing QoS paths with restoration / Y. Bejerano,
Y. Breitbart, A. Orda, R. Rastogi, A. Sprintson // IEEE/ACM Transactions on
Networking. — 2005. — V. 13. — №3. — P. 648–661.
41. Boeing G. OSMnx: New Methods for Acquiring, Constructing, Analyzing, and
Visualizing Complex Street Networks. / G. Boeing // Computers, Environment
and Urban Systems. — 2017. — V. 65. — P. 126–139.
42. Bretto A. Hypergraph theory: an introduction / A. Bretto // Springer, 2013.
43. Cooke K. L. The shortest route through a network with time-dependent
internodal transit times / K. L. Cooke, E. Halsey // Journal of Mathematical
Analysis and Applications. — 1966. — V. 14(3). — P. 493–498.
44. Damaschke P. Enumerating maximal bicliques in bipartite graphs with
favorable degree sequences / P. Damaschke // Inf. Process. Lett. — 2014. —
V. 114, Issue 6. — P. 317–321.
45. Delling D. Landmark-based Routing in Dynamic Graphs / D. Delling,
D. Wagner // In Proc. International Workshop on Experimental Algorithms
(WEA). Springer. — 2007. — 4525 of LNCS. — P. 52–65.
46. Delling D. Time-Dependent SHARC-Routing / D. Delling // J. Algorithmica. —
2011. — V. 60. — №. 1. — P. 60–94.
47. Di Puglia Pugliese L. A survey of resource constrained shortest path-problems:
exact solution approaches / L. Di Puglia Pugliese, F. Guerriero // Networks. —
2013. — P. 183–200.
48. DIMACS Implementation Challenge. Shortest Paths [Электронный ре-
сурс] : база данных дорожных графов. — 2006. — Режим доступа:
http://www.dis.uniroma1.it/challenge9/.
49. Dreyfus S. An Appraisal of Some Shortest-Path Algorithms / S. Dreyfus //
Operations Research. — 1969. — V. 17. — P. 395–412.
50. Dror M. Note on the complexity of the shortest path models for column
generation in VRPTW / M. Dror // Operation Reseatch. — 1994. — V. 42. —
P. 977–978.
51. Dumitrescu I. Improved preprocessing, labeling and scaling algorithms for
the weight-constrained shortest path problem / I. Dumitrescu, N. Boland //
Networks. — 2003. — V 42. — P. 135–153.
52. Eppstein D. Arboricity and bipartite subgraph listing algorithms / D. Eppstein //
Information Processing Letters. — V. 5, Issue 4. — 1994. — P. 207–211.
53. Eppstein D. Finding the k shortest paths / D. Eppstein // Proceedings 35th
Annual Symposium on Foundations of Computer Science. — 1994. — P. 154–
165.
54. Faure N. Biclique completion problems for multicast network design / N. Faure,
P. Chretienne, E. Gourdin, F. Sourd // Discrete Optimization. — 2007. — V. 4,
Issues 3–4. — P. 360–377.
55. Ganter B. Formal concept analysis / B. Ganter, R. Wille // Springer, 1999. —
285 p.
56. Google Maps [Электронный ресурс] : геоинформационная система. —
2021. — Режим доступа: https://www.google.com/maps/
57. Goldberg A. Better landmarks within reach / A. Goldberg, H. Kaplan,
R. Werneck // In Proc. International Workshop on Experimental Algorithms
(WEA). Springer. — 2007. — 4525 of LNCS. — P. 38–51.
58. Goldberg A. Reach for A*: Efficient point-to-point shortest path algorithms /
A. Goldberg, H. Kaplan, R. Werneck // Technical Report MSR-TR-2005-132,
Microsoft Research. Microsoft Corporation. — 2005.
59. Graham R. L. On the addressing problem for loop switching / R. L. Graham,
H. O. Pollak // The Bell System Technical Journal. — 1971. — V. 50. — №8. —
P. 2495–2519.
60. Handler G. A Dual Algorithm for the Constrained Shortest Path Problem /
G. Handler, I. Zang // Networks. — 1980. — V. 10. — P. 293–310.
61. Hassin R. Approximation Schemes for the Restricted Shortest Path Problem /
R. Hassin // Mathematics Oper. Res. — 1992. — V. 17. — P. 36–42.
62. Hermelin D.Efficientenumerationofmaximalinducedbicliques/
D. Hermelin, G. Manoussakis // Discrete Applied Mathematics. — 2020.
63. Horvath M. Solving resource constrained shortest path problems with LP-based
methods / M. Horvath, T. Kis. // Computers. — 2016. — V. 73. — P. 150–164.
64. IBM Corp.: IBM ILOG CPLEX Optimizer Studio. CPLEX User’s Manual. —
Version 12 Release 6. — 2015.
65. Jepsen M, A branch-and-cut algorithm for the capacitated profitable tour
problem / M. Jepsen, B. Petersen, S. Spoorendonk, D. Pisinger // Discrete
Optimization. — 2014 — V. 14. — P. 78–96.
66. Joksch H. C. The Shortest Route Problem with Constraints / H. C. Joksch //
Mathematical Analysis and Applecation. — 1966. — V. 14. — P. 191–197.
67. Jukna S. On covering graphs by complete bipartite subgraphs / S. Jukna,
A. Kulikov // Discrete Mathematics. — 2009. — V. 309. — P. 3399–3403.
68. Kaufman D. E. Fastest paths in time-dependent networks for intelligent vehicle-
highway systems application / D. E. Kaufman, R. L. Smith // J. Intelligent
Transportation Systems. — 1993. — V. 1. — №. 1. — P. 1–11.
69. Konstantinova E. V. Application of hypergraph theory in chemistry /
E. V. Konstantinova, V. A. Skorobogatov // Discrete Mathematics. — 2001. —
V. 235, Issues 1–3. — P. 365–383.
70. Kuznetsov S. Concept Stability for Constructing Taxonomies of Web-site
users / S. O. Kuznetsov, D. I. Ignatov In Proc. Social Network Analysis and
Conceptual Structures: Exploring Opportunities, Clermont-Ferrand — 2007.
71. Kuznetsov S. Comparing performance of algorithms for generating concept
lattices / S. Kuznetsov, S. Obiedkov // J. Exp. Theor. Artif. Intell. — 2002. —
V. 14. — P. 189–216.
72. Kuznetsov S. O. On Computing the Size of a Lattice and Related Decision
Problems / S. O. Kuznetsov // Order. — 2001. — V. 18. — №. 4. — P. 313–321.
73. Li J. Maximal Biclique Subgraphs and Closed Pattern Pairs of the Adjacency
Matrix: A One-to-One Correspondence and Mining Algorithms / J. Li, G. Liu,
H. Li, L. Wong // IEEE Transactions on Knowledge and Data Engineering. —
2007. — V. 19. — №12. — P. 1625–1637.
74. Lyu B. Maximum biclique search at billion scale /B. Lyu, L. Qin, X. Lin,
Y. Zhang, Z. Qian, J. Zhou // Proc. VLDB Endow. — 2020. — P. 1359–1372.
75. Mehlhorn K.Resourceconstrainedshortestpaths/K. Mehlhorn,
M. Ziegelmann // In Algorithms ESA. — 2000. — 1879 of LNCS.
76. Mongush Ch. M. On decomposition of a binary context without losing formal
concepts / Ch. M. Mongush, V. V. Bykova // Journal of Siberian Federal
University. Mathematics & Physics. — 2019. — № 3(12). — P. 323–330.
77. Nejad M. M. Hierarchical time-dependent shortest path algorithms for vehicle
routing under ITS / M. M. Nejad, L. Mashayekhy, R. B. Chinnam, A. Phillips //
J. IIE Transactions. — 2016. — V. 48. — №. 2. — P. 158–169.
78. Pathan A. K. Simulation Technologies in Networking and Communications:
Selecting the Best Tool for the Test. / A. K. Pathan, M. M. Monowar, S. Khan //
CRC Press. — 2017. — 648 p.
79. Prisner E. Bicliques in graphs I: bounds on their number / E. Prisner //
Combinatorica. — 2000. — V. 20. — P. 109–117.
80. Shaham E. On finding the maximum edge biclique in a bipartite graph: a
subspace clustering approach / E. Shaham, H. Yu, X. Li // Proc. of the 2016
SIAM International Conference on Data Mining (SDM). — 2016. — P. 315–323.
81. Sherali H. D.Thetime-dependentshortestpairofdisjointpaths
problem: Complexity, models, and algorithms / H. D. Sherali, K. Ozbay,
S. Subramanian // J. Networks. — 1998. — V. 31. — №. 4. — P. 259— 272.
82. Soldatenko A. Algorithm for Analysis of Road Networks Described as Graphs
and Hypergraphs / A. Soldatenko, D. Semenova // 2021 17th International
Asian School-Seminar Optimization Problems of Complex Systems (OPCS). —
2021. — P. 121–125.
83. Soldatenko A. A. On accuracy of approximation for the resource constrai-
ned shortest path problem / A. A. Soldatenko // Journal of Siberian Federal
University. Mathematics & Physics. — 2019. — № 12 (5). — P. 621–627.
84. Soldatenko A. A. On problem of finding all maximal induced bicliques of
hypergraph / A. A. Soldatenko, D. V. Semenova // Journal of Siberian Federal
University. Mathematics & Physics. — 2021. — № 14 (5). — P. 638–646.
85. Soldatenko A. A.OptimalRoutinginMulti-ServiceNetworks/
A. A. Soldatenko, V. V. Bykova // 2018 International Multi-Conference
on Industrial Engineering and Modern Technologies (FarEastCon). — 2018. —
P. 1–4.
86. Van Mieghem P. Quality of Service Routing / P. Van Mieghem, F. A. Kuipers,
T. Korkmaz, M. Krunz, M. Curado, E. Monteiro, X. Masip-BruinJ. Solé-
ParetaS. Sánchez-López // In Quality of Future Internet Services. — 2003. —
2856 of LNCS. — P. 80–117.
87. Wagner D. Speed-up techniques for shortest-path computations / D. Wagner,
T. Willhalm // In Proc. STACS. Springer. — 2007. — 4393 of LNCS. — P. 23–36.
88. Xue G. Polynomial Time Approximation Algorithms for Multi-Constrained
QoS Routing / G. Xue, W. Zhang, J. Tang, K. Thulasiraman // IEEE/ACM
Transactions on Networking. — 2008. — V. 16. — №3. — P. 656–669.
89. Zhang Y. On finding bicliques in bipartite graphs: a novel algorithm and its
application to the integration of diverse biological data types / Y. Zhang,
C. A. Phillips, G. L. Rogers, E. J. Baker, E. J. Chesler, M. A. Langston // BMC
Bioinformatics. — 2014. — V. 15.
90. Zhong-Ji F. Efficient algorithm for extreme maximal biclique mining in
cognitive frequency decision making / F. Zhong-Ji, L. Ming-Xue, H. Xiao-Xin,
H Xiao-Hui, Z. Xin // IEEE 3rd International Conference on Communication
Software and Networks. — 2011. — P. 25–30.
91. Zhu X. A three-stage approach for the resource-constrained shortest path as a
sub-problem in column generation / X. Zhu, W. E. Wilhelm // Computers &
Operations Research. — 2012. — V. 39. — Iss. 2. — P. 164–178.
92. Zverovich I. Bipartite bihypergraphs: A survey and new results / I. Zverovich,
I. Zverovich // Discrete Mathematics. — 2006. — V. 306. — P. 801–811.
Список таблиц
Читать «Разработка алгоритмов комбинаторной оптимизации для анализа графовых и гиперграфовых сетей»
Публикации автора в научных журналах
Помогаем с подготовкой сопроводительных документов
Хочешь уникальную работу?
Больше 3 000 экспертов уже готовы начать работу над твоим проектом!
5 (145 отзывов)
5 (174 отзыва)
4.1 (20 отзывов)
4.2 (5 отзывов)
4.4 (93 отзыва)
4.6 (30 отзывов)
4.7 (18 отзывов)
4.8 (13 отзывов)
4.7 (46 отзывов)
