de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

#### Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44374

Elbassioni,  Khaled
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Boros, E., Elbassioni, K., Gurvich, V., & Khachiyan, L. (2004). Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections. In LATIN 2004: Theoretical Informatics, 6th Latin American Symposium (pp. 488-498). Berlin, Germany: Springer.

Given a finite set $V$, and integers $k \geq 1$ and $r \geq 0$, denote by $\AA(k,r)$ the class of hypergraphs $\cA \subseteq 2^V$ with $(k,r)$-bounded intersections, i.e. in which the intersection of any $k$ distinct hyperedges has size at most $r$. We consider the problem $MIS(\cA,\cI)$: given a hypergraph $\cA$ and a subfamily $\cI \subseteq \In$, of its maximal independent sets (MIS) $\In$, either extend this subfamily by constructing a new MIS $I \in \In \setminus \cI$ or prove that there are no more MIS, that is $\cI = \In$. We show that for hypergraphs $\cA\in\AA(k,r)$ with $k+r\le const$, problem MIS$(\cA,\cI)$ is NC-reducible to problem MIS$(\cA',\emptyset)$ of generating a single MIS for a partial subhypergraph $\cA'$ of $\cA$. In particular, for this class of hypergraphs, we get an incremental polynomial algorithm for generating all MIS. Furthermore, combining this result with the currently known algorithms for finding a single maximal independent set of a hypergraph, we obtain efficient parallel algorithms for incrementally generating all MIS for hypergraphs in the classes $\AA(1,c)$, $\AA(c,0)$, and $\AA(2,1)$, where $c$ is a constant. We also show that, for $\cA \in \AA(k,r)$, where $k+r\le const$, the problem of generating all MIS of $\cA$ can be solved in incremental polynomial-time with space polynomial only in the size of $\cA$.