Breaking the linear-memory barrier in MPC: fast MIS on trees with strongly sublinear memory

DOI10.1007/978-3-030-24922-9_9MaRDI QIDQ2303285zbMATH OpenOpenAlexFDO

Authors Manuela Fischer, Jara Uitto, Sebastian F. Brandt

Publication date 3 March 2020

Full work available at URL https://arxiv.org/abs/1802.06748

Mathematics Subject Classification ID

Computer system organization (68Mxx) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory
• scientific article; zbMATH DE number 4030978
• Improved MPC algorithms for MIS, matching, and coloring on trees and beyond
• scientific article; zbMATH DE number 7774301
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• The Fine Details of Fast Dynamic Programming over Tree Decompositions
• Bounded treewidth and space-efficient linear algebra
• Faster Algorithms for Quantitative Analysis of MCs and MDPs with Small Treewidth
• Efficient, oblivious data structures for MPC

Cited in

(5)

• Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory
• Streaming and massively parallel algorithms for edge coloring
• Log diameter rounds algorithms for 2-vertex and 2-edge connectivity
• Improved MPC algorithms for MIS, matching, and coloring on trees and beyond
• Exponential speedup over locality in \textsf{MPC} with optimal memory

This page was built for publication: Breaking the linear-memory barrier in MPC: fast MIS on trees with strongly sublinear memory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2303285)