About: Compression with wildcards: All exact, or all minimal hitting sets

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Compression with wildcards: All exact, or all minimal hitting sets Goto Sponge NotDistinct Permalink

An Entity of Type : schema:ScholarlyArticle, within Data Space : covidontheweb.inria.fr associated with source document(s)

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
title	Compression with wildcards: All exact, or all minimal hitting sets
Creator	Wild, Marcel
source	ArXiv
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.
has issue date	2020-08-20(xsd:dateTime)
has license	arxiv
sha1sum (hex)	f6995d195949a167744f80b9a820c3ebe621c2ba
resource representing a document's title	Compression with wildcards: All exact, or all minimal hitting sets
resource representing a document's body	covid:f6995d195949a167744f80b9a820c3ebe621c2ba#body_text
is schema:about of	named entity 'VERSION' named entity 'NUMERICAL' named entity 'MINIMAL' named entity 'PREVIOUS' named entity 'MINIMAL' »more»

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software