Compactly generating all satisfying truth assignments of a Horn formula
M Wild - Journal on satisfiability, Boolean modeling and …, 2012 - content.iospress.com
While it was known that all models of a Horn formula can be generated in output-polynomial
time, here we present an explicit algorithm as opposed to the rather vague oracle-scheme …
time, here we present an explicit algorithm as opposed to the rather vague oracle-scheme …
Enumerating all minimal hitting sets in polynomial total time
M Wild - arXiv preprint arXiv:2303.07708, 2023 - arxiv.org
arXiv:2303.07708v1 [math.CO] 14 Mar 2023 Page 1 Enumerating all minimal hitting sets in
polynomial total time March 15, 2023 Marcel Wild ABSTRACT: We show that the R minimal …
polynomial total time March 15, 2023 Marcel Wild ABSTRACT: We show that the R minimal …
[PDF][PDF] Coupon collecting and transversals of hypergraphs
Coupon collecting and transversals of hypergraphs Page 1 Discrete Mathematics and
Theoretical Computer Science DMTCS vol. 15:2, 2013, 259–270 Coupon collecting and …
Theoretical Computer Science DMTCS vol. 15:2, 2013, 259–270 Coupon collecting and …
Compression with wildcards: All exact or all minimal hitting sets
M Wild - Open Mathematics, 2023 - degruyter.com
Our 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 towards …
of general hypergraphs. To the author's best knowledge, the only previous attempt towards …
Comparison of old and new algorithms for s, t-network reliability
SCF Zainabu - 2020 - scholar.sun.ac.za
Network reliability is the probability of an operative path connecting the source s with the
terminal t. s, t-network reliability problems have been proven to be# P-complete. In this …
terminal t. s, t-network reliability problems have been proven to be# P-complete. In this …
Compression with wildcards: From CNFs to orthogonal DNFs by imposing the clauses one-by-one
M Wild - The Computer Journal, 2022 - academic.oup.com
We present a novel technique for converting a Boolean conjunctive normal form (CNF) into
an orthogonal disjunctive normal form (DNF), aka exclusive sum of products. Our method …
an orthogonal disjunctive normal form (DNF), aka exclusive sum of products. Our method …
How to partition or count an abstract simplicial complex, given its facets
M Wild - arXiv preprint arXiv:1302.1039, 2013 - arxiv.org
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 …
SC into few pieces, each one compactly encoded by the use of wildcards. Such a …
[PDF][PDF] ALLSAT compressed with wildcards. Part 3: Partitionings and face-numbers of simplicial complexes
M Wild - 2017 - researchgate.net
More details about the mini-series whose “Part 3” is the present article can be found in [W4,
Section 8.4]. We won't further dwell on it here. A simplicial complex (also called set ideal) …
Section 8.4]. We won't further dwell on it here. A simplicial complex (also called set ideal) …
Coupons collecting with or without replacement, and with multipurpose coupons
arXiv:1107.1401v3 [math.PR] 24 Nov 2012 Page 1 COUPON COLLECTING AND
TRANSVERSALS OF HYPERGRAPHS MARCEL WILD, SVANTE JANSON, STEPHAN WAGNER …
TRANSVERSALS OF HYPERGRAPHS MARCEL WILD, SVANTE JANSON, STEPHAN WAGNER …
Compression with wildcards: All spanning trees with prescribed vertex-degrees
M Wild - arXiv preprint arXiv:2002.09707, 2020 - arxiv.org
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 …
trees of G can be compactly encoded. Surprisingly, a 1986 algorithm of Winter seems to …