On the complexity of the representation of simplicial complexes by trees

Jean-Daniel Boissonnat 1, 2 Dorian Mazauric 1, 3
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
2 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
3 ABS - Algorithms, Biology, Structure
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : In this paper, we investigate the problem of the representation of simplicial complexes by trees. We introduce and analyze local and global tree representations. We prove that the global tree representation is more efficient in terms of time complexity for searching a given simplex and we show that the local tree representation is more efficient in terms of size of the structure. The simplicial complexes are modeled by hypergraphs. We then prove that the associated combinatorial optimization problems are very difficult to solve and to approximate even if the set of maximal simplices induces a planar graph of maximum degree at most three or a bounded degree hypergraph. However, we prove polynomial time algorithms that compute constant factor approximations and optimal solutions for some classes of instances.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2016, 617, pp.17. 〈10.1016/j.tcs.2015.12.034〉
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01259806
Contributeur : Dorian Mazauric <>
Soumis le : jeudi 15 septembre 2016 - 10:19:33
Dernière modification le : samedi 18 février 2017 - 01:14:44
Document(s) archivé(s) le : vendredi 16 décembre 2016 - 12:44:12

Fichier

BM15-no-format.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Relations

  • est un autre format de hal-01089846 - Rapport de recherche

Citation

Jean-Daniel Boissonnat, Dorian Mazauric. On the complexity of the representation of simplicial complexes by trees. Theoretical Computer Science, Elsevier, 2016, 617, pp.17. 〈10.1016/j.tcs.2015.12.034〉. 〈hal-01259806〉

Partager

Métriques

Consultations de
la notice

242

Téléchargements du document

74