Kopeliovich_diploma.tex
\documentclass[12pt,a4paper,oneside]{article}
% ,draft
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{graphicx}
\usepackage{amsmath,amssymb}
\usepackage{rotating}
\usepackage{array}
\usepackage{multirow}
\usepackage[usenames]{color}
\usepackage[dot]{dashundergaps}
\newcounter{ijkl}
\newcommand{\setI}[1]{\setcounter{ijkl}{#1}}
\def\getI{\refstepcounter{ijkl}\arabic{ijkl}}
\def\So{\Rightarrow}
\def\t{\texttt}
\def\MySkip{\vspace{0.5em}}
\def\MySmallSkip{\vspace{0.3em}}
\def\term{}
\renewcommand{\ge}{\geqslant}
\renewcommand{\le}{\leqslant}
\renewcommand{\b}[1]{{\bf #1}}
\newcommand{\Tag}[2]{{\bf #1 : }{\it #2} \par}
%\newcommand{\MyBibitem}[4]{\bibitem{#1} #4 --- #3 \\ \emph{#2} \vspace{-0.5em}}
\newcommand{\MyBibitem}[2]{\bibitem{#1} #2 \vspace{-0.5em}}
%\newcommand{\MyBibitem}[4]{\bibitem{#1} #4 --- #3 \\ \emph{#2} \vspace{-0.5em}}
%\newcommand{\MyBibitem2}[4]{\bibitem{#1} #3 \\ \emph{#2} \vspace{-0.5em}}
\newcommand{\Pair}[2]{\langle #1,#2 \rangle}
\newenvironment{MyList}{
\begin{enumerate}
\setlength{\parskip}{-5pt}
\setlength{\itemsep}{5pt}
}{
\end{enumerate}
}
\newcounter{Theorem@cnt}
\setcounter{Theorem@cnt}{0}
\newcounter{Algorithm@cnt}
\setcounter{Algorithm@cnt}{0}
\newcommand{\Theorem}[2]{
\refstepcounter{Theorem@cnt}
\Tag{Теорема \arabic{section}.\arabic{Theorem@cnt}}{#1}
\newcounter{#2@theorem@cnt}
\setcounter{#2@theorem@cnt}{\arabic{Theorem@cnt}}
\newcounter{#2@theorem@sec}
\setcounter{#2@theorem@sec}{\arabic{section}}
}
\newcommand{\Algorithm}[1]{
\refstepcounter{Algorithm@cnt}
\vspace{0.5em}
\b{Алгоритм \Alph{Algorithm@cnt}:}
\newcounter{#1@algorithm@cnt}
\setcounter{#1@algorithm@cnt}{\arabic{Algorithm@cnt}}
}
\newcommand{\MySection}[2]{
\section{#1}
\setcounter{Theorem@cnt}{0}
\newcounter{#2}
\setcounter{#2}{\arabic{section}}
}
\newcommand{\MySubsection}[2]{
\subsection{#1}
\newcounter{#2@1}
\setcounter{#2@1}{\arabic{section}}
\newcounter{#2@2}
\setcounter{#2@2}{\arabic{subsection}}
}
\newcommand{\LinkTheorem}[1]{\arabic{#1@theorem@sec}.\arabic{#1@theorem@cnt}}
\newcommand{\LinkAlgorithm}[1]{\Alph{#1@algorithm@cnt}}
\newcommand{\LinkSubsection}[1]{\arabic{#1@1}.\arabic{#1@2}}
\pagestyle{plain}
\setlength{\parindent}{0em}
\righthyphenmin=2
\sloppy
%\raggedright
\begin{document}
\thispagestyle{empty}
\setcounter{page}{0}
\thispagestyle{empty}
\begin{center}
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ\\
Математико-механический факультет\\
\end{center}
%\vspace{1cm}
\begin{center}
Кафедра системного программирования\\
\end{center}
\vspace{2cm}
\begin{center}
\Large{Решения задач связности и двусвязности на динамически меняющихся графах} \\
\end{center}
\vspace{1cm}
\begin{center}
\normalsize{Дипломная работа студента 545 группы} \\
\large{Копелиовича Сергея Владимировича}
\end{center}
\vspace{3cm}
\noindent
\begin{center}
\small
\begin{tabular}{lcl}
Научный руководитель & \dotuline{\phantom{koshernaya podpis}} & старший преподаватель\\
& /подпись/ & Лопатин А.С.\\
Рецензент & \dotuline{\phantom{koshernaya podpis}} & доцент кафедры КТ НИУ ИТМО\\
& /подпись/& Станкевич А.С.\\
``Допустить к защите'' & \dotuline{\phantom{koshernaya podpis}} & д.ф.-м.н., проф. Терехов А.Н.\\
заведующий кафедрой, & /подпись/&\\
\end{tabular}
\end{center}
\vspace{\fill}
\begin{center}
\small
Санкт-Петербург\\2012
\end{center}
\pagebreak
\thispagestyle{empty}
\begin{center}
SAINT PETERSBURG STATE UNIVERSITY\\
Mathematics \& Mechanics Faculty\\
\end{center}
%\vspace{1cm}
\begin{center}
Software Engineering Chair\\
\end{center}
\vspace{2cm}
\begin{center}
\Large{Offline solution of connectivity and 2-edge-connectivity problems for fully dynamic graphs}\\
\end{center}
\vspace{1cm}
\begin{center}
\normalsize{Sergey Kopeliovich} \\
\large{Master's thesis}
\end{center}
\vspace{3cm}
\noindent
\begin{center}
\small
\begin{tabular}{lcl}
Supervisor & \dotuline{\phantom{koshernaya podpis}} & Senior lecturer\\
& & A.S. Lopatin\\
Reviewer & \dotuline{\phantom{koshernaya podpis}} & Associated Professor of NRU ITMO\\
& & A.S. Stankevich\\
``Approved by'' & \dotuline{\phantom{koshernaya podpis}} & Professor A. N. Terekhov\\
Head of Department, & &\\
\end{tabular}
\end{center}
\vspace{\fill}
\begin{center}
\small
Saint Petersburg\\2012
\end{center}
\pagebreak
\tableofcontents
\pagebreak
\MySection{Краткий обзор}{sAbstract}
Для задачи \term{dynamic connectivity problem} существует простое Offline решение
за время $O(k \log k)$, где $k$ --- общее количество запросов. Это решение в 1992-м году
предложил David Eppstein, подробное описание можно найти в статье \cite{EPPSTEIN}.
\MySkip
Для задачи \term{dynamic 2-edge-connectivity problem}
лучшее Online решение предложил в 2000-м году Mikkel Thorup \cite{MIKE1}. Запрос изменения графа обрабатывается
за время $O(\log^3n \log\log n)$. Offline решений, превосходящих данное по асимптотике, не существует.
\MySkip
Данная работа описывает простое Offline решение задачи \term{dynamic 2-edge-connectivity problem}, работающее за время
$O(k \log k)$, где $k$ --- общее количество запросов.
\MySkip
Кроме нового алгоритма за $O(k \log k)$ для \term{dynamic 2-edge-connectivity problem}
в данной работе описаны различные подходы к построению Offline решений \term{dynamic graph problems}.
Подходы проиллюстрированы на примере \term{dynamic connectivity problem}.
\MySection{Введение}{sIntroduction}
\MySubsection{Постановка задачи}{ssTheTask}
В этой работе речь пойдет о задачах поиска компонент связности
и компонент реберной двусвязности в динамически меняющихся
неориентированных графах. Графом $G$ называется $\Pair{V}{E}$, где $V$ ---
множество вершин графа, $E \subset V \times V$ --- множество ребер графа.
$|V|$ обозначим за $n$, $|E|$ обозначим за $m$.
{\bf Запросы изменения графа:}
\begin{MyList}
\item Добавить ребро
\item Удалить ребро
\end{MyList}
\vspace{-0.3em}
Такие запросы я, следуя терминологии, введенной в англоязычной литературе,
буду называть \emph{update-запросами}.
\vspace{0.3em}
{\bf Запросы к текущему состоянию структуры данных:}
\begin{MyList}
\item Для двух вершин определить, лежат ли они в одной компоненте
связности (и, соответственно, реберной двусвязности).
\item Для графа сказать, сколько в нем компонент связности (реберной двусвязности).
\end{MyList}
Такие запросы я буду называть \emph{get-запросами}.
\MySubsection{Обозначения}{ssNotations}
Общее количество запросов (и update-запросов, и get-запросов) я буду
обозначать символом $k$.
\MySkip
Для простоты оценки времени сложности описанных ниже алгоритмов,
предположим, что граф изначально пуст. Если мы хотим,
чтобы в нем изначально уже было $m$ ребер, можно добавить их,
сделав дополнительные update-запросы добавления.
\MySkip
В некоторых алгоритмах для анализа сложности мной используется
обратная функция Аккермана. Причина ее появления в моей работе ---
применение СНМ (Системы Непересекающихся Множеств).
Как известно из\cite{CORMEN}, амортизационное время на один запрос
у этой структуры данных равно $\alpha(n,m)$. В этой работе для
краткости и красоты формул я буду использовать обозначение~$\alpha$.
\MySkip
В работе я пользуюсь терминами offline задача, online задача.
При разработке структур данных, отвечающих на пользовательские запросы
возможна одна из двух ситуаций:
\begin{MyList}
\item Все запросы известны заранее. В таком случае это offline задача.
\item Перед ответом на следующий запрос, нужно обязательно ответить на предыдущий.
В таком случае это online задача.
\end{MyList}
\MySubsection{Англоязычные термины}{ssEnglishTerms}
На протяжении всей работы я буду пользоваться названиями задач,
заимствованными из англоязычной литературы.
Задачи, заключающиеся в поддержке
\vspace{-0.3em}
\begin{MyList}
\item компонент связности
\item компонент реберной двусвязности
\item минимального по весу остовного дерева
\end{MyList}
\vspace{-0.6em}
на динамически меняющихся графах, в англоязычной литературе называются, соответственно
\vspace{-0.3em}
\begin{MyList}
\item{fully dynamic connectivity}
\item{fully dynamic 2-edge-connectivity}
\item{fully dynamic minimum spanning tree}
\end{MyList}
Термин <<минимальное по весу остовное дерево>> я для краткости буду обозначать
MST (сокращение от minimum spanning tree).
\MySubsection{Кратко о последующих главах}{ssAboutFututre}
Работа состоит из нескольких глав. Разбиение на главы сделано таким образом, что
читать главы следует последовательно.
\setI{2}
\MySkip
В главе [\getI] подробно описана история исследования задачи.
В главе [\getI] описаны вспомогательные структуры данных, используемые затем в решениях задач fully dynamic connectivity и
2-edge-connectivity.
В главе [\getI] дано четкое описание формата входных данных алгоритмов, которые будут решать задачи fully dynamic connectivity и
2-edge-connectivity.
Далее в главе [\getI] подробно описаны известные мне offline решения fully dynamic connectivity problem.
В конце этой главы [6.5] дано описание нового offline алгоритма.
Наконец, в главе [\getI] представлена самая интересная часть работы --- новое offline
решение fully dynamic 2-edge-connectivity problem.
В той же главе, в части [7.1],
описано оптимальное решение задачи в случае когда ребра только добавляются в граф.
\MySection{Существующие решения}{sExistSolutions}
Прежде всего стоит отметить, что
описание существующих решений уже хорошо изложено в \cite{MIKE2} и в \cite{MIKE1}.
\MySkip
\Theorem{Если задача \term{fully dynamic minimum spanning tree} имеет
решение, обрабатывающее $k$ запросов за время $f(k)$, то задача \term{fully dynamic connectivity},
имеет решение, обрабатывающее $k$ запросов за время $O(f(k))$}{ConnToMST}
\b{Доказательство:} подробно о сведении можно прочитать в \cite{FRED} (стр. 21-22).
\MySkip
Далее я приведу достижения по решению задачи
\term{fully dynamic connectivity problem} и
\term{fully dynamic 2-edge-connectivity problem}
в хронологическом порядке.
Почти все оценки времени работы, указанные ниже, \term{амортизационные}.
\vspace{1em}
{\bf Задача fully dynamic connectivity}
Читая нижеприведенный список, важно помнить теорему [\LinkTheorem{ConnToMST}].
\MySmallSkip
{\bf 1985} -- Fredrickson изобрел новую структуру данных, \term{topology trees}.
Эта структура данных позволяет решать задачу \term{fully dynamic minimum spanning tree}
за время $O(\sqrt{m})$ на один update-запрос и $O(\log n)$ на один get-запрос \cite{FRED}.
\MySmallSkip
{\bf 1992} -- Eppstein et al. улучшили время на update-запрос до $O(\sqrt{n})$.
Один get-запрос обрабатывается в этом алгоритме за время $O(1)$. Для этого
они использовали \term{sparsification technique} \cite{EPPSTEIN2}.
\MySmallSkip
{\bf 1992} -- Eppstein предложил Offline алгоритм для решения \term{fully dynamic minimum spanning tree},
обрабатывающий $k$ update-запросов за время $O(k \log k)$ \cite{EPPSTEIN}.
\MySmallSkip
{\bf 1995} -- Monika Henzinger и Valerie King предложили первый полилогарифмический алгоритм для решения
\term{fully dynamic minimum spanning tree}. Алгоритм был рандомизированным и update-запросы обрабатывал за $O(\log^3n)$,
а get-запросы за время $O(\log n / \log\log n)$ \cite{KING3}.
\MySmallSkip
{\bf 1996} -- Monika Henzinger и Mikkel Thorup улучшили рандомизированную идею 1995-го года до $O(\log^2n)$ на запрос.
\MySmallSkip
{\bf 1997} -- Monika Henzinger и Valerie King предложили детерминированный алгоритм обрабатывающий
update-запрос за время $O(n^{\frac{1}{3}} \log n)$ и get-запрос за время $O(1)$ \cite{KING1}
\MySmallSkip
{\bf 1998} -- Mikkel Thorup, Jacom Holm, Kristian Lichtenberg предложили
детерминированный алгоритм с оценкой $O(\log^2n)$ на update-запрос, \\ $O(\log n / \log\log n)$ на get-запрос
и используемой памятью $O(m+n\log{n})$\cite{MIKE2}.
\MySmallSkip
{\bf 2000} -- Mikkel Thorup предложил детерминированный алгоритм с оценкой $O(\log n \log\log^3 n)$
на update-запрос, $O(\log n / \log\log\log n)$ на get-запрос и используемой памятью $O(m)$ \cite{MIKE1}.
В той же работе Mikkel Thorup улучшил используюмую память алгоритма 1998-го года до $O(m)$.
\MySmallSkip
{\bf 2004} -- Mihai Patrascu и Eric Demaine показали доказали оценку для Online алгоритмов: если
update-запрос обрабатывается за время $O(\log n \cdot x)$ (где $x$ > 1),
то get-запрос обрабатывается за время $\omega(\log n / \log x)$ \cite{PATRASCU}.
\MySkip
Итог можно подвести следующей таблицей:
\MySmallSkip
\begin{tabular}[l]{|p{1cm}|p{3.5cm}|p{8.5cm}|}
\hline
Год & Время~обработки $k$~запросов & Комментарий \\
\hline
1992 & $O(k \log k)$ & Offline решение через сведение к MST \\
\hline
2000 & $O(k \log k \log\log^3 k)$ & Лучшее online решение \\
\hline
\textcolor{red}{2012} &
\textcolor{red}{$O(k \log k)$} &
\textcolor{red}{Offline решение, не использующее MST} \\
\hline
\end{tabular}
\vspace{0.8em}
В последней строке таблицы приведено достижение, описанное в данной работе.
Оно не улучшает асимптотику, но проще чем идея предложенная Дэвидом Эппштейном.
\vspace{1em}
{\bf Задача fully dynamic 2-edge-connectivity}
\MySmallSkip
{\bf 1991} -- Fredrickson обобщил свою идею для 1-connectivity до 2-edge-connectivity.
Update-запрос обрабатывался за время $O(\sqrt{m})$, get-запрос за время $O(\log n)$ \cite{FRED}.
\MySmallSkip
{\bf 1993} -- Eppstein, применив \term{sparsification technique}, получил время $O(\sqrt{n})$ на один
update-запрос \cite{EPPSTEIN2}.
\MySmallSkip
{\bf 1997} -- Monika Henzinger и Valerie King предложили рандомизированный алгоритм, обрабатывающий
update-запросы за время $O(log^5n)$ \cite{KING2}.
\MySmallSkip
{\bf 1998} -- Mikkel Thorup, Jacom Holm, Kristian Lichtenberg предложили детерминированный алгоритм, обрабатывающий
update-запросы за время $O(log^4n)$ \cite{MIKE2}.
\MySmallSkip
{\bf 2000} -- Mikkel Thorup предложил детерминированный алгоритм с оценкой $O(\log^3n \log\log n)$
на update-запрос, $O(\log n)$ на get-запрос и используемой памятью $O(m)$ \cite{MIKE1}.
\MySkip
Итог можно подвести следующей таблицей:
\MySmallSkip
\begin{tabular}[l]{|p{1cm}|p{3.5cm}|p{8.5cm}|}
\hline
Год & Время~обработки $k$~запросов & Комментарий \\
\hline
1997 & $O(k \log^5 k)$ & Первое полилогарифмическое online решение \\
\hline
2000 & $O(k \log^3 k \log\log k)$ & Лучшее online решение \\
\hline
\textcolor{red}{2012} &
\textcolor{red}{$O(k \log k)$} &
\textcolor{red}{Offline решение} \\
\hline
\end{tabular}
\vspace{0.8em}
В последней строке таблицы приведено достижение, описанное в данной работе.
\MySkip
Так же, стоит заметить,
что я не обнаружил достижений по улучшению асимптотики худшего случая времени работы,
появившихся после 2001-го года. Например, я просмотрел все
публикации по ключевому слову \emph{Dynamic} с конференций
\emph{ACM-SIAM Symposium on Discrete Algorithms} за 2001-2012 года, а также
публикации авторов David Eppstein, Mikai Patrascu, Mikkel Thorup, Valerie King, Monika Henzinger, Giuseppe Italiano, Eric Demaine,
т.е. всех тех, чьему авторству принадлежат существующие ныне оптимальные алгоритмы и оценки из области \term{Dynamic Connectivity}.
В дополнении с только что приведенной таблицей этот факт представляется мне весьма удивительным.
\MySection{Вспомогательные структуры данных}{sAdditionalDS}
\MySubsection{Система Непересекающихся Множеств}{ssDSU}
Для некоторых решений \term{fully dynamic connectivity problem}
нам понадобится структура данных \emph{Система Непересекающихся Множеств} (или, более кратко, СНМ).
Подробнее о ней и об оценках времени работы можно прочесть в книге Кормена \cite{CORMEN}.
Структура оперирует с множеством $V$.
Начинает она с того, что каждый элемент $V$ лежит
в отдельном множестве.
\begin{MyList}
\item \b{Init}()
\item \hspace{2em} \b{for} $v \in V$
\item \hspace{4em} p[v] = v, size[v] = 1
\end{MyList}
\t{size[v]} --- размер множества, \t{p[v]} --- ссылка вершины на следующую.
Таким образом, каждое множество представлено в виде дерева. Корнем дерева является вершина,
ссылающаяся на себя саму (\t{p[v] = v}).
Операция \emph{Get} возвращает представителя множества.
Для всех вершин одного множества результат будет одним и тем же. Для
двух вершин разных множеств результат будет разным. С помощью
процедуры \emph{Get} можно определять, лежат ли две вершины в одном множестве.
Представителем дерева у нас будет его корень. Собственно \emph{Get} поднимается от
любой вершины $v$ до корня и возвращает его.
Здесь также используется эвристика сжатия путей.
\begin{MyList}
\item \b{Get}(v)
\item \hspace{2em} \b{return} v == p[v] ? v : (p[v] = \b{Get}(p[v]))
\end{MyList}
Операция \emph{Join} объединяет два множества в одно. Множество, в котором лежит
вершина $a$, и множество, в котором лежит вершина $b$.
Для этого \emph{Join} ссылку одного из двух корней направляет на второй.
Здесь используется эвристика <<выгодно меньшее множество подвешивать к б\emph{о}льшему>>
\begin{MyList}
\item \b{Join}(a, b)
\item \hspace{2em} a = Get(a)
\item \hspace{2em} b = Get(b)
\item \hspace{2em} \b{if} a = b \b{then}
\item \hspace{4em} \b{return} // вершины лежат в одном множестве
\item \hspace{2em} \b{if} size[a] < size[b] \b{then}
\item \hspace{4em} swap(a, b)
\item \hspace{2em} // теперь \t{a} является корнем б\emph{о}льшего множества.
\item \hspace{2em} p[b] = a
\item \hspace{2em} size[a] += size[b]
\end{MyList}
И \emph{Join}, и \emph{Get} работают за амортизированное время $O(\alpha)$.
Доказательство можно прочесть в первоисточнике --- работе Роберта Тарьяна 1975 года \cite{Tarjan} или в Кормене \cite{CORMEN}.
\MySubsection{Структуры данных с откатами назад}{ssOtkat}
Следующий инструмент, который нам потребуется, --- структуры данных с возможностью
отката к предыдущим версиям.
\MySkip
На самом деле, любую структуру данных можно научить откатывать состояние к предыдущим версиям.
Для этого достаточно хранить стек пар $\langle$адрес, значение$\rangle$ ---
адреса изменяемых ячеек памяти и старые значения этих ячеек.
Теперь каждую операцию присваивания нужно
обернуть в специальную функцию, которая перед изменением памяти
кладет нужную информацию в стек.
\MySkip
Откатиться к предыдущей версии = снять со стека несколько последних операций
и выполнить их в обратном порядке.
\MySkip
Запомнить версию (чтобы в будущем можно было к ней откатываться) =
запомнить указатель на вершину стека.
\MySkip
Откат --- операция необратимая, если у нас были версии $V_1, V_2, \ldots, V_9$ и
мы откатимся к версии $V_2$, все версии кроме $V_1$ и $V_2$ будут навсегда забыты.
\MySkip
\Theorem{Пусть есть две версии --- $A$ и $B$. $B$ была порождена из $A$.
Время, требуемое на откат от $B$ к $A$, асимптотически не превышает времени,
требуемого на внесение изменений при порождении $B$ из $A$}{otkat}
\b{Доказательство:} \hspace{2em}Пусть во время внесения изменений, у нас есть только одна операция для изменения памяти ---
\t{set}, меняющая значение ровно одного байта.
Время требуемое на откат = $O$(количества вызовов процедуры \t{set}) = $O$(времени, потраченного на внесение изменений).
\b{Следствие:} \hspace{2em}В оценках асимптотики времени работы алгоритмов
временем работы откатов к предыдущим версиям можно пренебречь.
\MySection{Формат входных данных}{sInputFile}
В этой главе мы сформулируем формат входных данных и сделаем первый шаг в решении произвольной
задачи из области dynamic graphs --- преобразуем формат входных данных к удобному для работы виду.
\MySkip
Итак, входные данные.
Поступают update-запросы двух видов --- \t{"ADD a b"}, \t{"DEL a b"}.
Гарантируется, что к моменту, когда поступает запрос \t{"DEL a b"}, ребро в графе присутствует.
Нужно после каждого update-запроса знать текущее количество компонент связности (или, соответственно,
реберной двусвязности) и уметь
отвечать на get-запрос \t{"GET a b"} --- лежат ли вершины $a$ и $b$ в одной компоненте
связности (или, соответственно, реберной двусвязности).
\MySkip
Пусть общее количество запросов (и get, и update) равно $k$.
Запросы пронумеруем числами от $0$ до $k-1$ ($q_0, q_1, \ldots, q_{k-1}$).
Будем говорить, что у нас есть $k+1$ момент времени
(в $i$-й момент времени уже выполнены все update-запросы с номерами от $0$ до $i-1$).
Будем также говорить, что $i$-й зарос случился в момент времени $i$.
\MySkip
Мы решаем задачу Offline, т.е. нам заранее доступны все запросы.
Поэтому можно все update-запросы модифицировать
следующим образом: ребро $\Pair{a}{b}$ в момент времени $L$ добавилось, в момент времени $R$ удалилось.
$L$ --- номер запроса \t{"ADD a b"}. $R$ --- номер запроса \t{"DEL a b"}.
Если какое-то ребро в конце не удалилось, скажем, что оно удаляется в момент времени $k+1$.
\MySkip
Теперь у нас вместо пары запросов \t{ADD}, \t{DEL} есть один запрос $\langle a,b,L,R \rangle$ ---
добавить ребро $\Pair{a}{b}$
так, чтобы оно присутствовало во все моменты от $L$+$1$ до $R$ включительно.
Данное преобразование update-запросов, если мы использовали сортировку подсчетом,
заняло у нас $O(k+n)$ времени. Новые update-запросы будем также называть ребрами-запросами.
\MySkip
В итоге у нас есть запросы типа get (q.type = \t{get}), и запросы-ребра (q.type = \t{update}).
У update-запросов есть свойства q.a, q.b --- номера вершин, которые соединяет ребро и
q.L, q.R --- моменты времени, когда ребро добавлялось и удалялось, соответственно.
Входные данные --- массив запросов q.
\MySection{Связность}{sConn}
В этой части работы я полностью разберу множество offline решений \term{dynamic connectivity problem}.
Все подходы, описанные ниже, так или, иначе, можно
обобщить до решения \term{dynamic 2-edge-connectivity problem}.
\MySubsection{Только добавление ребер: \\ Online решение за $O(\alpha)$ на запрос}{ssConnOnline}
Если ребра только добавляются в граф, решением является в чистом виде СНМ.
Секрет остальных offline решений заключается в том, что добавление ребра ---
дешевая операция, а удаление можно не делать, если удаляемое ребро в граф не добавлять.
\MySubsection{Offline решение за $O(k)$ на запрос}{ssConnK}
Для каждого момента времени возьмем все те ребра, которые в соответствующий момент времени добавлены и
выделим компоненты связности за $O(k)$. Каждая компонента связности покрашена в свой цвет, что
позволяет теперь за $O(1)$ отвечать на get-запросы.
\MySubsection{Offline решение за $O(\sqrt{k} \alpha)$}{ssConnSqrtK}
Разобьем моменты времени на группы (отрезки) по $\sqrt{k}$ моментов в каждой группе.
Научимся обрабатывать за $O(k)$ все get-запросы в любой из групп. Пусть наша группа --- это отрезок времени $[L..R]$.
Давайте возьмем все ребра-запросы, которые во все моменты времени от $L$ до $R$ присутствуют в графе.
Т.е. $q_i: (q_i.L < L)$ \t{and} $(q_i.R \ge R)$. Добавим эти ребра в граф. Добавление ребра обрабатывается
системой непересекающихся множеств.
Чем отличаются моменты времени $L..R$? Тем, что некоторые ребра-запросы присутствуют в графе не во все моменты времени
от $L$ до $R$. Это такое $q_i$, что $(q_i.L < R)$ \t{and} $(q_i.R \ge L)$.
\MySkip
Чтобы получить теперь структуру данных, умеющую отвечать на get-запросы для момента времени $i \in [L..R]$, нужно сделать не более $\sqrt{k}$
добавлений ребер. После этого все сделанные изменения следует отменить (откатить, см. [\LinkSubsection{ssOtkat}]).
\MySkip
Чтобы $\sqrt{k}$ добавлений ребер работали за $O(\sqrt{k}\cdot\alpha)$ нужно предварительно сделать сжатие всех путей за время $O(k)$.
\Algorithm{sqrtK}
\begin{MyList}
\item tn := k + 1
\item M := $\lbrack \sqrt{k} \rbrack$
\item \b{for} (i = 0; i $\cdot$ M < tn; i++) \{
\item \hspace{2em} L = i $\cdot$ M
\item \hspace{2em} R = min(i $\cdot$ M + M - 1, tn - 1)
\item \hspace{2em} // обрабатываем отрезок моментов времени [L..R]
\item \hspace{2em} множество ребер-запросов A = \{ $q_i: q_i.L < L$ \t{and} $q_i.R \ge R$ \}
\item \hspace{2em} множество ребер-запросов B = \{ $q_i: q_i.L < R$ \t{and} $q_i.R \ge L$ \}
\item \hspace{2em} // оба множества мы нашли за время $O(k)$, |B| = $O(\sqrt{k})$
\item \hspace{2em} инициализация СНМ
\item \hspace{2em} \b{for} $e \in A$ : Join(e.a, e.b) --- добавляем ребра
\item \hspace{2em} \b{for} $e \in A$ : Get(e.a), Get(e.b) --- сжатие путей
\item \hspace{2em} текущее состояние СНМ: base
\item \hspace{2em} \b{for} $t \in [L..R]$ \{
\item \hspace{4em} \b{for} $e \in B$
\item \hspace{6em} \b{if} $e.L < t$ \t{and} $e.R \ge t$
\item \hspace{8em} Join(e.a, e.b)
\item \hspace{4em} // новые ребра мы добавили за время $O(\sqrt{k})$
\item \hspace{4em} {\bf сейчас можно ответить на все get-запросы}
\item \hspace{4em} откатываем состояние СНМ к моменту base
\item \hspace{2em} \}
\item \}
\end{MyList}
\MySubsection{Offline решение за $O(\log^2k / \log\log k)$}{ssConnLogLogK}
Обобщим идею, описаную выше, до дерева отрезков (segment tree) \cite{DeBerg} на моментах времени.
Чтобы обработать все моменты времени $[L..R]$, можно сперва обработать моменты времени $[L..M]$, а
затем моменты времени $[M$+$1..R]$, где $M = \lbrack\frac{L+R}{2}\rbrack$.
Решением задачи будет рекурсивная процедура, которая получает некоторый отрезок времени $[L..R]$ и массив запросов.
На каждом шаге эта процедура добавляет в граф все ребра-запросы,
которые существуют во все моменты времени от $L$ до $R$ включительно.
Далее процедура делит отрезок времени пополам, и от каждой половины вызывается рекурсивно, передавая внутрь, то множество
запросов-ребер, которые в какой-то момент еще предстоит добавить в граф.
\Algorithm{logKlogK}
\begin{MyList}
\item \b{go}( $queries$, L, R ) \{
\item \hspace{2em} \b{if} L = R
\item \hspace{4em} \b{for} q $\in$ $queries$
\item \hspace{6em} \b{if} ($q.type$ = \t{get})
\item \hspace{8em} $q.answer$ := (Get(q.a) == Get(q.b))
\item \hspace{4em} \b{return}
\item \hspace{2em} текущее состояние СНМ: base
\item \hspace{2em} $queries_2$ := $\emptyset$
\item \hspace{2em} \b{for} q $\in$ $queries$
\item \hspace{4em} \b{if} ($q.type$ = \t{update}) \t{and} ($q.L < L$) \t{and} ($q.R \ge R$)
\item \hspace{6em} Join(q.a, q.b)
\item \hspace{4em} \b{else} \b{if} ($q.type$ = \t{get}) \t{or} ($q.L < R$) \t{and} ($q.R \ge L$)
\item \hspace{6em} $queries_2$.add(q)
\item \hspace{2em} M := $\lbrack\frac{L + R}{2}\rbrack$
\item \hspace{2em} \b{go}($queries_2$, L, M)
\item \hspace{2em} \b{go}($queries_2$, M+1, R)
\item \hspace{2em} откатываем состояние СНМ к моменту base
\item \}
\item \b{main}() \{
\item \hspace{2em} инициализация СНМ
\item \hspace{2em} \b{go}($all\_queries$, 0, k)
\item \}
\end{MyList}
Оценим время работы алгоритма \LinkAlgorithm{logKlogK}.
\MySkip
\Theorem{$|queries_2| \le R-L+1$}{BQueries}
\b{Доказательство:} если ребро-запрос попало в $queries_2$, значит или $q.L \in [L..R]$, или $q.R \in [L..R]$.
А поскольку все координаты $L$ и $R$ попарно различны (за исключением фиктивного $R$, появляющегося, если
ребро так и не будет удалено), то размер множества $queries_2$ не больше длины отрезка $[L..R$].
\Tag{Следствие}{$|queries| \le R-L+1$}
\MySkip
\Theorem{Cуммарная длина массивов $queries$ по всем состояниям рекурсии равна $O(k \log k)$}{BSumQueries}
\b{Доказательство:} глубина рекурсии $\log k$. На каждом уровне рекурсии каждый момент времени встречается не более чем
в одной ветви рекурсии, т.е. на одном уровне рекурсии суммарная длины отрезков времени = $O(k)$. Следовательно
суммарная длина отрезков времени по всем состояниям = $O(k) \cdot \log k$ = $O(k \log k)$. А, значит,
по теореме [\LinkTheorem{BQueries}], суммарная длина массивов $queries$ тоже не более $O(k \log k)$.
\MySkip
\Theorem{Каждый get-запрос обработается ровно один раз, в соответствующем листе дерева рекурсии.}{BNumOfGets}
\MySkip
\Theorem{Алгоритм \LinkAlgorithm{logKlogK} работает за время $O(k \log k \cdot tJoin$+$k \cdot tGet))$.\\
Где $tJoin$ --- время работы операции Join в СНМ, а $tGet$ --- время работы операции Get в СНМ.}{TimeAlgoB}
\b{Доказательство:} Запрос Get к СНМ по теореме [\LinkTheorem{BNumOfGets}] вызывается не более $k$ раз.
Запрос Join к СНМ вызывается не более одного раза для каждого элемента массива $queries$ значит,
по теореме [\LinkTheorem{BSumQueries}], запрос Join к СНМ вызывается $O(k \log k)$ раз.
\MySkip
Осталось оценить время работы СНМ.
Реализация СНМ, описанная ранее в главе [\LinkSubsection{ssDSU}] устроена так, что Join вызывает Get.
Поэтому $tGet$ = $O(tJoin)$, и по сути нас интересует время работы только одного запроса Join.
Один запрос к СНМ работает, казалось бы, за амортизационное время $O(\alpha)$,
но в нашем случае эвристика сжатия путей в худшем случае не работает, т.к., сделав
сжатие путей в некоторой версии СНМ, сжатие путей во всех родительских версиях мы не делаем.
Поэтому, когда мы сделаем откат к родительской версии, эффект сжатия путей пропадет.
На самом деле нас интересует не амортизационное время работы, а время на один запрос в худшем случае.
Наша СНМ дает оценку в худшем случае на один запрос $\theta(\log k)$. Лучшая же с
точки зрения <<время работы одного запроса в худшем случае>>
реализация СНМ дает время $\theta(\log k / \log\log k)$ на один запрос \cite{DSU}.
Получается, что суммарное время выполнения всех $O(k \log k)$ операций с СНМ равно $O(k \log^2 k / \log\log k)$
\MySubsection{Offline решение за $O(\log k)$}{ssConnLogK}
\Theorem{Сжатие компонент связности}{cc} Если в графе $G = \Pair{V}{E}$ всегда присутствует набор ребер $A$
(нет update-запросов, удаляющих ребра из $A$), то можно
построить новый граф $G_2$, вершинами которого будут компоненты связности графа $\Pair{V}{A}$, а множество
ребер = $\{\Pair{color[a]}{color[b]} : \Pair{a}{b} \in E \setminus A \}$.
Здесь $color[a]$ --- номер компоненты связности, в которой лежит вершина $a$.
При переходе к новому графу запросы (и update-запросы, и get-запросы)
следует поменять следующим образом: $a \rightarrow color[a]$ для всех вершин $a$, участвующих в запросе.
\b{Утверждение теоремы:}
результаты новых запросов типа \t{get} на графе $G_2$ будут совпадать
с результатами старых запросов на графе $G$.
\MySkip
\b{Доказательство:}
1. Добавим в граф $G_2$ петли, тогда любому пути $p_1, p_2, \ldots, p_k$ в графе $G$
соответствует путь $color[p_1], color[p_2], \ldots, color[p_k]$ в графе $G_2$. Значит, если $a$ и $b$
связны в $G$, то $color[a]$ и $color[b]$ связны в $G_2$.
2. Пусть в графе $G$ нет пути из $a$ в $b$, значит, после добавления новых ребер не появилось пути из
компоненты связности~$a$ в компоненту связности~$b$. Поэтому в графе $G_2$ вершины $color[a]$ и $color[b]$ не связны.
\MySkip
\Theorem{Редукция графа}{reduction}
Если сейчас $G$ пуст (не содержит ребер), а запросы затрагивают только
множество вершин $B$, то можно все запросы рассматривать,
как запросы к меньшему графу $G_2 = \Pair{B}{\varnothing}$.
\b{Утверждение теоремы:}
Количество вершин в графе $G_2$ = $O(k)$, где $k$ --- общее количество запросов.
Результаты get-запросов над $G$ и $G_2$ одинаковы.
\MySkip
\b{Доказательство:}
1. $|B| \le 2k$ (т.к. один запрос влияет на две вершины, значит, у нас не более $2k$ различных вершин).
2. Ни одно ребро никогда не будет смежно $V \setminus B$. Поэтому результат get-запроса на $\Pair{V}{E}$ равен результату
get-запроса на $\Pair{B}{E}$ для любого множества ребер $E$.
\MySkip
Решением задачи будет рекурсивная процедура, которая на каждом шаге
добавляет все ребра, которые точно нужно добавить,
делит отрезок времени пополам, сжимает компоненты связности в вершины (т.е. создает новый граф),
из нового графа выкидываются вершины, не используемые в ребрах-запросах.
Эту рекурсивную процедуру изначально следует вызвать от множества всех запросов и отрезка $[0..k]$.
\Algorithm{logK}
\begin{MyList}
\item \b{go}( G, $queries$, L, R ) \{
\item \hspace{2em} // $G = \Pair{V}{\varnothing}$, нам важно только множество вершин $V$
\item \hspace{2em} \b{if} L = R
\item \hspace{4em} Если $queries$ содержит get-запрос, обработать
\item \hspace{4em} \b{return}
\item \hspace{2em} A := $\emptyset$.
\item \hspace{2em} $queries_2$ := $\emptyset$
\item \hspace{2em} \b{for} q $\in$ $queries$
\item \hspace{4em} \b{if} ($q.type$ = \t{update}) \t{and} ($q.L < L$) \t{and} ($q.R \ge R$)
\item \hspace{6em} A.add(q)
\item \hspace{4em} \b{else} \b{if} ($q.type$ = \t{get}) \t{or} (($q.L < R$) \t{and} ($q.R \ge L$))
\item \hspace{6em} $queries_2$.add(q)
\item \hspace{2em} сожмем компоненты графа $\Pair{V}{A}$, получим новый граф $G_2$
\item \hspace{2em} $G_3$ = $G_2$ - вершины, не участвующие в $queries_2$
\item \hspace{2em} M := $\lbrack\frac{L + R}{2}\rbrack$
\item \hspace{2em} \b{go}($G_3$, $queries_2$, L, M)
\item \hspace{2em} \b{go}($G_3$, $queries_2$, M+1, R)
\item \}
\item \b{main}() \{
\item \hspace{2em} инициализация СНМ
\item \hspace{2em} \b{go}($all\_queries$, 0, k)
\item \}
\end{MyList}
Оцени время работы алгоритма \LinkAlgorithm{logK}.
Пусть длина отрезка $[L..R]$ = $K$.
\MySkip
\Theorem{Алгоритм \LinkAlgorithm{logK} работает за время $O(K \log K)$.}{logK@time}
\MySkip
\b{Доказательство:} запишем реккурентное соотношение на время работы рекурсивной функции.
$T(K) = O(|queries|) + T(K / 2) + T(K / 2)$
Как мы уже знаем из теоремы \LinkTheorem{BQueries}, $|queries| = O(K)$.
Решив реккурентность, получаем время работы $O(K \log K)$.
\MySection{Реберная двусвязность}{sConn2}
\MySubsection{Только добавление ребер: \\ Offline решение за $O(\alpha)$ на запрос}{ssConn2Online}
Научимся сперва online обрабатывать запрос добавления ребра в граф. Будем поддерживать лес
компонент реберной двусвязности. Каждую компоненту связности (дерево) будем хранить как подвешенное ориентированное дерево.
Т.е. у каждой вершины \t{v} есть отец \t{parent[v]}, если вершина \t{v} --- корень дерева, то пусть \t{parent[v]} = -1.
\MySkip
Обработка запроса состоит из двух случаев.
\MySkip
1. Если концы ребра принадлежат одной компоненте связности, то новое ребро образует ровно один цикл.
При этом все вершины нового цикла лежат теперь в одной компоненте реберной двусвязности.
Этот цикл можно сжать в новую вершину за время $O(Len \cdot \alpha)$, где $Len$ --- длина цикла.
При сжатии цикла используется СНМ.
\MySkip
2. Если концы ребра принадлежат разным компонентам связности, то новых циклов не образуется, и
нужно одну компоненту связности (дерево) подвесить к другой (к другому дереву).
Чтобы это можно было просто сделать, достаточно чтобы один из двух концов ребра был корнем дерева.
Обозначим это условие \t{[*]}.
Действительно, если у нас есть ребро $\Pair{a}{b}$, и его конец $a$ --- корень своего дерева,
то одной операцией \t{parent[b]~:=~a}, мы соединим деревья в новое большое дерево.
\MySkip
Чтобы гарантировать условие \t{[*]}, заранее сделаем offline проход по всем ребрам, выполним все операции добавления
в нужном порядке. В процессе добавления, некоторые ребра будут образовывать цикл. В этом случае
мы считаем ребро не интересным и ничего не делаем. А некоторые ребра, будут соединять разные компоненты
связности, такие ребра мы считаем интересными. Все интересные ребра образуют остовный лес $F$.
Подвесим все деревья леса $F$ за произвольные вершины.
Утверждается, что теперь у нас выполнено условие \t{[*]}.
Поскольку добавляемое ребро является ребром $F$, мы делаем отцом нижней вершины верхнюю вершину.
После всех операций добавления мы получим ровно лес $F$.
\MySubsection{Offline решение за $O(\log{k})$}{ssConn2logK}
В этой части работы, для удобства рассуждения, все ребра имеют длину.
Также все мосты имеют длину, поэтому запрос <<сколько в графе мостов>>
переформулируется на запрос <<суммарная длина всех мостов>>. Соответственно
у каждого запроса $q$ помимо полей $q.a$, $q.b$, $q.L$, $q.R$ появилось поле $q.len$ --- длина соответствующего ребра.
Исходно все ребра имеют длину $1$.
\MySkip
Сформулируем теорему аналогичную теореме [\LinkTheorem{cc}].
\MySkip
\Theorem{Сжатие компонент реберной двусвязности связности}{cc2}
Если в графе $G = \Pair{V}{E}$ всегда присутствует набор ребер $A$
(нет update-запросов, удаляющих ребра из $A$), то можно
построить новый граф $G_2$, вершинами которого будут компоненты реберной двусвязности графа $\Pair{V}{A}$, а множество
ребер = $\{\Pair{color[a]}{color[b]} : \Pair{a}{b} \in E \}$.
Здесь $color[a]$ --- номер компоненты реберной двусвязности, в которой лежит вершина $a$.
При переходе к новому графу запросы (и update-запросы, и get-запросы)
следует поменять следующим образом: $a \rightarrow color[a]$ для всех вершин $a$, участвующих в запросе.
\b{Утверждение теоремы:}
результаты новых запросов типа \t{get} на графе $G_2$ будут совпадать
с результатами старых запросов на графе $G$.
\MySkip
\b{Доказательство:}
Для доказательства я буду использовать следующий факт из теории графов,
который оставлю без доказательства. За доказательством можно обратиться к \cite{Asanov}.
\MySkip
\Tag{Утверждение}{(Вершины $a$ и $b$ лежат в одной компоненте реберной двусвязности) $\Leftrightarrow$
(существуют два простых, не пересекающихся по ребрам, пути между $a$ и $b$)}
Вернемся к доказательству теоремы.
1. Пусть в графе $G$ есть два простых реберно не пересекающихся пути между $a$ и $b$. Применим ко всем вершинам пути преобразование
$a \rightarrow color[a]$ и уберем возможно появившиеся петли и циклы. Мы получили простые реберно не пересекающиеся пути в $G_2$.
2. Пусть в графе $G_2$ есть два простых реберно не пересекающихся пути между $color[a]$ и $color[b]$. Дополним их до путей в графе $G$.
\MySkip
Теперь сформулируем теорему аналогичную теореме [\LinkTheorem{reduction}].
\MySkip
\Theorem{Редукция графа}{reduction2}
Если сейчас граф $G$ является лесом, все деревья этого леса подвешены,
а запросы затрагивают только множество вершин $B$, то можно все запросы рассматривать,
как запросы к меньшему графу $G_2 = \Pair{B \cap \{LCA(b_i, b_j)\} : b_i, b_j \in B}{E_2}$.
Здесь $E_2$ --- ребра задающие лес на вершинах графа $G_2$ и имеющие длину равную расстоянию
между соответствующими вершинами в графе $G$. \b{Утверждение теоремы:}
Количество вершин в графе $G_2$ = $O(k)$, где $k$ --- общее количество запросов.
Результаты get-запросов над $G$ и $G_2$ одинаковы.
\MySkip
\b{Доказательство:}
1. $|B| \le 5k$. Нужно сперва увидеть, что у нас есть $2k$ концов ребер-запросов, затем сказать, что
это листья некоторого леса. Вершины вида $LCA(b_i, b_j)$ --- это развилки в этом дереве и особые вершины, корни деревьев.
есть в каждом дереве есть еще одна особая вершина --- корень дерева.
В дереве с $2k$ листьями может быть не более $4k$ развилок, в каждом дереве не более одного корня. Каждый из $k$
запросов породил не более одного корня. Итого, суммарное количество вершин не превосходит~$5k$.
2. Рассмотрим два случая.
2.1. Граф $G$ больше не будет меняться. Тогда достаточно заметить, что расстояния между вершинами при перехода от $G$ к $G_2$ не поменялись.
2.2. В граф $G$ добавятся новые ребра. Тогда нужно заметить, что любой кратчайший путь, проходящий по ребрам (и старым, и только что добавленным)
графа $G$ пройдет по любому ребру графа $G_2$ от начала до конца.
\b{Доказательство закончено.}
\MySkip
Решением задачи, как и в случае односвязности, будет рекурсивная процедура, которая на каждом шаге
добавляет все ребра, которые точно нужно добавить,
делит отрезок времени пополам, сжимает компоненты реберной двусвязности в вершины (т.е. создает второй граф),
из второго графа создает третий с помощью преобразования, описанного в теореме [\LinkTheorem{reduction2}].
Эту рекурсивную процедуру изначально следует вызвать от множества всех запросов и отрезка $[0..k]$.
\Algorithm{logK2}
\begin{MyList}
\item \b{go}( G, $queries$, L, R ) \{
\item \hspace{2em} // $G = \Pair{V}{\varnothing}$, нам важно только множество вершин $V$
\item \hspace{2em} \b{if} L = R
\item \hspace{4em} Если $queries$ содержит get-запрос, обработать
\item \hspace{4em} \b{return}
\item \hspace{2em} A := $\emptyset$.
\item \hspace{2em} $queries_2$ := $\emptyset$
\item \hspace{2em} \b{for} q $\in$ $queries$
\item \hspace{4em} \b{if} ($q.type$ = \t{update}) \t{and} ($q.L < L$) \t{and} ($q.R \ge R$)
\item \hspace{6em} A.add(q)
\item \hspace{4em} \b{else} \b{if} ($q.type$ = \t{get}) \t{or} (($q.L < R$) \t{and} ($q.R \ge L$))
\item \hspace{6em} $queries_2$.add(q)
\item \hspace{2em} сожмем компоненты реберной двусвязности графа $\Pair{V}{A}$, получим новый граф $G_2$
\item \hspace{2em} $G_3$ = \t{Reduction}($G_2$)
\item \hspace{2em} M := $\lbrack\frac{L + R}{2}\rbrack$
\item \hspace{2em} \b{go}($G_3$, $queries_2$, L, M)
\item \hspace{2em} \b{go}($G_3$, $queries_2$, M+1, R)
\item \}
\item \b{main}() \{
\item \hspace{2em} инициализация СНМ
\item \hspace{2em} \b{go}($all\_queries$, 0, k)
\item \}
\end{MyList}
Оцени время работы алгоритма \LinkAlgorithm{logK2}.
\MySkip
\Theorem{Алгоритм \LinkAlgorithm{logK2} работает за время $O(k \log k)$.}{logK2@time}
\b{Доказательство:} для быстрого доказательства заметим, что алгоритм \LinkAlgorithm{logK2} отличается
от алгоритма \LinkAlgorithm{logK} только тем, что мы по-другому получаем граф $G_3$. Тем не менее,
по-прежнему $|queries| = O(R-L+1)$, а $|G_3.V| = O(K)$. Т.е. доказать нужно только то, что
граф $G_3$ мы построили из графа $G$ за линейное время.
1. $G_2$ построен за линейное время, т.к. компоненты реберной двусвязности можно найти за линейное время \cite{Asanov}, \cite{CORMEN}.
2. Преобразование \t{Reduction} также можно реализовать за линейное время, используя алгоритм Фараха-Колтона-Бендера подсчета LCA за
$O(1)$. Упомянутый алгоритм описан здесь \cite{fastLCA}.
\MySkip
Теорема доказана.
\MySection{Заключение}{sEnd}
Данная работа содержит описание и обоснование корректности двух новых алгоритмов.
Это простой алгоритм для решения задачи fully dynamic connectivity в режиме offline за время $O(k \log k)$ и
аналогичный алгоритм для решения задачи fully dynamic 2-edge-connectivity в режиме offline за время $O(k \log k)$.
Второй по асимптотике времени работы превосходит все предыдущие достижения в данной области.
Первый удобен и прост в реализации по сравнению с аналогичным по времени работы достижением Дэвида Эппштейна \cite{EPPSTEIN}.
\pagebreak
\begin{thebibliography}{99}
\MyBibitem{CORMEN}
{Кормен, Лейзерсон, Ривест, Штейн. Алгоритмы. Построение и анализ. Издание 2-е, М.: Вильямс, 2007.}
\MyBibitem{FRED}
{Frederickson, Greg N., Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications. CSTech-Report.No 83-449. May 1, 1984. Paper 368.}
\MyBibitem{EPPSTEIN}
{Eppstein, D., Offline Algorithms for Dynamic Minimum Spanning Tree Problems. Tech-Report.No 92-04. January 10, 1992. Dept. of Information and Computer Science,Univ. of California, Irvine, CA 92717}
\MyBibitem{MIKE1}
{M. Thorup, Near-optimal fully-dynamic graph connectivity, in Proc. 32nd ACM Symposium on Theory of Computing (STOC), 2000, pp. 343-350.}
\MyBibitem{MIKE2}
{Holm, J., Lichtenberg, K., Thorup, M., Poly-Logarithmic Deterministic Fully-Dynamic Algorithms
for Connectivity, Minimum Spanning Tree, 2-Edge,
and Biconnectivity, Journal of the ACM, Vol. 48, No. 4, July 2001, pp. 723–760.}
\MyBibitem{EPPSTEIN2}
{Eppstein, D., Galily, Z., Italiano, G.F., Improved Sparsification, Tech. Report 93-20, April 15, 1993, Dept. of Information and Computer Science Univ. of California, Irvine, CA 92717}
\MyBibitem{PATRASCU}
{Patrascu, M., Demaine E., Lower Bounds for Dynamic Connectivity, STOC’04, June 13–15, 2004, Chicago, Illinois, USA}
\MyBibitem{DSU}
{Alstrup, S., Ben-Amram, A.M., Rauhe, T., Worst-case and Amortised Optimality in Union-Find, 1999}
\MyBibitem{Tarjan}
{Tarjan, R.E., Efficiency of a good but not linear set union algorithm, Journal of the ACM, 22:215 225, 1975}
\MyBibitem{DeBerg}
{Mark de Berg, Mark van Kreveld. Computational Geometry Algorithms and Applications. Springer - Verlag Berlin Heidelberg New York, 1998}
\MyBibitem{KING1}
{Henzinger, M., King, V., Maintaining Minimum Spanning Fotests In Dynamic Graphs,2001 Society for Industrial and Applied Mathematics, SIAM J. COMPUT. Vol. 31, No. 2, pp. 364–374}
\MyBibitem{KING2}
{Henzinger, M., King, V., Fully Dynamic 2-Edge Connectivity Algorithm in Polylogarithmic Time per Operation, SRC Technical Note, 1997 - 004, June 27, 1997}
\MyBibitem{KING3}
{Henzinger, M., King, V., Randomized dynamic graph algorithm with polylogarithmic time per operation, 1995}
\MyBibitem{Asanov}
{Асанов М.О., Баранский В.А., Расин В.В., Дискретная Математика: Графы, Матроиды, Алгоритмы, Ижевск: НИЦ "РХД", 2001, 288 стр.}
\MyBibitem{fastLCA}
{M. A. Bender and M. Farach-Colton. "The LCA Problem Revisited." LATIN, pages 88-94, 2000}
\end{thebibliography}
\end{document}
Стипендия А.Н. Терехова
