Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the distributed complexity of large-scale graph computations
KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-9108-2448
2018 (English)In: SPAA '18 Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, Association for Computing Machinery (ACM), 2018, p. 405-414Conference paper, Published paper (Refereed)
Abstract [en]

Motivated by the increasing need to understand the distributed algorithmic foundations of large-scale graph computations, we study some fundamental graph problems in a message-passing model for distributed computing where k 2 machines jointly perform computations on graphs with n nodes (typically, n ≫ k). The input graph is assumed to be initially randomly partitioned among the k machines, a common implementation in many real-world systems. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2018. p. 405-414
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-234110DOI: 10.1145/3210377.3210409Scopus ID: 2-s2.0-85051131123ISBN: 9781450357999 (print)OAI: oai:DiVA.org:kth-234110DiVA, id: diva2:1245374
Conference
30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, Vienna, Austria, 16 July 2018 through 18 July 2018
Note

QC 20180905

Available from: 2018-09-05 Created: 2018-09-05 Last updated: 2018-09-05Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Scquizzato, Michele

Search in DiVA

By author/editor
Scquizzato, Michele
By organisation
Theoretical Computer Science, TCS
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 68 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf