From c7507dbc7e6e4a6b4fd28b743497b7cb367daeaf Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 28 Jul 2008 23:58:46 +0200 Subject: [PATCH] Slides v0.0. --- slides/Makefile | 7 + slides/slides.tex | 319 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 326 insertions(+) create mode 100644 slides/Makefile create mode 100644 slides/slides.tex diff --git a/slides/Makefile b/slides/Makefile new file mode 100644 index 0000000..67ad505 --- /dev/null +++ b/slides/Makefile @@ -0,0 +1,7 @@ +all: slides.pdf + +slides.pdf: slides.tex + pdflatex slides.tex + +clean: + rm -f *~ *.{aux,log,nav,out,pdf,snm,toc} diff --git a/slides/slides.tex b/slides/slides.tex new file mode 100644 index 0000000..9819207 --- /dev/null +++ b/slides/slides.tex @@ -0,0 +1,319 @@ +\documentclass{beamer} +\usepackage[latin2]{inputenc} +\usepackage{palatino} +\usetheme{Warsaw} +\title[Graph Algorithms]{Graph Algorithms\\Spanning Trees and Ranking} +\author[Martin Mare¹]{Martin Mare¹\\\texttt{mares@kam.mff.cuni.cz}} +\institute{Department of Applied Mathematics\\MFF UK Praha} +\date{2008} +\begin{document} +\setbeamertemplate{navigation symbols}{} +\setbeamerfont{title page}{family=\rmfamily} + +\def\[#1]{~{\color{violet} [#1]}} +\def\O{{\cal O}} + +\begin{frame} +\titlepage +\end{frame} + +\begin{frame}{The Minimum Spanning Tree Problem} + +{\bf 1. Minimum Spanning Tree Problem:} + +\begin{itemize} +\item Given a~weighted undirected graph,\\ + what is its lightest spanning tree? +\item In fact, a~linear order on edges is sufficient. +\item Efficient solutions are very old \[Borùvka 1926] +\item A~long progression of faster and faster algorithms. +\item Currently very close to linear time, but still not there. +\end{itemize} + +\end{frame} + +\begin{frame}{The Ranking Problems} + +{\bf 2. Ranking of Combinatorial Structures:} + +\begin{itemize} +\item We are given a~set~$C$ of objects with a~linear order $\prec$. +\item {\bf Ranking function $R_\prec(x)$:} how many objects precede~$x$? +\item {\bf Unranking function $R^{-1}_\prec(i)$:} what is the $i$-th object? +\end{itemize} + +\pause + +\begin{example}[toy] +$C=\{0,1\}^n$ with lexicographic order + +\pause +$R$ = conversion from binary\\ +$R^{-1}$ = conversion to binary +\end{example} + +\pause +\begin{example}[a~real one] +$C=$ set of all permutations on $\{1,\ldots,n\}$ +\end{example} + +\pause +How to compute the (un)ranking function efficiently? + +For permutations, an $\O(n\log n)$ algorithm was known \[folklore]. + +We will show how to do that in $\O(n)$. + +\end{frame} + +\begin{frame}{Models of computation: RAM} + +As we approach linear time, we must specify the model. + +~ + +{\bf 1. The Random Access Machine (RAM):} + +\begin{itemize} +\item Works with integers +\item Memory: an array of integers indexed by integers +\end{itemize} + +~ + +Many variants exist, we will use the {\bf Word-RAM:} + +\begin{itemize} +\item Machine words of $W$ bits +\item The ``C operations'': arithmetics, bitwise logical op's +\item Unit cost +\item We know that $W\ge\log_2 \vert \hbox{input} \vert$ +\end{itemize} + +\end{frame} + +\begin{frame}{Models of computation: PM} + +{\bf 2. The Pointer Machine (PM):} + +\begin{itemize} +\item Memory cells accessed via pointers +\item Each cell contains $\O(1)$ pointers and $\O(1)$ symbols +\item Operates only on pointers and symbols +\end{itemize} + +~ + +\begin{beamerboxesrounded}[upper=block title example,shadow=true]{Key differences} +\begin{itemize} +\item PM has no arrays, we can emulate them in $\O(\log n)$ +\item PM has no arithmetics +\end{itemize} +\end{beamerboxesrounded} + +~ + +We can emulate PM on RAM with constant slowdown. + +Emulation of RAM on PM is more expensive. + +\end{frame} + +\begin{frame}{PM Techniques} + +{\bf Bucket Sorting} does not need arrays. + +~ + +Interesting consequences: + +\begin{itemize} +\item Flattening of multigraphs in $\O(m+n)$ +\item Unification of sequences in $\O(n+\sum_i\ell_i+\vert\Sigma\vert)$ +\item (Sub)tree isomorphism in $\O(n)$ simplified \[M. 2008] +\item Batched graph computations \[Buchsbaum et al.~1998] +\end{itemize} + +\end{frame} + +\begin{frame}{RAM Techniques} + +We can use RAM as a vector machine: + +~ + +\begin{example} +\def\sep{\;{\color{brown}0}} +\def\seq{\;{\color{brown}1}} +\def\sez{\;{\color{red}0}} +We can encode the vector $(1,5,3,0)$ with 3-bit fields as: +\begin{center} +\sep001\sep101\sep011\sep000 +\end{center} +And then search for 3 by: + +\begin{center} +\begin{tabular}{rc} + &\seq001\seq101\seq011\seq000 \\ +{\sc xor} &\sep011\sep011\sep011\sep011 \\ +\hline + &\seq010\seq110\seq000\seq011 \\ +$-$ &\sep001\sep001\sep001\sep001 \\ +\hline + &\seq001\seq101\sez111\seq010 \\ +{\sc and} &\seq000\seq000\seq000\seq000 \\ +\hline + &\seq000\seq000\sez000\seq000 \\ +\end{tabular} +\end{center} +\end{example} + +\end{frame} + +\begin{frame}{RAM Data Structures} + +We can translate vector operations to $\O(1)$ RAM instructions + +\smallskip + +\dots\ as long as the vector fits in $\O(1)$ words. + +~ + +We can build ``small'' data structures operating in $\O(1)$ time: + +\begin{itemize} +\item Sets +\item Ordered sets with ranking +\item ``Small'' heaps of ``large'' integers \[Fredman \& Willard 1990] +\end{itemize} + +\end{frame} + +\begin{frame}{Minimum Spanning Trees} +Algorithms for Minimum Spanning Trees: + +\begin{itemize} +\item Classical algorithms \[Borùvka, Jarník-Prim, Kruskal] +\item Contractive: $\O(m\log n)$ using flattening on the PM \\ + (lower bound: \[M.]) +\item Iterated: $\O(m\,\beta(m,n))$ \[Fredman \& Tarjan~1987] \\ + where $\beta(m,n) = \min\{ k: \log_2^{(k)} n \le m/n \}$ +\item Even better: $\O(m\,\alpha(m,n))$ using {\it soft heaps}\\ + \[Chazelle 1998, Pettie 1999] +\item MST verification: $\O(m)$ on RAM \[King 1997, M. 2008] +\item Randomized: $\O(m)$ w.h.p. \[Karger et al.~1995] +\end{itemize} +\end{frame} + +\begin{frame}{MST -- Special cases} + +We have $\O(m)$ time algorithms for: + +\begin{itemize} +\item Planar graphs \[Tarjan 1976, Matsui 1995, M. 2004] (PM) +\item Minor-closed classes \[Tarjan 1983, M. 2004] (PM) +\item $\O(1)$ different weights \[folklore] (PM) +\item Integer weights \[Fredman \& Willard 1990] (RAM) +\end{itemize} + +\end{frame} + +\begin{frame}{MST -- Optimality} + +There is a~provably optimal comparison-based algorithm \\\[Pettie \& Ramachandran 2002] + +~ + +However, there is a catch: \pause Nobody knows its complexity. + +~ + +We know that it is $\O({\cal T}(m,n))$ where ${\cal T}(m,n)$ is the depth +of the optimum MST decision tree. + +\pause +~ + +\begin{corollary} +It runs on the PM, so we know that if there is a~linear-time algorithm, +it does not need any special RAM data structures. (They can however +help us to find it.) +\end{corollary} + +\end{frame} + +\begin{frame}{MST -- Dynamic algorithms} + +Sometimes, we need to find the MST of a~changing graph. \\ +We insert/delete edges, the structure responds with $\O(1)$ +modifications of the MST. + +\begin{itemize} +\item Unweighted cases similar to dynamic connectivity: + \begin{itemize} + \item Incremental: $\O(\alpha(n))$ \[Tarjan 1975] + \item Fully dynamic: $\O(\log^2 n)$ \[Holm et al.~2001] + \end{itemize} +\item Weighted cases are harder: + \begin{itemize} + \item Decremental: $\O(\log^2 n)$ \[Holm et al.~2001] + \item Fully dynamic: $\O(\log^4 n)$ \[Holm et al.~2001] + \item Only~$W$ weights: $\O(W\log^2 n)$ \[M. 2008] + \end{itemize} +\item $K$ best spanning trees: + \begin{itemize} + \item Simple: $\O(T_{MST} + Km)$ \[Katoh et al.~1981, M.~2008] + \item Reduced: $\O(T_{MST} + \min(K^2, Km + K\log K))$ \[Eppst.~1992] + \item Large~$K$: $\O(T_{MST} + \min(K^{3/2}, Km^{1/2}))$ \[Frederickson 1997] + \end{itemize} +\end{itemize} + +\end{frame} + +\begin{frame}{Back to Ranking} + +Ranking of permutations on the RAM: \[M. \& Straka 2007] + +\begin{itemize} +\item Traditional algorithms represent a~subset of $\{1,\ldots,n\}$ +\item The result can be $n!$ $\Rightarrow$ word size $=\Omega(n\log n)$ bits +\item We can represent the subsets as RAM vectors +\item This gives us an~$\O(n)$ time algorithm for (un)ranking +\end{itemize} + +~ + +Easily extendable to $k$-permutations, also in $\O(n)$ + +\end{frame} + +\begin{frame}{Restricted permutations} + +For restricted permutations (e.g., derangements): \[M. 2008] + +\begin{itemize} +\item Existence of permutation reduces to network flows +\item The ranking problem can be used to calculate permanents,\\ + so it is $\#\rm P$-complete +\item However, this is the only obstacle. Calculating $\O(n)$ + sub-permanents is sufficient. +\item For derangements, we have achieved $\O(n)$ time after $\O(n^2)$ time + preprocessing. +\end{itemize} + +\end{frame} + +\begin{frame}{My contributions} + +\begin{itemize} +\item The lower bound for the Contractive Borùvka's algorithm +\item A~simpler linear-time tree isomorphism algorithm. +\item A~linear-time algorithm for MST on minor-closed classes. +\item Corrected and simplified MST verification. +\item Ranking and unranking algorithms. +\end{itemize} + +\end{frame} + +\end{document} -- 2.39.2