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

Zeitschrift:
Journal of Symbolic Computation

ISSN: 0747-7171

Datum der Publikation: 2013

Ausgabe: 50

Seiten: 170-196

Art: Artikel

beta Ver similares en nube de resultados
DOI: 10.1016/J.JSC.2012.07.003 SCOPUS: 2-s2.0-84870239031 WoS: WOS:000312574000009 GOOGLE SCHOLAR

Andere Publikationen in: Journal of Symbolic Computation

Institutionelles Repository: lock_openOpen Access Editor

Projekte im Zusammenhang

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

2009/00207/001

Zusammenfassung

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.