Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Incrementally maintaining the number of l-cliques

Grandoni, Fabrizio

MPI-I-2002-1-002. July 2002, 10 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-2002-1-002.ps109 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  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},