On the complexity of the representation of simplicial complexes by trees - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2014

On the complexity of the representation of simplicial complexes by trees

De la difficulté de représenter des complexes simpliciaux par des arbres

Dorian Mazauric

Résumé

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 ecient in terms of time complexity for searching a given simplex and we show that the local tree representation is more ecient 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 dicult to solve and to approximate even if the set of maximal simplices induces a cubic graph, a planar graph, or a bounded degree hypergraph. However, we prove polynomial time algorithms that compute constant factor approximations and optimal solutions for some classes of instances.
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.
Fichier principal
Vignette du fichier
RR-8647.pdf (1.42 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01089846 , version 1 (04-12-2014)
hal-01089846 , version 2 (04-09-2015)

Identifiants

  • HAL Id : hal-01089846 , version 2

Citer

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⟩
175 Consultations
241 Téléchargements

Partager

Gmail Facebook X LinkedIn More