Efficient distributed approximation algorithms via probabilistic tree embeddings

DOI10.1145/1400751.1400787MaRDI QIDQ5892002zbMATH OpenOpenAlexFDO

Authors Maleq Khan, Fabian Kuhn, Dahlia Malkhi, Gopal Pandurangan, Kunal Talwar

Publication date 12 December 2014

Published in Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1400751.1400787

zbMATH Keywords

distributed approximationgeneralized steiner forestsleast element listsmetric spacesnetwork optimizationprobabilistic tree embeddings

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Distributed algorithms (68W15) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Recommendations

• Efficient distributed approximation algorithms via probabilistic tree embeddings
• scientific article; zbMATH DE number 7204478
• A Fast Distributed Approximation Algorithm for Minimum Spanning Trees
• A fast distributed approximation algorithm for minimum spanning trees
• Distributed algorithms for low stretch spanning trees

Cited in

(6)

• Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
• Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE
• Efficient distributed approximation algorithms via probabilistic tree embeddings
• Singularly optimal randomized leader election
• Massively parallel approximate Steiner tree algorithms
• Efficient distributed computation of distance sketches in networks

This page was built for publication: Efficient distributed approximation algorithms via probabilistic tree embeddings

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