On the complexity of the representation of simplicial complexes by trees

DOI10.1016/j.tcs.2015.12.034zbMath1335.68076OpenAlexW2224115673MaRDI QIDQ905846

Jean-Daniel Boissonnat, Dorian Mazauric

Publication date: 28 January 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.12.034

zbMATH Keywords

simplicial complexesNP-completenesshypergraphsapproximation algorithmstree representationsAPX-completeness

Mathematics Subject Classification ID

Searching and sorting (68P10) Hypergraphs (05C65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Combinatorial aspects of simplicial complexes (05E45)

Related Items

Building efficient and compact data structures for simplicial complexes

Cites Work

• The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes
• Efficient bounds for the stable set, vertex cover and set packing problems
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Building Efficient and Compact Data Structures for Simplicial Complexes