hide
Free keywords:
-
Abstract:
The main contribution of this paper is an incremental algorithm to
update the number of $l$-cliques, for $l \geq 3$, in which each node of a graph is contained,
after the deletion of an arbitrary node. The initialization
cost is $O(n^{\omega p+q})$, where $n$ is the number of nodes,
$p=\lfloor \frac{l}{3} \rfloor$, $q=l \pmod{3}$, and $\omega=\omega(1,1,1)$
is the exponent of the multiplication of two $n x n$ matrices.
The amortized updating cost is $O(n^{q}T(n,p,\epsilon))$ for any
$\epsilon \in [0,1]$, where
$T(n,p,\epsilon)=\min\{n^{p-1}(n^{p(1+\epsilon)}+n^{p(\omega(1,\epsilon,1)-\epsilon)}),n^{p \omega(1,\frac{p-1}{p},1)}\}$
and $\omega(1,r,1)$ is the exponent of the multiplication of an
$n x n^{r}$ matrix by an $n^{r} x n$ matrix.
The current best bounds on
$\omega(1,r,1)$ imply an $O(n^{2.376p+q})$ initialization cost, an
$O(n^{2.575p+q-1})$ updating cost for $3 \leq l \leq 8$, and an
$O(n^{2.376p+q-0.532})$ updating cost for $l \geq 9$.
An interesting application to constraint programming is also considered.
