On the complexity of cycle enumeration using ZeonsReportar como inadecuado




On the complexity of cycle enumeration using Zeons - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 IECN - Institut Élie Cartan de Nancy 2 LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications 3 Department of Mathematics and Statistics - Southern Illinois University

Abstract : Nilpotent adjacency matrix methods are employed to enumerate $k$-cycles in simple graphs on $n$ vertices for any $k\le n$. The worst-case time complexity of counting $k$-cycles in an $n$-vertex simple graph is shown to be $\mathcal{O}n^{\alpha+1} 2^{n}$, where $\alpha\le 3$ is the exponent representing the complexity of matrix multiplication. When $k$ is fixed, the enumeration of all $k$-cycles in an $n$-vertex graph is of time complexity $\mathcal{O}n^{\alpha+k-1}$. Letting $\Omega=\binom{n}{2}$, the average-case time complexity of counting $k$-cycles in an $n$-vertex, $e$-edge graph where $e\le \displaystyle q\left\frac{\Omega}{k}-1 ight$ for fixed $0



Autor: René Schott - Stacey Staples -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados