On the complexity of the representation of simplicial complexes by trees

DOI10.1016/J.TCS.2015.12.034MaRDI QIDQ905846zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmsAPX-completenesshypergraphsNP-completenesssimplicial complexestree representations

Mathematics Subject Classification ID

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

Recommendations

• Building efficient and compact data structures for simplicial complexes
• Building efficient and compact data structures for simplicial complexes
• Tree checking for sparse complexes

Cites work

• Building efficient and compact data structures for simplicial complexes
• Efficient bounds for the stable set, vertex cover and set packing problems
• The Rectilinear Steiner Tree Problem is NP-Complete

Cited in

(5)

• Optimal decision trees on simplicial complexes
• Complexity and algorithms for Euler characteristic of simplicial complexes
• Building efficient and compact data structures for simplicial complexes
• Simplicial cycles and the computation of simplicial trees
• Tree checking for sparse complexes

This page was built for publication: On the complexity of the representation of simplicial complexes by trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q905846)