MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Boros, Endre
Elbassioni, Khaled M.
Khachiyan, Leonid
Gurvich, Vladimir		dblp
dblp
dblp
dblp
Not MPG Author(s):
Boros, Endre
Khachiyan, Leonid
Gurvich, Vladimir
Editor(s):
Not MPII Editor(s):
Giuseppe Di Battista,
Uri Zwick
BibTeX cite key*:
Elbassioni2003e
Title, Booktitle
Title*:
An Efficient Implementation of a Quasi-polynomial Algorithm for Generating Hypergraph Transversals
ESA03.pdf (233.65 KB)
Booktitle*:
Algorithms - ESA 2003, 11th Annual European Symposium
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Budapest, Hungary
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
16 September 2003
Event End Date:
19 September 2003
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
2832
Number:
Month:
September
Pages:
556-567
Year*:
2003
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Elbassioni2003e,
AUTHOR = {Boros, Endre and Elbassioni, Khaled M. and Khachiyan, Leonid and Gurvich, Vladimir},
 TITLE = {An Efficient Implementation of a Quasi-polynomial Algorithm for Generating Hypergraph Transversals},
 BOOKTITLE = {Algorithms - ESA 2003, 11th Annual European Symposium},
 PUBLISHER = {Springer},
 YEAR = {2003},
 VOLUME = {2832},
 PAGES = {556--567},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Budapest, Hungary},
 MONTH = {September},
}

Entry last modified by Christine Kiesel, 07/15/2014
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]		Created
02/22/2005 08:06:09 PM
Revisions
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Christine Kiesel
Khaled Elbassioni
Khaled Elbassioni
Edit Dates
02.05.2007 15:40:11
02.06.2006 15:18:42
04/20/2006 06:40:54 PM
02/22/2005 08:06:10 PM

File Attachment Icon
ESA03.pdf