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

Aldizkaria:
Journal of Symbolic Computation

ISSN: 0747-7171

Argitalpen urtea: 2013

Alea: 50

Orrialdeak: 170-196

Mota: Artikulua

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

Beste argitalpen batzuk: Journal of Symbolic Computation

Gordailu instituzionala: lock_openSarbide irekia Editor

Lotura duten proiektuak

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

2009/00207/001

Laburpena

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.