Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Polynomially Solvable Cases of Hypergraph Transversal and Related Problems

Rauf, I. (2011). Polynomially Solvable Cases of Hypergraph Transversal and Related Problems. PhD Thesis, Universität des Saarlandes, Saarbrücken. doi:10.22028/D291-26196.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-AB0E-9 Versions-Permalink: https://hdl.handle.net/21.11116/0000-000C-7A47-C
Genre: Hochschulschrift

Externe Referenzen

einblenden:
ausblenden:
externe Referenz:
http://scidok.sulb.uni-saarland.de/volltexte/2011/4471/ (beliebiger Volltext)
Beschreibung:
-
OA-Status:
Grün
externe Referenz:
http://scidok.sulb.uni-saarland.de/doku/lic_ohne_pod.php?la=de (Verlagsvertrag)
Beschreibung:
-
OA-Status:
Keine Angabe

Urheber

einblenden:
ausblenden:
 Urheber:
Rauf, Imran1, 2, Autor           
Mehlhorn, Kurt1, Ratgeber           
Boros, Endre3, Gutachter
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2International Max Planck Research School, MPI for Informatics, Max Planck Society, Campus E1 4, 66123 Saarbrücken, DE, ou_1116551              
3External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: This thesis is mainly concerned with the hypergraph transversal problem, which
asks to generate all minimal transversals of a given hypergraph. While the
current best upper bound on the complexity of the problem is quasi-polynomial
in the combined input and output sizes, it is shown to be solvable in output
polynomial time for a number of hypergraph classes. We extend this polynomial
frontier to the hypergraphs induced by hyperplanes and constant-sided polytopes
in fixed dimension R^d and hypergraphs for which every minimal transversal and
hyperedge intersection is bounded. We also show the problem to be fixed
parameter tractable with respect to the minimum integer k such that the input
hypergraph is k-degenerate, and also with respect to its maximum complementary
degree. Whereas we improve the known bounds when the parameter is the maximum
degree of a hypergraph.

We also study the readability of a monotone Boolean function which is defined
as the minimum integer r such that it can be represented by an AND-OR-formula
with every variable occurrence is bounded by r. We prove that it is NP-hard to
approximate the readability of even a depth three Boolean formula. We also give
tight sublinear upper bounds on the readability of a monotone Boolean function
given in CNF (or DNF) form, parameterized by the number of terms in the CNF and
the maximum number of variables in the intersection of any constant number of
terms. For interval DNF's we give much tighter logarithmic bounds on the
readability.

Finally, we discuss an implementation of a quasi-polynomial algorithm for the
hypergraph transversal problem that runs in polynomial space. We found our
implementation to be competitive with all but one previous implementation on
various datasets.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2011-10-2520112011
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: Saarbrücken : Universität des Saarlandes
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: BibTex Citekey: Rauf2011
DOI: 10.22028/D291-26196
URN: urn:nbn:de:bsz:291-scidok-44713
Anderer: hdl:20.500.11880/26252
 Art des Abschluß: Doktorarbeit

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle

einblenden: