28623 articles – 22140 Notices  [english version]

hal-00567889, version 1

On the complexity of cycle enumeration using Zeons

René Schott () 1, 2, Stacey Staples () 3

(2010)

Résumé : 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\right)$ for fixed $0

  • 1 :  Institut Elie Cartan Nancy (IECN)
  • CNRS : UMR7502 – INRIA – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • 2 :  Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA)
  • INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • 3 :  Department of Mathematics and Statistics - Southern Illinois University
  • Southern Illinois University Edwardsville
  • Domaine : Mathématiques/Combinatoire
    Mathématiques/Algèbres d'opérateurs
  • Mots-clés : Cycles – Enumeration – Complexity – Zeons
  • Référence interne : Prépublication 2010/32
 
  • hal-00567889, version 1
  • http://hal.archives-ouvertes.fr/hal-00567889
  • oai:hal.archives-ouvertes.fr:hal-00567889
  • Contributeur : René Schott <>
  • Soumis le : Mardi 22 Février 2011, 11:36:22
  • Dernière modification le : Mardi 22 Février 2011, 12:54:43