On the complexity of the representation of simplicial complexes by trees

Jean-Daniel Boissonnat 1 Dorian Mazauric 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Résumé : Dans cet article, nous nous intéressons au problème de la représentation des complexes simpliciaux par des arbres. Nous introduisons et analysons une représentation locale et une représentation globale. Nous prouvons que la représentation globale est la plus efficace en termes de complexité en temps pour la recherche d'un simplexe et nous montrons que la représentation locale est la plus efficace en termes de taille de structure. Les complexes simpliciaux sont modélisés par des hypergraphes. Nous prouvons ensuite que les problèmes d'optimisation combinatoire associés sont très difficiles à résoudre voire à approximer même lorsque l'ensemble des simplexes maximaux induit un graphe cubique, un graphe planaire ou un hypergraphe de degré borné. Nous proposons cependant des algorithmes polynomiaux exactes et d'approximation pour certaines classes d'instances.
Type de document :
Rapport
[Research Report] RR-8647, Inria Sophia Antipolis; INRIA. 2014
Liste complète des métadonnées


https://hal.inria.fr/hal-01089846
Contributeur : Dorian Mazauric <>
Soumis le : vendredi 4 septembre 2015 - 16:36:18
Dernière modification le : jeudi 9 février 2017 - 15:48:12
Document(s) archivé(s) le : samedi 5 décembre 2015 - 12:36:02

Fichier

RR-8647.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01089846, version 2

Collections

Citation

Jean-Daniel Boissonnat, Dorian Mazauric. On the complexity of the representation of simplicial complexes by trees. [Research Report] RR-8647, Inria Sophia Antipolis; INRIA. 2014. <hal-01089846v2>

Partager

Métriques

Consultations de
la notice

142

Téléchargements du document

108