Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Boros, Endre Elbassioni, Khaled M. Gurvich, Vladimir Khachiyan, Leonid dblp dblp dblp dblp Not MPG Author(s): Boros, Endre Gurvich, Vladimir Khachiyan, Leonid
 Editor(s): Farach-Colton, Martin dblp Not MPII Editor(s): Farach-Colton, Martin
 BibTeX cite key*: Elbassioni2004d

 Title, Booktitle
 Title*: Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections LATIN04.pdf (182.6 KB) Booktitle*: LATIN 2004: Theoretical Informatics, 6th Latin American Symposium

 Event, URLs
 URL of the conference: URL for downloading the paper: Event Address*: Buenos Aires, Argentina Language: English Event Date* (no longer used): Organization: Event Start Date: 5 April 2004 Event End Date: 8 April 2004

 Publisher
 Name*: Springer URL: Address*: Berlin, Germany Type:

 Vol, No, Year, pp.
 Series: Lecture Notes in Computer Science
 Volume: 2976 Number: Month: April Pages: 488-498 Year*: 2004 VG Wort Pages: ISBN/ISSN: 3-540-21258-2 Sequence Number: DOI:

 (LaTeX) Abstract: 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$. 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{Elbassioni2004d,
AUTHOR = {Boros, Endre and Elbassioni, Khaled M. and Gurvich, Vladimir and Khachiyan, Leonid},
EDITOR = {Farach-Colton, Martin},
TITLE = {Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections},
BOOKTITLE = {LATIN 2004: Theoretical Informatics, 6th Latin American Symposium},
PUBLISHER = {Springer},
YEAR = {2004},
VOLUME = {2976},
PAGES = {488--498},
SERIES = {Lecture Notes in Computer Science},