About: 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.   Goto Sponge  NotDistinct  Permalink

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

AttributesValues
type
value
  • 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.
Subject
  • Closure operators
  • 1990s American drama television series
  • 1991 American television series endings
  • English-language television programs
  • Television series by Warner Bros. Television
  • 1990 American television series debuts
  • Arrowverse
  • CBS original programming
  • Flash (comics) television series
  • Television shows set in the United States
part of
is abstract of
is hasSource of
Faceted Search & Find service v1.13.91 as of Mar 24 2020


Alternative Linked Data Documents: Sponger | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data]
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