40 citations · 64 across the 27 of their papers we have counts for
29 papers
Enumerating all minimal hitting sets in polynomial total time
Marcel Wild
Consider a hypergraph (=set system) whose hyperedges are subsets of a set with w elements. We show that the minimal hitting sets of can be enumera…
Modular lattices of finite length (Part A)
Marcel Wild
This is Part A of four Parts dedicated to modular lattices of finite length. It builds on 1992 notes of the author (available on ResearchGate), and in so doing heeds a wish of the…
Compression with wildcards: All exact, or all minimal hitting sets
Marcel Wild
Our main objective is the COMPRESSED enumeration (based on wildcards) of all minimal hitting sets of general hypergraphs. To the author's best knowledge the only previous attempt t…
Compression with wildcards: All spanning trees with prescribed vertex-degrees
Marcel Wild
By processing all minimal cutsets of a graph G, and by using novel wildcards, all spanning trees of G can be compactly encoded. Surprisingly, a 1986 algorithm of Winter seems to ac…
ALLSAT compressed with wildcards: Frequent Set Mining
Marcel Wild
Like any simplicial complex the simplicial complex of all frequent sets can be compressed with wildcards once the maximal frequent sets (=facets) are known. Namely, the task (a par…
Compression with wildcards: Abstract simplicial complexes
Marcel Wild
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 m…
Finding or counting all shellings of a simplicial complex
Marcel Wild
The shellability status of previously investigated simplicial complexes with up to 24 facets is settled. In case of shellability the exact number of shellings is determined. Our al…
ALLSAT compressed with wildcards: An invitation for C-programmers
Marcel Wild
The model set of a general Boolean function in CNF is calculated in a compressed format, using novel wildcards. This method can be explained in very visual ways. Preliminary compar…
An efficient data structure for counting all linear extensions of a poset, calculating its jump number, and the likes
Marcel Wild
Achieving the goals in the title (and others) relies on a cardinality-wise scanning of the ideals of the poset. Specifically, the relevant numbers attached to the k+1 element ideal…
Tight embedding of modular lattices into partition lattices: progress and program
Marcel Wild
Representing lattices L by equivalence relations amounts to embed them into the lattice Part(V) of all partitions of a set V, and has a long history. Here we are concerned with MOD…
Compression with wildcards: All k-models of a binary decision diagram
Marcel Wild, Yves Semegni
Given a Binary Decision Diagram of a Boolean function in variables, it is well known that all -models can be enumerated in output polynomial time, and in a compresse…
ALLSAT compressed with wildcards: From CNF's to orthogonal DNF's by imposing the clauses one by one
Marcel Wild
We present a novel technique for converting a Boolean CNF into an orthogonal DNF, aka exclusive sum of products. Our method (which will be pitted against a hardwired command from M…
The joy of implications, aka pure Horn functions: mainly a survey
Marcel Wild
Apart from a brief look at applications (Relational Databases, Formal Concept Analysis, data mining) this article is devoted to the mathematical t h e o r y of implications (=pure…
Compressed representation of Learning Spaces
Marcel Wild
Learning Spaces are certain set systems that are applied in the mathematical modeling of education. We propose a suitable compression (without loss of information) of such set syst…
Inclusion-exclusion enhanced by nerve stimulation
Marcel Wild
When evaluating the lengthy inclusion-exclusion expansion many of its terms may turn out to be zero, and hence should be discarded beforehand. Often this can be done. The main idea…
How to partition or count an abstract simplicial complex, given its facets
Marcel Wild
Given are the facets of an abstract (finite) simplicial complex SC. We show how to partition SC into few pieces, each one compactly encoded by the use of wildcards. Such a represen…
Compression with wildcards: All models of a Boolean 2-CNF
Marcel Wild
Let be a finite set which simultaneously serves as the universe of any poset and as the vertex set of any graph . Our algorithm, abbreviated A-I-I, enumerates…
Output polynomial enumeration of all fixed-cardinality ideals of a poset, respectively all fixed-cardinality subtrees of a tree
Marcel Wild
The N cardinality k ideals of any w-element poset (w, k variable) can be enumerated in time O(Nw^3). The corresponding bound for k-element subtrees of a w-element tree is O(Nw^5).…
A catalogue of small regular matroids and their Tutte polynomials
Harald Fripertinger, Marcel Wild
A catalogue of all non-isomorphic simple connected regular matroids of cardinality is provided on the net. These matroids are given as binary matrix matroids…
Coupons collecting with or without replacement, and with multipurpose coupons
Marcel Wild, Svante Janson, Stephan Wagner +1
The classic Coupon-Collector Problem (CCP) is generalized to the extent that each coupons serves certain "purposes". Only basic probability theory is used. Centerpiece rather is an…
Counting or producing all fixed cardinality transversals
Marcel Wild
An algorith to count, or alternatively generate, all k-element transversals of a set system is presented and compared with three known methods. For special cases it works in output…
Compactly generating all satisfying truth assignments of a Horn formula
Marcel Wild
As instance of an overarching principle of exclusion an algorithm is presented that compactly (thus not one by one) generates all models of a Horn formula. The principle of exclusi…
Lattices freely generated by posets within a variety. Part II: Finitely generated varieties
Jean Yves Semegni, Marcel Wild
This article is the second part of an essay dedicated to lattices freely generated by posets within a variety. The first part dealt with four easy varieties while this part is conc…
Lattices freely generated by posets within a variety. Part I: Four easy varieties
Jean Yves Semegni, Marcel Wild
We introduce an algorithm for computing closure systems derived from a family of implications on a set. Semilattices presentations are explored and used in conjunction with the alg…