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/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The greedy sequential algorithm for maximal independent set (MIS) loops overthe vertices in arbitrary order adding a vertex to the resulting set if andonly if no previous neighboring vertex has been added. In this loop, as in manysequential loops, each iterate will only depend directly on a subset of theprevious iterates (i.e. knowing that any one of a vertices neighbors is in theMIS or knowing that it has no previous neighbors is sufficient to decide itsfate). This leads to a dependence structure among the iterates. If thisstructure is shallow then running the iterates in parallel while respecting thedependencies can lead to an efficient parallel implementation mimicking thesequential algorithm.  In this paper, we show that for any graph, and for a random ordering of thevertices, the dependence depth of the sequential greedy MIS algorithm ispolylogarithmic (O(log^2 n) with high probability). Our results extend previousresults that show polylogarithmic bounds only for random graphs. We showsimilar results for a greedy maximal matching (MM). For both problems wedescribe simple linear work parallel algorithms based on the approach. Thealgorithms allow for a smooth tradeoff between more parallelism and reducedwork, but always return the same result as the sequential greedy algorithms. Wepresent experimental results that demonstrate efficiency and the tradeoffbetween work and parallelism.

Greedy Sequential Maximal Independent Set and Matching are Parallel on Average