\n{$C_k$}{cycle on~$k$ vertices}
\n{${\cal D}(G)$}{optimal MSF decision tree for a~graph~$G$ \[decdef]}
\n{$D(G)$}{depth of ${\cal D}(G)$ \[decdef]}
-\n{$D(m,n)$}{decision tree complexity of MSF \[decdef]}
+\n{$D(m,n)$}{decision tree complexity of MSF for $m$~edges and $n$~vertices \[decdef]}
\n{$D_n$}{$n\times n$ matrix with 0's on the main diagonal and 1's elsewhere \[hatrank]}
\n{$\deg_G(v)$}{degree of vertex~$v$ in graph~$G$; we omit $G$ if it is clear from context}
\n{$E(G)$}{set of edges of a graph~$G$}
\n{$K_k$}{complete graph on~$k$ vertices}
\n{$L(\pi,A)$}{lexicographic ranking function for permutations on a~set~$A\subseteq{\bb N}$ \[brackets]}
\n{$L^{-1}(i,A)$}{lexicographic unranking function, the inverse of~$L$ \[brackets]}
-\n{$\log n$}{a binary logarithm of the number~$n$}
+\n{$\log n$}{binary logarithm of the number~$n$}
\n{$\log^* n$}{iterated logarithm: $\log^*n := \min\{i \mid \log^{(i)}n \le 1\}$; the inverse of~$2\tower n$}
\n{$\<LSB>(x)$}{position of the lowest bit set in~$x$ \[lsbmsb]}
\n{$\<MSB>(x)$}{position of the highest bit set in~$x$ \[lsbmsb]}
\n{$\mst(G)$}{the unique minimum spanning tree of a graph~$G$ \[mstnota]}
\n{$m(G)$}{number of edges of a graph~$G$, that is $\vert E(G)\vert$}
\n{$m$}{$m(G)$ when the graph~$G$ is clear from context}
-\n{$\bb N$}{set of all natural numbers, including 0}
+\n{$\bb N$}{set of all non-negative integers}
\n{${\bb N}^+$}{set of all positive integers}
\n{$N_0(M)$}{number of permutations satisfying the restrictions~$M$ \[restnota]}
\n{$n(G)$}{number of vertices of a graph~$G$, that is $\vert V(G)\vert$}
\n{$\alpha(n)$}{diagonal inverse of the Ackermann's function \[ackerinv]}
\n{$\alpha(m,n)$}{$\alpha(m,n) := \min\{ x\ge 1 \mid A(x,4\lceil m/n\rceil) > \log n \}$ \[ackerinv]}
\n{$\beta(m,n)$}{$\beta(m,n) := \min\{i \mid \log^{(i)}n \le m/n \}$ \[itjarthm]}
-\n{$\delta_G(U)$}{all edges connecting $U\subset V(G)$ with $V(G)\setminus U$; we usually omit the~$G$}
-\n{$\delta_G(v)$}{edges of a one-vertex cut, i.e., $\delta_G(\{v\})$}
+\n{$\delta_G(U)$}{the cut separating $U\subset V(G)$ from $V(G)\setminus U$ \[deltanota]}
+\n{$\delta_G(v)$}{edges of a one-vertex cut, i.e., $\delta_G(\{v\})$ \[deltanota]}
\n{$\Theta(g)$}{asymptotic~$\Theta$: $f=\Theta(g)$ iff $f=\O(g)$ and $f=\Omega(g)$}
\n{$\lambda_i(n)$}{inverse of the $i$-th row of the Ackermann's function \[ackerinv]}
\n{$\varrho({\cal C})$}{edge density of a graph class~$\cal C$ \[density]}
\n{$\Omega(g)$}{asymptotic~$\Omega$: $f=\Omega(g)$ iff $\exists c>0: f(n)\ge g(n)$ for all~$n\ge n_0$}
+%%\n{$x := y$}{$x$ is defined as~$y$}
\n{$T[u,v]$}{the path in a tree~$T$ joining vertices $u$ and $v$ \[heavy]}
\n{$T[e]$}{the path in a tree~$T$ joining the endpoints of an~edge~$e$ \[heavy]}
\n{$A\symdiff B$}{symetric difference of sets: $(A\setminus B) \cup (B\setminus A)$}
\n{$X \choose k$}{the set of all $k$-element subsets of a set~$X$}
\n{$G/e$}{multigraph contraction \[contract]}
\n{$G\sgc e$}{simple graph contraction \[simpcont]}
-\n{$G/X$, $G.X$}{contraction by a~set $X$ of vertices or edges \[setcont]}
+\n{$G/X$, $G\sgc X$}{contraction by a~set $X$ of vertices or edges \[setcont]}
\n{$f[X]$}{function applied to a set: $f[X]:=\{ f(x) \mid x\in X \}$}
\n{$f[e]$}{as edges are two-element sets, $f[e]$ maps both endpoints of an edge~$e$}
\n{$f^{(i)}$}{function~$f$ iterated $i$~times: $f^{(0)}(x):=x$, $f^{(i+1)}(x):=f(f^{(i)}(x))$}
\n{$\sigma^k$}{the string~$\sigma$ repeated $k$~times \[bitnota]}
\n{$\0$, $\1$}{bits in a~bit string \[bitnota]}
\n{$\equiv$}{congruence modulo a~given number}
-\n{$\bf x$}{a~vector with elements $x_1,\ldots,x_d$; $x$ is its bitwise encoding \[vecnota]}
+\n{$\bf x$}{vector with elements $x_1,\ldots,x_d$; $x$ is its bitwise encoding \[vecnota]}
\n{$x \shl n$}{bitwise shift of~$x$ by $n$~positions to the left: $x\shl n = x\cdot 2^n$}
\n{$x \shr n$}{bitwise shift of~$x$ by $n$~positions to the right: $x\shr n = \lfloor x/2^n \rfloor$}
\n{$[n]$}{the set $\{1,2,\ldots,n\}$ \[pranksect]}
-\n{$n^{\underline k}$}{the $k$-th falling factorial power: $n\cdot(n-1)\cdot\ldots\cdot(n-k+1)$ \[kpranksect]}
+\n{$n^{\underline k}$}{$k$-th falling factorial power: $n\cdot(n-1)\cdot\ldots\cdot(n-k+1)$ \[kpranksect]}
\n{$H\minorof G$}{$H$ is a~minor of~$G$ \[minordef]}
\n{$G\crpt R$}{graph~$G$ with edges in~$R$ corrupted \[corrnota]}
\n{$R^C$}{$R^C = R\cap \delta(C)$ \[corrnota]}
(if the edge is a loop).
\proclaim{Notation}%
-When the meaning is clear from the context, we use our notation originally
-defined for graphs even for multigraphs. For example, $xy\in E(G)$ becomes a
+When the meaning is clear from the context, we use the standard graph notation
+even for multigraphs. For example, $xy\in E(G)$ becomes a
shorthand for $\exists e\in E(G)$ such that $M(G)(e) = \{x,y\}$. Also, we
consider multigraphs with no multiple edges nor loops and simple graphs to be
the same objects, although they formally differ.
$$\eqalign{
V' &= (V(G) \setminus \{x,y\}) \cup \{v_e\},\quad\hbox{where $v_e$ is a new vertex,}\cr
E' &= E(G) - \{e\},\cr
-M'(f) &= \{ m(v) \mid v\in M(f) \} \quad\hbox{for every $f=\in E'$, and}\cr
-m(x) &= \cases{v_e & \hbox{for $v=x,y,$}\cr v & \hbox{otherwise.}} \cr
+M'(f) &= \{ m(v) \mid v\in M(f) \} \quad\hbox{for every $f\in E'$, and}\cr
+m(x) &= \cases{v_e & \hbox{for $v=x,y,$}\cr \noalign{\vskip5pt} v & \hbox{otherwise.}} \cr
}$$
-Sometimes we need contraction for simple graphs as well. It is equivalent to performing
+We sometimes also need to contract edges in simple graphs. It is equivalent to performing
the multigraph contraction and then unifying parallel edges and deleting loops.
\defn\id{simpcont}%
\defn\id{setcont}%
We can also extend the above definitions to contractions of a~set of vertices or edges.
For $F\subseteq E(G)$, the graph $G/F$ is defined as $(G/f_1)/f_2/\ldots/f_k$ where
-$f_1,\ldots,f_k$ are the elements of~$F$ (you can observe that the result
-does not depend on the order of edges). For $U\subseteq V(G)$, we define $G/U$
+$f_1,\ldots,f_k$ are the elements of~$F$ (the result obviously does not depend on the order of edges).
+For $U\subseteq V(G)$, we define $G/U$
as the graph with all vertices of~$U$ merged to a~single vertex, that is $(G\cup U^*)/U^*$,
where $U^*$ is the complete graph on~$U$. Similarly for $G\sgc F$ and $G\sgc U$.
computability theory. Its original purpose was to demonstrate that not every recursive
function is also primitive recursive. At the first sight, it does not
seem related to efficient algorithms at all. Its various inverses however occur in
-analyses of various algorithms and mathematical structures surprisingly often:
+analyses of algorithms and mathematical structures surprisingly often:
We meet them in Section \ref{classalg} in the time complexity of the Disjoint Set Union
data structure and also in the best known upper bound on the decision tree
complexity of minimum spanning trees in Section \ref{optalgsect}. Another
related to the topic of our study.
Various sources differ in the exact definition of both the Ackermann's
-function and its inverse, but most of the differences are in factors that
+function and its inverse, but most of these differences are in factors that
are negligible in the light of the giant asymptotic growth of the function.\foot{%
To quote Pettie \cite{pettie:onlineverify}: ``In the field of algorithms \& complexity,
Ackermann's function is rarely defined the same way twice. We would not presume to buck
such a~well-established precedent. Here is a~slight variant.''}
We will use the definition by double recursion given by Tarjan \cite{tarjan:setunion},
-which is predominant in the literature on graph algorithms:
+which is predominant in the literature on graph algorithms.
\defn\id{ackerdef}%
The \df{Ackermann's function} $A(x,y)$ is a~function on non-negative integers defined as follows:
&= A(2,A(2,4)) = 2\tower(2\tower 4) = 2\tower 65536. \cr
}$$
-\para
-Three functions related to the inverse of the function~$A$ are usually considered:
+\paran{Inverses}%
+As common for functions of multiple parameters, there is no single function which
+could claim the title of the only true Inverse Ackermann's function.
+The following three functions related to the inverse of the function~$A$ are often considered:
\defn\id{ackerinv}%
The \df{$i$-th row inverse} $\lambda_i(n)$ of the Ackermann's function is defined by:
projects / saga.git / blobdiff