Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Boros, Endre
Elbassioni, Khaled M.
Khachiyan, Leonid
Gurvich, Vladimir

dblp
dblp
dblp
dblp

Not MPG Author(s):

Boros, Endre
Gurvich, Vladimir
Khachiyan, Leonid

BibTeX cite key*:

Elbassioni2000

Title

Title*:

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

Journal

Journal Title*:

Parallel Processing Letters

Journal's URL:

http://www.worldscinet.com/ppl/ppl.shtml

Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

World Scientific

Publisher's URL:


Publisher's
Address:


ISSN:


Vol, No, pp, Date

Volume*:

10

Number:

4

Publishing Date:

December 2000

Pages*:

14

Number of
VG Pages:


Page Start:

253

Page End:

266

Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

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.

URL for the Abstract:


Categories,
Keywords:

Hypergraph Transversals, Parallel Algorithms, Lattices

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

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:

@ARTICLE{Elbassioni2000,
AUTHOR = {Boros, Endre and Elbassioni, Khaled M. and Khachiyan, Leonid and Gurvich, Vladimir},
TITLE = {An Efficient Incremental Algorithm for Generating All Maximal Independent Sets in Hypergraphs of Bounded Dimension},
JOURNAL = {Parallel Processing Letters},
PUBLISHER = {World Scientific},
YEAR = {2000},
NUMBER = {4},
VOLUME = {10},
PAGES = {14},
MONTH = {December},
}


Entry last modified by Christine Kiesel, 05/02/2007
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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/22/2005 06:15:05 PM
Revisions
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Khaled Elbassioni
Christine Kiesel
Khaled Elbassioni
Edit Dates
02.05.2007 16:48:12
04/20/2006 06:43:34 PM
21.04.2005 15:50:18
02/22/2005 06:15:05 PM