Complexity and algorithms for Euler characteristic of simplicial complexes

  1. Roune, B.H. 1
  2. Sáenz-de-Cabezón, E. 2
  1. 1 Cornell University
    info

    Cornell University

    Ithaca, Estados Unidos

    ROR https://ror.org/05bnh6r87

  2. 2 Universidad de La Rioja
    info

    Universidad de La Rioja

    Logroño, España

    ROR https://ror.org/0553yr311

Revista:
Journal of Symbolic Computation

ISSN: 0747-7171

Año de publicación: 2013

Volumen: 50

Páginas: 170-196

Tipo: Artículo

DOI: 10.1016/J.JSC.2012.07.003 SCOPUS: 2-s2.0-84870239031 WoS: WOS:000312574000009 GOOGLE SCHOLAR

Otras publicaciones en: Journal of Symbolic Computation

Repositorio institucional: lock_openAcceso abierto Editor

Proyectos relacionados

Gestión Mecanizada del Conocimiento Matemático. Aplicaciones en Topología Algebraica y en Lógica.

2009/00207/001

Resumen

We consider the problem of computing the Euler characteristic of an abstract simplicial complex given by its vertices and facets. We show that this problem is #P-complete and present two new practical algorithms for computing Euler characteristic. The two new algorithms are derived using combinatorial commutative algebra and we also give a second description of them that requires no algebra. We present experiments showing that the two new algorithms can be implemented to be faster than previous Euler characteristic implementations by a large margin. © 2012 Elsevier B.V.