Compression with wildcards: Abstract simplicial complexes

<a class="pub-badge pub-badge--doi" href="https://doi.org/10.2989/16073606.2022.2071181" rel="nofollow">DOI 10.2989/16073606.2022.2071181</a><a class="pub-badge pub-badge--grey" href="https://openalex.org/works/W3135857014" rel="nofollow">OpenAlex</a><a class="pub-badge pub-badge--mardi" href="https://portal.mardi4nfdi.de/wiki/Item:Q6132729" rel="nofollow">MaRDI QID Q6132729</a><a class="pub-badge pub-badge--grey" href="https://fdo.portal.mardi4nfdi.de/fdo/Q6132729" rel="nofollow">FDO</a>

Authors Marcel Wild

Publication date 14 July 2023

Published in Quaestiones Mathematicae (Search for Journal in Brave)

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)

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.

Cites work

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

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)