Michael Elkin - RankMe

176 papers A* 48A 6B 6Journal 102Unranked 7

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Efficient Parallel (Δ+1)-Edge-Coloring. CoRR Michael Elkin, Ariel Khuzman
2025	J	`jnl`	Faster Multi-Source Reachability and Approximate Distances via Shortcuts, Hopsets and Matrix Multiplication. CoRR Michael Elkin, Chhaya Trehan
2025	J	`jnl`	Spanning and Metric Tree Covers Parameterized by Treewidth. CoRR Michael Elkin, Idan Shabat
2024	J	`jnl`	Deterministic Simple (1+°)Δ-Edge-Coloring in Near-Linear Time. CoRR Michael Elkin, Ariel Khuzman
2024	J	`jnl`	Faster Multi-Source Directed Reachability via Shortcuts and Matrix Multiplication. CoRR Michael Elkin, Chhaya Trehan
2023	J	`jnl`	Improved weighted additive spanners. Distributed Comput. Michael Elkin, Yuval Gitlitz, Ofer Neiman
2023	A*	`conf`	Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n log log n). FOCS Michael Elkin, Idan Shabat
2023	J	`jnl`	Path-Reporting Distance Oracles with Near-Logarithmic Stretch and Linear Size. CoRR Michael Elkin, Idan Shabat
2022	A	`conf`	(1+ε)-Approximate Shortest Paths in Dynamic Streams. APPROX/RANDOM Michael Elkin, Chhaya Trehan
2022	—	`conf`	Almost Shortest Paths with Near-Additive Error in Weighted Graphs. SWAT Michael Elkin, Yuval Gitlitz, Ofer Neiman
2022	A*	`conf`	Brief Announcement: (1+ε)-Approximate Shortest Paths in Dynamic Streams. PODC Michael Elkin, Chhaya Trehan
2022	A	`conf`	Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication. STACS Michael Elkin, Ofer Neiman
2022	B	`conf`	Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates. SPAA Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon
2022	J	`jnl`	Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates. CoRR Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon
2022	A*	`conf`	Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications. FOCS Václav Rozhon, Michael Elkin, Christoph Grunau, Bernhard Haeupler
2022	J	`jnl`	Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications. CoRR Michael Elkin, Bernhard Haeupler, Václav Rozhon, Christoph Grunau
2022	J	`jnl`	Distributed strong diameter network decomposition. Theor. Comput. Sci. Michael Elkin, Ofer Neiman
2022	J	`jnl`	Linear-Size hopsets with small hopbound, and constant-hopbound hopsets in RNC. Distributed Comput. Michael Elkin, Ofer Neiman
2022	J	`jnl`	Locally-iterative Distributed (Δ + 1)-coloring and Applications. J. ACM Leonid Barenboim, Michael Elkin, Uri Goldenberg
2022	J	`jnl`	Lossless Prioritized Embeddings. SIAM J. Discret. Math. Michael Elkin, Ofer Neiman
2021	J	`jnl`	$(1+ε)$-Approximate Shortest Paths in Dynamic Streams. CoRR Michael Elkin, Chhaya Trehan
2021	B	`conf`	Deterministic PRAM Approximate Shortest Paths in Polylogarithmic Time and Slightly Super-Linear Work. SPAA Michael Elkin, Shaked Matar
2021	A	`conf`	Improved Weighted Additive Spanners. DISC Michael Elkin, Yuval Gitlitz, Ofer Neiman
2021	J	`jnl`	Near Isometric Terminal Embeddings for Doubling Metrics. Algorithmica Michael Elkin, Ofer Neiman
2021	A*	`conf`	Ultra-Sparse Near-Additive Emulators. PODC Michael Elkin, Shaked Matar
2021	J	`jnl`	Ultra-Sparse Near-Additive Emulators. CoRR Michael Elkin, Shaked Matar
2020	J	`jnl`	A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities. J. ACM Michael Elkin
2020	J	`jnl`	Centralized and Parallel Multi-Source Shortest Paths via Hopsets and Fast Matrix Multiplication. CoRR Michael Elkin, Ofer Neiman
2020	J	`jnl`	Deterministic PRAM Approximate Shortest Paths in Polylogarithmic Time and Slightly Super-Linear Work. CoRR Michael Elkin, Shaked Matar
2020	A*	`conf`	Distributed Construction of Light Networks. PODC Michael Elkin, Arnold Filtser, Ofer Neiman
2020	J	`jnl`	Distributed Exact Shortest Paths in Sublinear Time. J. ACM Michael Elkin
2020	J	`jnl`	Improved Weighted Additive Spanners. CoRR Michael Elkin, Yuval Gitlitz, Ofer Neiman
2020	A*	`conf`	Lossless Prioritized Embeddings. SODA Michael Elkin, Ofer Neiman
2020	J	`jnl`	Near-Additive Spanners and Near-Exact Hopsets, A Unified View. CoRR Michael Elkin, Ofer Neiman
2020	J	`jnl`	Near-Additive Spanners and Near-Exact Hopsets, A Unified View. Bull. EATCS Michael Elkin, Ofer Neiman
2020	J	`jnl`	Ramsey Spanning Trees and Their Applications. ACM Trans. Algorithms Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, Ofer Neiman
2019	J	`jnl`	Almost Shortest Paths and PRAM Distance Oracles in Weighted Graphs. CoRR Michael Elkin, Yuval Gitlitz, Ofer Neiman
2019	J	`jnl`	Distributed Construction of Light Networks. CoRR Michael Elkin, Arnold Filtser, Ofer Neiman
2019	J	`jnl`	Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. ACM Trans. Algorithms Michael Elkin, Ofer Neiman
2019	J	`jnl`	Fast Deterministic Constructions of Linear-Size Spanners and Skeletons. CoRR Michael Elkin, Shaked Matar
2019	J	`jnl`	Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. SIAM J. Comput. Michael Elkin, Ofer Neiman
2019	B	`conf`	Linear-Size Hopsets with Small Hopbound, and Constant-Hopbound Hopsets in RNC. SPAA Michael Elkin, Ofer Neiman
2019	J	`jnl`	Lossless Prioritized Embeddings. CoRR Michael Elkin, Ofer Neiman
2019	A*	`conf`	Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time. PODC Michael Elkin, Shaked Matar
2019	J	`jnl`	Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time. CoRR Michael Elkin, Shaked Matar
2018	J	`jnl`	A fast network-decomposition algorithm and its applications to constant-time distributed computation. Theor. Comput. Sci. Leonid Barenboim, Michael Elkin, Cyril Gavoille
2018	A*	`conf`	Locally-Iterative Distributed (Δ+ 1): -Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models. PODC Leonid Barenboim, Michael Elkin, Uri Goldenberg
2018	A*	`conf`	Near Isometric Terminal Embeddings for Doubling Metrics. SoCG Michael Elkin, Ofer Neiman
2018	J	`jnl`	Near Isometric Terminal Embeddings for Doubling Metrics. CoRR Michael Elkin, Ofer Neiman
2018	A*	`conf`	Near-Optimal Distributed Routing with Low Memory. PODC Michael Elkin, Ofer Neiman
2018	J	`jnl`	On efficient distributed construction of near optimal routing schemes. Distributed Comput. Michael Elkin, Ofer Neiman
2018	J	`jnl`	Prioritized Metric Structures and Embedding. SIAM J. Comput. Michael Elkin, Arnold Filtser, Ofer Neiman
2018	A*	`conf`	Ramsey Spanning Trees and their Applications. SODA Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, Ofer Neiman
2018	A*	`conf`	Session details: Session 3D: Graphs and Population. PODC Michael Elkin
2017	A*	`conf`	A Simple Deterministic Distributed MST Algorithm, with Near-Optimal Time and Message Complexities. PODC Michael Elkin
2017	J	`jnl`	A Simple Deterministic Distributed MST Algorithm, with Near-Optimal Time and Message Complexities. CoRR Michael Elkin
2017	A*	`conf`	Deterministic Distributed (Delta + o(Delta))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity. PODC Leonid Barenboim, Michael Elkin, Tzalik Maimon
2017	J	`jnl`	Distributed Exact Shortest Paths in Sublinear Time. CoRR Michael Elkin
2017	A*	`conf`	Distributed exact shortest paths in sublinear time. STOC Michael Elkin
2017	A*	`conf`	Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. SODA Michael Elkin, Ofer Neiman
2017	J	`jnl`	Linear-Size Hopsets with Small Hopbound, and Distributed Routing with Low Memory. CoRR Michael Elkin, Ofer Neiman
2017	J	`jnl`	Locally-Iterative Distributed (Delta + 1)-Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models. CoRR Leonid Barenboim, Michael Elkin, Uri Goldenberg
2017	J	`jnl`	Ramsey Spanning Trees and their Applications. CoRR Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, Ofer Neiman
2017	J	`jnl`	Terminal embeddings. Theor. Comput. Sci. Michael Elkin, Arnold Filtser, Ofer Neiman
2016	J	`jnl`	A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. ACM Trans. Algorithms Michael Elkin, Seth Pettie
2016	J	`jnl`	Deterministic Distributed (Delta + o(Δ))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity. CoRR Leonid Barenboim, Michael Elkin, Tzalik Maimon
2016	J	`jnl`	Distributed Strong Diameter Network Decomposition. CoRR Michael Elkin, Ofer Neiman
2016	A*	`conf`	Distributed Strong Diameter Network Decomposition: Extended Abstract. PODC Michael Elkin, Ofer Neiman
2016	J	`jnl`	Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. CoRR Michael Elkin, Ofer Neiman
2016	J	`jnl`	Fast Constructions of Lightweight Spanners for General Graphs. ACM Trans. Algorithms Michael Elkin, Shay Solomon
2016	A*	`conf`	Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. FOCS Michael Elkin, Ofer Neiman
2016	J	`jnl`	Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. CoRR Michael Elkin, Ofer Neiman
2016	—	`ch.`	Low Stretch Spanning Trees. Encyclopedia of Algorithms Michael Elkin
2016	J	`jnl`	On Efficient Distributed Construction of Near Optimal Routing Schemes. CoRR Michael Elkin, Ofer Neiman
2016	A*	`conf`	On Efficient Distributed Construction of Near Optimal Routing Schemes: Extended Abstract. PODC Michael Elkin, Ofer Neiman
2016	J	`jnl`	Optimizing budget allocation for center and median points. Theor. Comput. Sci. Boaz Ben-Moshe, Michael Elkin, Lee-Ad Gottlieb, Eran Omri
2016	J	`jnl`	Space-efficient path-reporting approximate distance oracles. Theor. Comput. Sci. Michael Elkin, Ofer Neiman, Christian Wulff-Nilsen
2016	—	`ch.`	Sparse Graph Spanners. Encyclopedia of Algorithms Michael Elkin
2016	—	`ch.`	Synchronizers, Spanners. Encyclopedia of Algorithms Michael Elkin
2016	J	`jnl`	Terminal Embeddings. CoRR Michael Elkin, Arnold Filtser, Ofer Neiman
2016	J	`jnl`	The Locality of Distributed Symmetry Breaking. J. ACM Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider
2015	A*	`conf`	(2Δ - l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting. SODA Michael Elkin, Seth Pettie, Hsin-Hao Su
2015	B	`conf`	A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation - (Extended Abstract). SIROCCO Leonid Barenboim, Michael Elkin, Cyril Gavoille
2015	J	`jnl`	A Fast Network-Decomposition Algorithm and its Applications to Constant-Time Distributed Computation. CoRR Leonid Barenboim, Michael Elkin, Cyril Gavoille
2015	A*	`conf`	A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. SODA Michael Elkin, Seth Pettie
2015	J	`jnl`	A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. CoRR Michael Elkin, Seth Pettie
2015	J	`jnl`	Light Spanners. SIAM J. Discret. Math. Michael Elkin, Ofer Neiman, Shay Solomon
2015	J	`jnl`	Optimal Euclidean Spanners: Really Short, Thin, and Lanky. J. ACM Michael Elkin, Shay Solomon
2015	A*	`conf`	Prioritized Metric Structures and Embedding. STOC Michael Elkin, Arnold Filtser, Ofer Neiman
2015	J	`jnl`	Prioritized Metric Structures and Embedding. CoRR Michael Elkin, Arnold Filtser, Ofer Neiman
2015	J	`jnl`	Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones. SIAM J. Comput. Michael Elkin, Shay Solomon
2015	—	`conf`	Terminal Embeddings. APPROX-RANDOM Michael Elkin, Arnold Filtser, Ofer Neiman
2014	J	`jnl`	Balancing Degree, Diameter, and Weight in Euclidean Spanners. SIAM J. Discret. Math. Shay Solomon, Michael Elkin
2014	A*	`conf`	Can quantum communication speed up distributed computation? PODC Michael Elkin, Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan
2014	J	`jnl`	Combinatorial algorithms for distributed graph coloring. Distributed Comput. Leonid Barenboim, Michael Elkin
2014	J	`jnl`	Distributed (Delta+1)-Coloring in Linear (in Delta) Time. SIAM J. Comput. Leonid Barenboim, Michael Elkin, Fabian Kuhn
2014	—	`conf`	Light Spanners. ICALP (1) Michael Elkin, Ofer Neiman, Shay Solomon
2014	J	`jnl`	Light Spanners. CoRR Michael Elkin, Ofer Neiman, Shay Solomon
2014	J	`jnl`	Optimizing Budget Allocation in Graphs. CoRR Boaz Ben-Moshe, Michael Elkin, Lee-Ad Gottlieb, Eran Omri
2014	J	`jnl`	Space-Efficient Path-Reporting Approximate Distance Oracles. CoRR Michael Elkin, Ofer Neiman, Christian Wulff-Nilsen
2013	—	`book`	Distributed Graph Coloring: Fundamentals and Recent Developments Distributed Graph Coloring Leonid Barenboim, Michael Elkin
2013	J	`jnl`	Distributed deterministic edge coloring using bounded neighborhood independence. Distributed Comput. Leonid Barenboim, Michael Elkin
2013	A*	`conf`	Fast Constructions of Light-Weight Spanners for General Graphs. SODA Michael Elkin, Shay Solomon
2013	A*	`conf`	Optimal euclidean spanners: really short, thin and lanky. STOC Michael Elkin, Shay Solomon
2013	J	`jnl`	Symmetry breaking depending on the chromatic number or the neighborhood growth. Theor. Comput. Sci. Johannes Schneider, Michael Elkin, Roger Wattenhofer
2012	J	`jnl`	Fast Constructions of Light-Weight Spanners for General Graphs CoRR Michael Elkin, Shay Solomon
2012	J	`jnl`	Fast Distributed Algorithms for Maximal Matching and Maximal Independent Set CoRR Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider
2012	J	`jnl`	Optimal Euclidean spanners: really short, thin and lanky CoRR Michael Elkin, Shay Solomon
2012	J	`jnl`	Quantum Distributed Network Computing: Lower Bounds and Techniques CoRR Michael Elkin, Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan
2012	A*	`conf`	The Locality of Distributed Symmetry Breaking. FOCS Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider
2011	J	`jnl`	Balancing Degree, Diameter and Weight in Euclidean Spanners CoRR Shay Solomon, Michael Elkin
2011	A	`conf`	Combinatorial Algorithms for Distributed Graph Coloring. DISC Leonid Barenboim, Michael Elkin
2011	J	`jnl`	Deterministic Distributed Vertex Coloring in Polylogarithmic Time. J. ACM Leonid Barenboim, Michael Elkin
2011	A*	`conf`	Distributed deterministic edge coloring using bounded neighborhood independence. PODC Leonid Barenboim, Michael Elkin
2011	J	`jnl`	Narrow-Shallow-Low-Light Trees with and without Steiner Points. SIAM J. Discret. Math. Michael Elkin, Shay Solomon
2011	J	`jnl`	Novel algorithms for the network lifetime problem in wireless settings. Wirel. Networks Michael Elkin, Yuval Lando, Zeev Nutov, Michael Segal, Hanan Shpungin
2011	—	`conf`	Optimizing Budget Allocation in Graphs. CCCG Boaz Ben-Moshe, Eran Omri, Michael Elkin
2011	A*	`conf`	Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones. FOCS Michael Elkin, Shay Solomon
2011	J	`jnl`	Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Trans. Algorithms Michael Elkin
2010	A*	`conf`	An Improved Construction of Progression-Free Sets. SODA Michael Elkin
2010	—	`conf`	Balancing Degree, Diameter and Weight in Euclidean Spanners. ESA (1) Shay Solomon, Michael Elkin
2010	J	`jnl`	Deterministic Distributed Vertex Coloring in Polylogarithmic Time CoRR Leonid Barenboim, Michael Elkin
2010	A*	`conf`	Deterministic distributed vertex coloring in polylogarithmic time. PODC Leonid Barenboim, Michael Elkin
2010	J	`jnl`	Distributed Deterministic Edge Coloring using Bounded Neighborhood Independence CoRR Leonid Barenboim, Michael Elkin
2010	J	`jnl`	Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners. Discret. Comput. Geom. Yefim Dinitz, Michael Elkin, Shay Solomon
2010	J	`jnl`	Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. Distributed Comput. Leonid Barenboim, Michael Elkin
2009	A*	`conf`	Distributed (delta+1)-coloring in linear (in delta) time. STOC Leonid Barenboim, Michael Elkin
2009	A	`conf`	Narrow-Shallow-Low-Light Trees with and without Steiner Points. ESA Michael Elkin, Shay Solomon
2008	J	`jnl`	Bounds on the performance of back-to-front airplane boarding policies. Oper. Res. Lett. Eitan Bachmat, Michael Elkin
2008	J	`jnl`	Distributed (Delta + 1)-coloring in linear (in Delta) time CoRR Leonid Barenboim, Michael Elkin
2008	—	`ch.`	Low Stretch Spanning Trees. Encyclopedia of Algorithms Michael Elkin
2008	J	`jnl`	Lower-Stretch Spanning Trees. SIAM J. Comput. Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng
2008	—	`conf`	Novel Algorithms for the Network Lifetime Problem in Wireless Settings. ADHOC-NOW Michael Elkin, Yuval Lando, Zeev Nutov, Michael Segal, Hanan Shpungin
2008	J	`jnl`	Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners CoRR Yefim Dinitz, Michael Elkin, Shay Solomon
2008	A*	`conf`	Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners. FOCS Yefim Dinitz, Michael Elkin, Shay Solomon
2008	—	`ch.`	Sparse Graph Spanners. Encyclopedia of Algorithms Michael Elkin
2008	A*	`conf`	Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition. PODC Leonid Barenboim, Michael Elkin
2008	—	`ch.`	Synchronizers, Spanners. Encyclopedia of Algorithms Michael Elkin
2007	A*	`conf`	A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners. PODC Michael Elkin
2007	J	`jnl`	An improved algorithm for radio broadcast. ACM Trans. Algorithms Michael Elkin, Guy Kortsarz
2007	J	`jnl`	New length bounds for cycle bases. Inf. Process. Lett. Michael Elkin, Christian Liebchen, Romeo Rizzi
2007	A*	`conf`	Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners. ICALP Michael Elkin
2007	J	`jnl`	The Hardness of Approximating Spanner Problems. Theory Comput. Syst. Michael Elkin, David Peleg
2006	J	`jnl`	A faster distributed protocol for constructing a minimum spanning tree. J. Comput. Syst. Sci. Michael Elkin
2006	J	`jnl`	A near-optimal fully dynamic distributed algorithm for maintaining sparse spanners CoRR Michael Elkin
2006	J	`jnl`	An Approximation Algorithm for the Directed Telephone Multicast Problem. Algorithmica Michael Elkin, Guy Kortsarz
2006	J	`jnl`	An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem. SIAM J. Comput. Michael Elkin
2006	J	`jnl`	Efficient algorithms for constructing (1+epsilon, beta)-spanners in the distributed and streaming models. Distributed Comput. Michael Elkin, Jian Zhang
2006	J	`jnl`	Sparse Sourcewise and Pairwise Distance Preservers. SIAM J. Discret. Math. Don Coppersmith, Michael Elkin
2006	J	`jnl`	Sublogarithmic approximation for telephone multicast. J. Comput. Syst. Sci. Michael Elkin, Guy Kortsarz
2005	J	`jnl`	A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem. SIAM J. Comput. Michael Elkin, Guy Kortsarz
2005	J	`jnl`	Approximating Theor. Comput. Sci. Michael Elkin, David Peleg
2005	J	`jnl`	Computing almost shortest paths. ACM Trans. Algorithms Michael Elkin
2005	A*	`conf`	Improved schedule for radio broadcast. SODA Michael Elkin, Guy Kortsarz
2005	A*	`conf`	Lower-stretch spanning trees. STOC Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng
2005	J	`jnl`	Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem. SIAM J. Discret. Math. Michael Elkin, Guy Kortsarz
2005	J	`jnl`	Sparse Distance Preservers and Additive Spanners. SIAM J. Discret. Math. Béla Bollobás, Don Coppersmith, Michael Elkin
2005	A*	`conf`	Sparse source-wise and pair-wise distance preservers. SODA Don Coppersmith, Michael Elkin
2004	J	`jnl`	(1+epsilon, beta)-Spanner Constructions for General Graphs. SIAM J. Comput. Michael Elkin, David Peleg
2004	A*	`conf`	A faster distributed protocol for constructing a minimum spanning tree. SODA Michael Elkin
2004	J	`jnl`	Distributed approximation: a survey. SIGACT News Michael Elkin
2004	A*	`conf`	Efficient algorithms for constructing (1+, varepsilon;, beta)-spanners in the distributed and streaming models. PODC Michael Elkin, Jian Zhang
2004	J	`jnl`	Logarithmic inapproximability of the radio broadcast problem. J. Algorithms Michael Elkin, Guy Kortsarz
2004	J	`jnl`	Lower-Stretch Spanning Trees CoRR Michael Elkin, Daniel A. Spielman, Shang-Hua Teng
2004	—	`conf`	Polylogarithmic Inapproximability of the Radio Broadcast Problem. APPROX-RANDOM Michael Elkin, Guy Kortsarz
2004	A*	`conf`	Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. STOC Michael Elkin
2003	A*	`conf`	Approximation Algorithm for Directed Telephone Multicast Problem. ICALP Michael Elkin, Guy Kortsarz
2003	A*	`conf`	Sparse distance preservers and additive spanners. SODA Béla Bollobás, Don Coppersmith, Michael Elkin
2003	A*	`conf`	Sublogarithmic approximation for telephone multicast: path out of jungle. SODA Michael Elkin, Guy Kortsarz
2002	A*	`conf`	Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem. STOC Michael Elkin, Guy Kortsarz
2001	A*	`conf`	(1+epsilon, beta)-spanner constructions for general graphs. STOC Michael Elkin, David Peleg
2001	B	`conf`	Approximating k-Spanner Problems for k>2. IPCO Michael Elkin, David Peleg
2001	A*	`conf`	Computing almost shortest paths. PODC Michael Elkin
2001	B	`conf`	The Client-Server 2-Spanner Problem with Applications to Network Design. SIROCCO Michael Elkin, David Peleg
2000	A*	`conf`	Strong Inapproximability of the Basic ICALP Michael Elkin, David Peleg
2000	A	`conf`	The Hardness of Approximating Spanner Problems. STACS Michael Elkin, David Peleg