Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections

MPG-Autoren
/persons/resource/persons44374

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

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte in PuRe 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.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-000F-2AA6-C
Zusammenfassung
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$.