MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

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, Martindblp
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
Conference URL::
Downloading URL:
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:
Note, Abstract, ©
(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},
 ADDRESS = {Buenos Aires, Argentina},
 MONTH = {April},
 ISBN = {3-540-21258-2},
}

Entry last modified by Christine Kiesel, 05/02/2007
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Khaled Elbassioni		Created
02/23/2005 02:33:12 PM
Revisions
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Khaled Elbassioni
Edit Dates
02.05.2007 15:39:34
23.05.2005 14:29:21
21.04.2005 16:22:57
02/23/2005 02:33:12 PM

File Attachment Icon
LATIN04.pdf