Graph spanners in the message-passing model

DOI10.4230/LIPICS.ITCS.2020.77MaRDI QIDQ5875784zbMATH OpenFDO

Authors David P. Woodruff, Taisuke Yasuda

Publication date 3 February 2023

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

zbMATH Keywords

communication complexitygraph spannersmessage-passing model

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Local Computation of Nearly Additive Spanners
• On the locality of distributed sparse spanner construction
• Additive spanners and \(({\alpha}, {\beta})\)-spanners

Cited in

(2)

• Message Reduction in the LOCAL Model is a Free Lunch
• Communication-efficient distributed graph clustering and sparsification under duplication models

This page was built for publication: Graph spanners in the message-passing model

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