|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Compression with wildcards: All exact, or all minimal hitting sets | | Marcel Wild
; | | Date: |
20 Aug 2020 | | Abstract: | 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 towards compression, due to Toda [T], is based on BDD’s
and much different from our techniques. Preliminary numerical experiments show
that traditional one-by-one enumeration schemes cannot compete against
compressed enumeration when the degree of compression is high. Despite the fact
that thorough numerical experiments are postponed to a later version of our
article, several tools to enhance compression (inclusion-exclusion, a matroid
theorem of Rado, or adding dual kinds of wildcards) are put in place and their
pros and cons are evaluated.
Nevertheless, classic one-by-one enumeration is not neglected. Corollary 2
states that under mild provisos all perfect matchings of a graph can be
enumerated in polynomial total time. Likewise all minimal edge-covers of a
graph (Corollary 6). Furthermore, enumerating all minimal hypergraph
transversals is fixed-parameter tractable for novel types of parameters
(Corollary 5 and 4.6.3). Exact hitting sets constitute only a ’side show’ but
we start with them by pedagogical reasons: Our wildcard method is more
clear-cut for exact hitting sets than for minimal hitting sets. | | Source: | arXiv, 2008.08996 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER