On the complexity of the representation of simplicial complexes by trees - Archive ouverte HAL Access content directly
Journal Articles Theoretical Computer Science Year : 2016

On the complexity of the representation of simplicial complexes by trees

(1, 2) , (1, 3)
1
2
3

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.
Fichier principal
Vignette du fichier
BM15-no-format.pdf (1.12 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01259806 , version 1 (15-09-2016)

Identifiers

Cite

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

Relations

310 View
191 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More