# MPI-I-2002-1-002

## 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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 109 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: **http://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},`

`}`