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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In parallel computing, a valid graph coloring yields a lock-free processingof the colored tasks, data points, etc., without expensive synchronizationmechanisms. However, coloring is not free and the overhead can be significant.In particular, for the bipartite-graph partial coloring (BGPC) and distance-2graph coloring (D2GC) problems, which have various use-cases within thescientific computing and numerical optimization domains, the coloring overheadcan be in the order of minutes with a single thread for many real-life graphs.  In this work, we propose parallel algorithms for bipartite-graph partialcoloring on shared-memory architectures. Compared to the existing shared-memoryBGPC algorithms, the proposed ones employ greedier and more optimistictechniques that yield a better parallel coloring performance. In particular, on16 cores, the proposed algorithms perform more than 4x faster than theircounterparts in the ColPack library which is, to the best of our knowledge, theonly publicly-available coloring library for multicore architectures. Inaddition to BGPC, the proposed techniques are employed to devise paralleldistance-2 graph coloring algorithms and similar performance improvements havebeen observed. Finally, we propose two costless balancing heuristics for BGPCthat can reduce the skewness and imbalance on the cardinality of color sets(almost) for free. The heuristics can also be used for the D2GC problem and ingeneral, they will probably yield a better color-based parallelizationperformance especially on many-core architectures.

Greed is Good: Optimistic Algorithms for Bipartite-Graph Partial Coloring on Multicore Architectures