Skip to Main content Skip to Navigation
Reports

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

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/hal-01089846
Contributor : Dorian Mazauric <>
Submitted on : Friday, September 4, 2015 - 4:36:18 PM
Last modification on : Saturday, January 27, 2018 - 1:31:34 AM
Long-term archiving on: : Saturday, December 5, 2015 - 12:36:02 PM

File

RR-8647.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

255

Files downloads

233