Strong Inapproximability of the Basic k-Spanner Problem. - Michael Elkin; David Peleg (ICALP, 2000)

Approximating k-Spanner Problems for k>2. - Michael Elkin; David Peleg (IPCO, 2001)

The Client-Server 2-Spanner Problem with Applications to Network Design. - Michael Elkin; David Peleg (SIROCCO, 2001)

Approximation Algorithm for Directed Telephone Multicast Problem. - Michael Elkin; Guy Kortsarz (ICALP, 2003)

Sublogarithmic approximation for telephone multicast: path out of jungle. - Michael Elkin; Guy Kortsarz (SODA, 2003)

Polylogarithmic Inapproximability of the Radio Broadcast Problem. - Michael Elkin; Guy Kortsarz (APPROX-RANDOM, 2004)

Efficient algorithms for constructing (1+, varepsilon;, beta)-spanners in the distributed and streaming models. - Michael Elkin; Jian Zhang 004 (PODC, 2004)

Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. - Michael Elkin (STOC, 2004)

Lower-Stretch Spanning Trees - Michael Elkin; Daniel A. Spielman; Shang-Hua Teng (CoRR, 2004)

Logarithmic inapproximability of the radio broadcast problem. - Michael Elkin; Guy Kortsarz (J. Algorithms, 2004)

(1+epsilon, beta)-Spanner Constructions for General Graphs. - Michael Elkin; David Peleg (SIAM J. Comput., 2004)

Distributed approximation: a survey. - Michael Elkin (SIGACT News, 2004)

Sparse source-wise and pair-wise distance preservers. - Don Coppersmith; Michael Elkin (SODA, 2005)

Improved schedule for radio broadcast. - Michael Elkin; Guy Kortsarz (SODA, 2005)

A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem. - Michael Elkin; Guy Kortsarz (SIAM J. Comput., 2005)

Sparse Distance Preservers and Additive Spanners. - Béla Bollobás; Don Coppersmith; Michael Elkin (SIAM J. Discret. Math., 2005)

Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem. - Michael Elkin; Guy Kortsarz (SIAM J. Discret. Math., 2005)

Computing almost shortest paths. - Michael Elkin (ACM Trans. Algorithms, 2005)

Approximating k-spanner problems for kge2. - Michael Elkin; David Peleg (Theor. Comput. Sci., 2005)

An Approximation Algorithm for the Directed Telephone Multicast Problem. - Michael Elkin; Guy Kortsarz (Algorithmica, 2006)

A near-optimal fully dynamic distributed algorithm for maintaining sparse spanners - Michael Elkin (CoRR, 2006)

Efficient algorithms for constructing (1+epsilon, beta)-spanners in the distributed and streaming models. - Michael Elkin; Jian Zhang 004 (Distributed Comput., 2006)

A faster distributed protocol for constructing a minimum spanning tree. - Michael Elkin (J. Comput. Syst. Sci., 2006)

Sublogarithmic approximation for telephone multicast. - Michael Elkin; Guy Kortsarz (J. Comput. Syst. Sci., 2006)

An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem. - Michael Elkin (SIAM J. Comput., 2006)

Sparse Sourcewise and Pairwise Distance Preservers. - Don Coppersmith; Michael Elkin (SIAM J. Discret. Math., 2006)

A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners. - Michael Elkin (PODC, 2007)

New length bounds for cycle bases. - Michael Elkin; Christian Liebchen; Romeo Rizzi (Inf. Process. Lett., 2007)

The Hardness of Approximating Spanner Problems. - Michael Elkin; David Peleg (Theory Comput. Syst., 2007)

An improved algorithm for radio broadcast. - Michael Elkin; Guy Kortsarz (ACM Trans. Algorithms, 2007)

Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners. - Yefim Dinitz; Michael Elkin; Shay Solomon (FOCS, 2008)

Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners - Yefim Dinitz; Michael Elkin; Shay Solomon (CoRR, 2008)

Bounds on the performance of back-to-front airplane boarding policies. - Eitan Bachmat; Michael Elkin (Oper. Res. Lett., 2008)

Lower-Stretch Spanning Trees. - Michael Elkin; Yuval Emek; Daniel A. Spielman; Shang-Hua Teng (SIAM J. Comput., 2008)

Low Stretch Spanning Trees. - Michael Elkin (Encyclopedia of Algorithms, 2008)

Sparse Graph Spanners. - Michael Elkin (Encyclopedia of Algorithms, 2008)

Synchronizers, Spanners. - Michael Elkin (Encyclopedia of Algorithms, 2008)

Distributed (delta+1)-coloring in linear (in delta) time. - Leonid Barenboim; Michael Elkin (STOC, 2009)

An Improved Construction of Progression-Free Sets. - Michael Elkin (SODA, 2010)

Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. - Leonid Barenboim; Michael Elkin (Distributed Comput., 2010)

Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners. - Yefim Dinitz; Michael Elkin; Shay Solomon (Discret. Comput. Geom., 2010)

Optimizing Budget Allocation in Graphs. - Boaz Ben-Moshe; Eran Omri; Michael Elkin (CCCG, 2011)

Deterministic Distributed Vertex Coloring in Polylogarithmic Time. - Leonid Barenboim; Michael Elkin (J. ACM, 2011)

Narrow-Shallow-Low-Light Trees with and without Steiner Points. - Michael Elkin; Shay Solomon (SIAM J. Discret. Math., 2011)

Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. - Michael Elkin (ACM Trans. Algorithms, 2011)

Novel algorithms for the network lifetime problem in wireless settings. - Michael Elkin; Yuval Lando; Zeev Nutov; Michael Segal 001; Hanan Shpungin (Wirel. Networks, 2011)

Fast Distributed Algorithms for Maximal Matching and Maximal Independent Set - Leonid Barenboim; Michael Elkin; Seth Pettie; Johannes Schneider 002 (CoRR, 2012)

Quantum Distributed Network Computing: Lower Bounds and Techniques - Michael Elkin; Hartmut Klauck; Danupon Nanongkai; Gopal Pandurangan (CoRR, 2012)

Fast Constructions of Light-Weight Spanners for General Graphs. - Michael Elkin; Shay Solomon (SODA, 2013)

Distributed deterministic edge coloring using bounded neighborhood independence. - Leonid Barenboim; Michael Elkin (Distributed Comput., 2013)

Symmetry breaking depending on the chromatic number or the neighborhood growth. - Johannes Schneider 002; Michael Elkin; Roger Wattenhofer (Theor. Comput. Sci., 2013)

Distributed Graph Coloring: Fundamentals and Recent Developments - Leonid Barenboim; Michael Elkin (Distributed Graph Coloring, 2013)

Can quantum communication speed up distributed computation? - Michael Elkin; Hartmut Klauck; Danupon Nanongkai; Gopal Pandurangan (PODC, 2014)

Optimizing Budget Allocation in Graphs. - Boaz Ben-Moshe; Michael Elkin; Lee-Ad Gottlieb; Eran Omri (CoRR, 2014)

Combinatorial algorithms for distributed graph coloring. - Leonid Barenboim; Michael Elkin (Distributed Comput., 2014)

Distributed (Delta+1)-Coloring in Linear (in Delta) Time. - Leonid Barenboim; Michael Elkin; Fabian Kuhn (SIAM J. Comput., 2014)

Balancing Degree, Diameter, and Weight in Euclidean Spanners. - Shay Solomon; Michael Elkin (SIAM J. Discret. Math., 2014)

A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation - (Extended Abstract). - Leonid Barenboim; Michael Elkin; Cyril Gavoille (SIROCCO, 2015)

(2Δ - l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting. - Michael Elkin; Seth Pettie; Hsin-Hao Su (SODA, 2015)

Optimal Euclidean Spanners: Really Short, Thin, and Lanky. - Michael Elkin; Shay Solomon (J. ACM, 2015)

Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones. - Michael Elkin; Shay Solomon (SIAM J. Comput., 2015)

Light Spanners. - Michael Elkin; Ofer Neiman; Shay Solomon (SIAM J. Discret. Math., 2015)

Distributed Strong Diameter Network Decomposition: Extended Abstract. - Michael Elkin; Ofer Neiman (PODC, 2016)

On Efficient Distributed Construction of Near Optimal Routing Schemes: Extended Abstract. - Michael Elkin; Ofer Neiman (PODC, 2016)

Deterministic Distributed (Delta + o(Δ))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity. - Leonid Barenboim; Michael Elkin; Tzalik Maimon (CoRR, 2016)

The Locality of Distributed Symmetry Breaking. - Leonid Barenboim; Michael Elkin; Seth Pettie; Johannes Schneider 002 (J. ACM, 2016)

A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. - Michael Elkin; Seth Pettie (ACM Trans. Algorithms, 2016)

Fast Constructions of Lightweight Spanners for General Graphs. - Michael Elkin; Shay Solomon (ACM Trans. Algorithms, 2016)

Optimizing budget allocation for center and median points. - Boaz Ben-Moshe; Michael Elkin; Lee-Ad Gottlieb; Eran Omri (Theor. Comput. Sci., 2016)

Space-efficient path-reporting approximate distance oracles. - Michael Elkin; Ofer Neiman; Christian Wulff-Nilsen (Theor. Comput. Sci., 2016)

Low Stretch Spanning Trees. - Michael Elkin (Encyclopedia of Algorithms, 2016)

Sparse Graph Spanners. - Michael Elkin (Encyclopedia of Algorithms, 2016)

Synchronizers, Spanners. - Michael Elkin (Encyclopedia of Algorithms, 2016)

Deterministic Distributed (Delta + o(Delta))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity. - Leonid Barenboim; Michael Elkin; Tzalik Maimon (PODC, 2017)

Linear-Size Hopsets with Small Hopbound, and Distributed Routing with Low Memory. - Michael Elkin; Ofer Neiman (CoRR, 2017)

Locally-Iterative Distributed (Delta + 1)-Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models. - Leonid Barenboim; Michael Elkin; Uri Goldenberg (CoRR, 2017)

Terminal embeddings. - Michael Elkin; Arnold Filtser; Ofer Neiman (Theor. Comput. Sci., 2017)

Locally-Iterative Distributed (Δ+ 1): -Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models. - Leonid Barenboim; Michael Elkin; Uri Goldenberg (PODC, 2018)

Session details: Session 3D: Graphs and Population. - Michael Elkin (PODC, 2018)

Near-Optimal Distributed Routing with Low Memory. - Michael Elkin; Ofer Neiman (PODC, 2018)

On efficient distributed construction of near optimal routing schemes. - Michael Elkin; Ofer Neiman (Distributed Comput., 2018)

Prioritized Metric Structures and Embedding. - Michael Elkin; Arnold Filtser; Ofer Neiman (SIAM J. Comput., 2018)

A fast network-decomposition algorithm and its applications to constant-time distributed computation. - Leonid Barenboim; Michael Elkin; Cyril Gavoille (Theor. Comput. Sci., 2018)

Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time. - Michael Elkin; Shaked Matar (PODC, 2019)

Fast Deterministic Constructions of Linear-Size Spanners and Skeletons. - Michael Elkin; Shaked Matar (CoRR, 2019)

Almost Shortest Paths and PRAM Distance Oracles in Weighted Graphs. - Michael Elkin; Yuval Gitlitz; Ofer Neiman (CoRR, 2019)

Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. - Michael Elkin; Ofer Neiman (SIAM J. Comput., 2019)

Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. - Michael Elkin; Ofer Neiman (ACM Trans. Algorithms, 2019)

Distributed Construction of Light Networks. - Michael Elkin; Arnold Filtser; Ofer Neiman (PODC, 2020)

Centralized and Parallel Multi-Source Shortest Paths via Hopsets and Fast Matrix Multiplication. - Michael Elkin; Ofer Neiman (CoRR, 2020)

Near-Additive Spanners and Near-Exact Hopsets, A Unified View. - Michael Elkin; Ofer Neiman (Bull. EATCS, 2020)

A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities. - Michael Elkin (J. ACM, 2020)

Distributed Exact Shortest Paths in Sublinear Time. - Michael Elkin (J. ACM, 2020)

Ramsey Spanning Trees and Their Applications. - Ittai Abraham; Shiri Chechik; Michael Elkin; Arnold Filtser; Ofer Neiman (ACM Trans. Algorithms, 2020)

Ultra-Sparse Near-Additive Emulators. - Michael Elkin; Shaked Matar (PODC, 2021)

Deterministic PRAM Approximate Shortest Paths in Polylogarithmic Time and Slightly Super-Linear Work. - Michael Elkin; Shaked Matar (SPAA, 2021)

Near Isometric Terminal Embeddings for Doubling Metrics. - Michael Elkin; Ofer Neiman (Algorithmica, 2021)

(1+ε)-Approximate Shortest Paths in Dynamic Streams. - Michael Elkin; Chhaya Trehan (APPROX/RANDOM, 2022)

Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications. - Václav Rozhon; Michael Elkin; Christoph Grunau; Bernhard Haeupler (FOCS, 2022)

Brief Announcement: (1+ε)-Approximate Shortest Paths in Dynamic Streams. - Michael Elkin; Chhaya Trehan (PODC, 2022)

Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates. - Marcel Bezdrighin; Michael Elkin; Mohsen Ghaffari 001; Christoph Grunau; Bernhard Haeupler; Saeed Ilchi; Václav Rozhon (SPAA, 2022)

Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication. - Michael Elkin; Ofer Neiman (STACS, 2022)

Almost Shortest Paths with Near-Additive Error in Weighted Graphs. - Michael Elkin; Yuval Gitlitz; Ofer Neiman (SWAT, 2022)

Linear-Size hopsets with small hopbound, and constant-hopbound hopsets in RNC. - Michael Elkin; Ofer Neiman (Distributed Comput., 2022)

Locally-iterative Distributed (Δ + 1)-coloring and Applications. - Leonid Barenboim; Michael Elkin; Uri Goldenberg (J. ACM, 2022)

Lossless Prioritized Embeddings. - Michael Elkin; Ofer Neiman (SIAM J. Discret. Math., 2022)

Distributed strong diameter network decomposition. - Michael Elkin; Ofer Neiman (Theor. Comput. Sci., 2022)

Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n log log n). - Michael Elkin; Idan Shabat (FOCS, 2023)

Path-Reporting Distance Oracles with Near-Logarithmic Stretch and Linear Size. - Michael Elkin; Idan Shabat (CoRR, 2023)

Improved weighted additive spanners. - Michael Elkin; Yuval Gitlitz; Ofer Neiman (Distributed Comput., 2023)

Faster Multi-Source Directed Reachability via Shortcuts and Matrix Multiplication. - Michael Elkin; Chhaya Trehan (CoRR, 2024)

Deterministic Simple (1+°)Δ-Edge-Coloring in Near-Linear Time. - Michael Elkin; Ariel Khuzman (CoRR, 2024)

Faster Multi-Source Reachability and Approximate Distances via Shortcuts, Hopsets and Matrix Multiplication. - Michael Elkin; Chhaya Trehan (CoRR, 2025)