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

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Lower and upper bounds for finding a minimum spanning tree (MST) in a weighted undirected graph on the BSP model are presented. We provide the first non-trivial lower bounds on the communication volume required to solve the MST problem. Let p denote the number of processors, n the number of nodes of the input graph, and m the number of edges of the input graph. We show that in the worst case a total of Ω(k · min(m,pn)) bits need to be transmitted in order to solve the MST problem, where k is the number of bits required to represent a single edge weight. This implies that if a message can contain at most O(k) bits, any BSP algorithm for finding an MST requires communication time Ω(g ·min(m/p, n)), where g is the gap parameter of the BSP model. In addition, we present two algorithms whose running times match the lower bounds in different situations. Both algorithms perform linear work and use a number of supersteps independent of the input size. The first algorithm is simple but can employ at most m/n processors efficiently. Hence, it should be applied in situations where the input graph is relatively dense. The second algorithm is a randomized algorithm that performs linear work with high probability, provided that m ≥ n · log p. This is the first linear work BSP algorithm for finding an MST in sparse graphs. Department of Computer Science, University of Toronto, Canada. Email: micah@cs.toronto.edu. Supported by an operating grant from the Natural Sciences and Engineering Research Council of Canada, and by ITRC, an Ontario Centre of Excellence. This research was conducted in part while the author was at the Heinz Nixdorf Institute Graduate College, Paderborn, Germany. Bosch Telecom GmbH, Dept. UC-ON/ERS, Backnang, Germany. Email: Wolfgang.Dittrich2@pcm.bosch.de. This research was done while the author was working at the University of Paderborn, Germany. Heinz Nixdorf Institute, Dept. of Computer Science, University of Paderborn, Germany. Email: {benj,inri}@uni-paderborn.de. This research was partially supported by DFG-SFB 376 “Massive Parallelität” and EU ESPRIT Long Term Research Project 20244 (ALCOM-IT). Computer Science Institute, University of Wroc law, Poland. Email: mirekk@tcs.uni.wroc.pl.

Communication-optimal parallel minimum spanning tree algorithms (extended abstract)