English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Open

Presents the pdf analysis as premium feature

PDF Analysis

Insights

Presents the summarisation as premium feature

Summarisation

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

A basic problem in hypergraphs is that of finding a large independent set-one of guaranteed size-in a given hypergraph. Understanding the parallel complexity of this and related independent set problems on hypergraphs is a fundamental open issue in parallel computation. Caro and Tuza (J. Graph Theory, Vol. 15, pp. 99-107, 1991) have shown a certain lower bound &agr;k(H) on the size of a maximum independent set in a given k-uniform hypergraph H, and have also presented an efficien sequential algorithm to find an independent set of size &agr;k (H). They also show that &agr;k (H) is the size of the maximum independent set for various hypergraph families. Here, we develop the first RNC algorithm to find an independent set of size &agr;k(H), and also derandomize it for various special cases. We also present lower bounds on independent set size and corresponding RNC algorithms for non-uniform hypergraphs.

Finding large independent sets of hypergraphs in parallel