de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

An Efficient Incremental Algorithm for Generating All Maximal Independent Sets in Hypergraphs of Bounded Dimension

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

Elbassioni,  Khaled M.
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. M., Khachiyan, L., & Gurvich, V. (2000). An Efficient Incremental Algorithm for Generating All Maximal Independent Sets in Hypergraphs of Bounded Dimension. Parallel Processing Letters, 10(4).


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-3373-7
Zusammenfassung
We show that for hypergraphs of bounded edge size, the problem of extending a given list of maximal independent sets is $NC$-reducible to the computation of an arbitrary maximal independent set for an induced sub-hypergraph. The latter problem is known to be in $RNC$. In particular, our reduction yields an incremental $RNC$ dualization algorithm for hypergraphs of bounded edge size, a problem previously known to be solvable in polynomial incremental time. We also give a similar parallel algorithm for the dualization problem on the product of arbitrary lattices which have a bounded number of immediate predecessors for each element.