Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  An Efficient Implementation of a Quasi-polynomial Algorithm for Generating Hypergraph Transversals

Boros, E., Elbassioni, K. M., Khachiyan, L., & Gurvich, V. (2003). An Efficient Implementation of a Quasi-polynomial Algorithm for Generating Hypergraph Transversals. In Algorithms - ESA 2003 (pp. 556-567). Berlin: Springer.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-EC57-2 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-EC59-D
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Boros, Endre1, Autor
Elbassioni, Khaled M.2, Autor           
Khachiyan, Leonid1, Autor
Gurvich, Vladimir1, Autor
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: Given a finite set V, and a hypergraph , the hypergraph transversal problem calls for enumerating all minimal hitting sets (transversals) for . This problem plays an important role in practical applications as many other problems were shown to be polynomially equivalent to it. Fredman and Khachiyan (1996) gave an incremental quasi-polynomial time algorithm for solving the hypergraph transversal problem [9]. In this paper, we present an efficient implementation of this algorithm. While we show that our implementation achieves the same bound on the running time as in [9], practical experience with this implementation shows that it can be substantially faster. We also show that a slight modification of the algorithm in [9] can be used to give a stronger bound on the running time.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2003
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: BibTex Citekey: Elbassioni2003e
DOI: 10.1007/978-3-540-39658-1_51
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: ESA 2003
Veranstaltungsort: Budapest, Hungary
Start-/Enddatum: 2003-09-16 - 2003-09-19

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Algorithms - ESA 2003
  Kurztitel : ESA 2003
  Untertitel : 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 556 - 567 Identifikator: -

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
  Kurztitel : LNCS
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 2832 Artikelnummer: - Start- / Endseite: - Identifikator: -