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

metric spacesnetwork optimizationdistributed approximationprobabilistic tree embeddingsgeneralized steiner forestsleast element lists

Mathematics Subject Classification ID

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

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

(5)

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

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)