Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadatas

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/hal-01259806
Contributor : Dorian Mazauric <>
Submitted on : Thursday, September 15, 2016 - 10:19:33 AM
Last modification on : Friday, April 12, 2019 - 10:18:10 AM
Document(s) archivé(s) le : Friday, December 16, 2016 - 12:44:12 PM

File

BM15-no-format.pdf
Files produced by the author(s)

Identifiers

Relations

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⟩

Share

Metrics

Record views

526

Files downloads

227