MPI-I-2002-1-002
Incrementally maintaining the number of l-cliques
Grandoni, Fabrizio
July 2002, 10 pages.
.
Status: available - back from printing
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.
-
- Attachement: MPI-I-2002-1-002.ps (109 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2002-1-002
BibTeX
@TECHREPORT{Grandoni2002,
AUTHOR = {Grandoni, Fabrizio},
TITLE = {Incrementally maintaining the number of l-cliques},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-2002-1-002},
MONTH = {July},
YEAR = {2002},
ISSN = {0946-011X},
}