Compression with wildcards: Abstract simplicial complexes

DOI10.2989/16073606.2022.2071181arXiv1812.02570OpenAlexW3135857014MaRDI QIDQ6132729FDOQ6132729

Authors: Marcel Wild 

Publication date: 14 July 2023

Published in: Quaestiones Mathematicae (Search for Journal in Brave)

Abstract: Despite the more handy terminology of abstract simplicial complexes SC, in its core this article is about antitone Boolean functions. Given the maximal faces (=facets) of SC, our main algorithm, called Facets-To-Faces, outputs SC in a compressed format. The degree of compression of Facets-To-Faces, which is programmed in high-level Mathematica code, compares favorably to both the Mathematica command BooleanConvert, and to the BDD's provided by Python. A novel way to calculate the face-numbers from the facets is also presented. Both algorithms can be parallelized and are applicable (e.g.) to reliability analysis, combinatorial topology, and frequent set mining.

Full work available at URL: https://arxiv.org/abs/1812.02570

zbMATH Keywords

binary decision diagramreliability polynomialwildcardsabstract simplicial complexcompressed enumerationantitone Boolean functionexclusive sum of productsface-numberspartitionability conjecture

Mathematics Subject Classification ID

Data structures (68P05) Combinatorial aspects of simplicial complexes (05E45) Parallel algorithms in computer science (68W10) Computational aspects of satisfiability (68R07)

Cites Work

• The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes
• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
• The Complexity of Enumeration and Reliability Problems
• Compactly generating all satisfying truth assignments of a Horn formula
• Counting or producing all fixed cardinality transversals
• Computing the face lattice of a polytope from its vertex-facet incidences
• Matroids and a Reliability Analysis Problem
• Combinatorial face enumeration in convex polytopes
• The Partitionability Conjecture
• Conceptual exploration

Cited In (1)

• Complexity and algorithms for Euler characteristic of simplicial complexes

This page was built for publication: Compression with wildcards: Abstract simplicial complexes

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