On the complexity of the representation of simplicial complexes by trees - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2014

On the complexity of the representation of simplicial complexes by trees

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

(1) , (1)
1
Dorian Mazauric

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 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
Origin : Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

  • HAL Id : hal-01089846 , version 2

Cite

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⟩
168 View
214 Download

Share

Gmail Facebook Twitter LinkedIn More