Output-sensitive algorithms for enumerating minimal transversals for some geometric hypergraphs

Khaled Elbassioni, Kazuhisa Makino, Imran Rauf

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

6 Scopus citations

Abstract

We give a general framework for the problem of finding all minimal hitting sets of a family of objects in by another. We apply this framework to the following problems: (i) hitting hyper-rectangles by points in ; (ii) stabbing connected objects by axis-parallel hyperplanes in ; and (iii) hitting half-planes by points. For both the covering and hitting set versions, we obtain incremental polynomial-time algorithms, provided that the dimension d is fixed.

Original languageBritish English
Title of host publicationAlgorithms - ESA 2009 - 17th Annual European Symposium, Proceedings
Pages143-154
Number of pages12
DOIs
StatePublished - 2009
Event17th Annual European Symposium on Algorithms, ESA 2009 - Copenhagen, Denmark
Duration: 7 Sep 20099 Sep 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5757 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference17th Annual European Symposium on Algorithms, ESA 2009
Country/TerritoryDenmark
CityCopenhagen
Period7/09/099/09/09

Fingerprint

Dive into the research topics of 'Output-sensitive algorithms for enumerating minimal transversals for some geometric hypergraphs'. Together they form a unique fingerprint.

Cite this