English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  An Efficient Incremental Algorithm for Generating All Maximal Independent Sets in Hypergraphs of Bounded Dimension

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).

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3373-7 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3374-5
Genre: Journal Article

Files

show Files
hide Files
:
ppl.ps (Publisher version), 221KB
 
File Permalink:
-
Name:
ppl.ps
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/postscript
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Boros, Endre, Author
Elbassioni, Khaled M.1, Author           
Khachiyan, Leonid, Author
Gurvich, Vladimir, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2007-05-022000
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: eDoc: 518228
Other: Local-ID: C1256428004B93B8-5A6FCBE2962F2B3FC1256FB0005EC3F9-Elbassioni2000
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Parallel Processing Letters
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 10 (4) Sequence Number: - Start / End Page: - Identifier: -