English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  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

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-EC57-2 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-EC59-D
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Boros, Endre1, Author
Elbassioni, Khaled M.2, Author           
Khachiyan, Leonid1, Author
Gurvich, Vladimir1, Author
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: 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

show
hide
Language(s): eng - English
 Dates: 2003
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: Elbassioni2003e
DOI: 10.1007/978-3-540-39658-1_51
 Degree: -

Event

show
hide
Title: ESA 2003
Place of Event: Budapest, Hungary
Start-/End Date: 2003-09-16 - 2003-09-19

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithms - ESA 2003
  Abbreviation : ESA 2003
  Subtitle : 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 556 - 567 Identifier: -

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 2832 Sequence Number: - Start / End Page: - Identifier: -