default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDMichael Elkin
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[i45]Michael Elkin, Chhaya Trehan:
Faster Multi-Source Directed Reachability via Shortcuts and Matrix Multiplication. CoRR abs/2401.05628 (2024)- [i44]Michael Elkin, Ariel Khuzman:
Deterministic Simple (1+°)Δ-Edge-Coloring in Near-Linear Time. CoRR abs/2401.10538 (2024) - 2023
- [j54]Michael Elkin, Yuval Gitlitz, Ofer Neiman:
Improved weighted additive spanners. Distributed Comput. 36(3): 385-394 (2023) - [c67]Michael Elkin, Idan Shabat:
Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n log log n). FOCS 2023: 2278-2311 - [i43]Michael Elkin, Idan Shabat:
Path-Reporting Distance Oracles with Near-Logarithmic Stretch and Linear Size. CoRR abs/2304.04445 (2023) - 2022
- [j53]Michael Elkin, Ofer Neiman
:
Linear-Size hopsets with small hopbound, and constant-hopbound hopsets in RNC. Distributed Comput. 35(5): 419-437 (2022) - [j52]Leonid Barenboim, Michael Elkin, Uri Goldenberg:
Locally-iterative Distributed (Δ + 1)-coloring and Applications. J. ACM 69(1): 5:1-5:26 (2022) - [j51]Michael Elkin, Ofer Neiman:
Lossless Prioritized Embeddings. SIAM J. Discret. Math. 36(3): 1529-1550 (2022) - [j50]Michael Elkin, Ofer Neiman:
Distributed strong diameter network decomposition. Theor. Comput. Sci. 922: 150-157 (2022) - [c66]Michael Elkin, Chhaya Trehan:
(1+ε)-Approximate Shortest Paths in Dynamic Streams. APPROX/RANDOM 2022: 51:1-51:23 - [c65]Václav Rozhon, Michael Elkin, Christoph Grunau, Bernhard Haeupler:
Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications. FOCS 2022: 1114-1121 - [c64]Michael Elkin, Chhaya Trehan:
Brief Announcement: (1+ε)-Approximate Shortest Paths in Dynamic Streams. PODC 2022: 57-59 - [c63]Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon:
Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates. SPAA 2022: 1-10 - [c62]Michael Elkin, Ofer Neiman:
Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication. STACS 2022: 27:1-27:22 - [c61]Michael Elkin, Yuval Gitlitz, Ofer Neiman:
Almost Shortest Paths with Near-Additive Error in Weighted Graphs. SWAT 2022: 23:1-23:22 - [i42]Michael Elkin, Bernhard Haeupler, Václav Rozhon, Christoph Grunau:
Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications. CoRR abs/2204.08254 (2022) - [i41]Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon:
Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates. CoRR abs/2204.14086 (2022) - 2021
- [j49]Michael Elkin, Ofer Neiman:
Near Isometric Terminal Embeddings for Doubling Metrics. Algorithmica 83(11): 3319-3337 (2021) - [c60]Michael Elkin, Shaked Matar:
Ultra-Sparse Near-Additive Emulators. PODC 2021: 235-246 - [c59]Michael Elkin, Shaked Matar:
Deterministic PRAM Approximate Shortest Paths in Polylogarithmic Time and Slightly Super-Linear Work. SPAA 2021: 198-207 - [c58]Michael Elkin, Yuval Gitlitz, Ofer Neiman:
Improved Weighted Additive Spanners. DISC 2021: 21:1-21:15 - [i40]Michael Elkin, Shaked Matar:
Ultra-Sparse Near-Additive Emulators. CoRR abs/2106.01036 (2021) - [i39]Michael Elkin, Chhaya Trehan:
$(1+ε)$-Approximate Shortest Paths in Dynamic Streams. CoRR abs/2107.13309 (2021) - 2020
- [j48]Michael Elkin, Ofer Neiman:
Near-Additive Spanners and Near-Exact Hopsets, A Unified View. Bull. EATCS 130 (2020) - [j47]Michael Elkin:
A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities. J. ACM 67(2): 13:1-13:15 (2020) - [j46]Michael Elkin:
Distributed Exact Shortest Paths in Sublinear Time. J. ACM 67(3): 15:1-15:36 (2020) - [j45]Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, Ofer Neiman:
Ramsey Spanning Trees and Their Applications. ACM Trans. Algorithms 16(2): 19:1-19:21 (2020) - [c57]Michael Elkin, Arnold Filtser, Ofer Neiman:
Distributed Construction of Light Networks. PODC 2020: 483-492 - [c56]Michael Elkin, Ofer Neiman:
Lossless Prioritized Embeddings. SODA 2020: 1049-1062 - [i38]Michael Elkin, Ofer Neiman:
Near-Additive Spanners and Near-Exact Hopsets, A Unified View. CoRR abs/2001.07477 (2020) - [i37]Michael Elkin, Ofer Neiman:
Centralized and Parallel Multi-Source Shortest Paths via Hopsets and Fast Matrix Multiplication. CoRR abs/2004.07572 (2020) - [i36]Michael Elkin, Yuval Gitlitz, Ofer Neiman:
Improved Weighted Additive Spanners. CoRR abs/2008.09877 (2020) - [i35]Michael Elkin, Shaked Matar:
Deterministic PRAM Approximate Shortest Paths in Polylogarithmic Time and Slightly Super-Linear Work. CoRR abs/2009.14729 (2020)
2010 – 2019
- 2019
- [j44]Michael Elkin, Ofer Neiman:
Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. SIAM J. Comput. 48(4): 1436-1480 (2019) - [j43]Michael Elkin, Ofer Neiman:
Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. ACM Trans. Algorithms 15(1): 4:1-4:29 (2019) - [c55]Michael Elkin, Shaked Matar:
Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time. PODC 2019: 531-540 - [c54]Michael Elkin, Ofer Neiman:
Linear-Size Hopsets with Small Hopbound, and Constant-Hopbound Hopsets in RNC. SPAA 2019: 333-341 - [i34]Michael Elkin, Shaked Matar:
Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time. CoRR abs/1903.00872 (2019) - [i33]Michael Elkin, Arnold Filtser, Ofer Neiman:
Distributed Construction of Light Networks. CoRR abs/1905.02592 (2019) - [i32]Michael Elkin, Ofer Neiman:
Lossless Prioritized Embeddings. CoRR abs/1907.06983 (2019) - [i31]Michael Elkin, Shaked Matar:
Fast Deterministic Constructions of Linear-Size Spanners and Skeletons. CoRR abs/1907.10895 (2019) - [i30]Michael Elkin, Yuval Gitlitz, Ofer Neiman:
Almost Shortest Paths and PRAM Distance Oracles in Weighted Graphs. CoRR abs/1907.11422 (2019) - 2018
- [j42]Michael Elkin, Ofer Neiman:
On efficient distributed construction of near optimal routing schemes. Distributed Comput. 31(2): 119-137 (2018) - [j41]Michael Elkin, Arnold Filtser, Ofer Neiman:
Prioritized Metric Structures and Embedding. SIAM J. Comput. 47(3): 829-858 (2018) - [j40]Leonid Barenboim, Michael Elkin, Cyril Gavoille:
A fast network-decomposition algorithm and its applications to constant-time distributed computation. Theor. Comput. Sci. 751: 2-23 (2018) - [c53]Michael Elkin, Ofer Neiman:
Near Isometric Terminal Embeddings for Doubling Metrics. SoCG 2018: 36:1-36:15 - [c52]Leonid Barenboim, Michael Elkin, Uri Goldenberg:
Locally-Iterative Distributed (Δ+ 1): -Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models. PODC 2018: 437-446 - [c51]Michael Elkin:
Session details: Session 3D: Graphs and Population. PODC 2018 - [c50]Michael Elkin, Ofer Neiman:
Near-Optimal Distributed Routing with Low Memory. PODC 2018: 207-216 - [c49]Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, Ofer Neiman:
Ramsey Spanning Trees and their Applications. SODA 2018: 1650-1664 - [i29]Michael Elkin, Ofer Neiman:
Near Isometric Terminal Embeddings for Doubling Metrics. CoRR abs/1802.07967 (2018) - 2017
- [j39]Michael Elkin, Arnold Filtser, Ofer Neiman:
Terminal embeddings. Theor. Comput. Sci. 697: 1-36 (2017) - [c48]Michael Elkin:
A Simple Deterministic Distributed MST Algorithm, with Near-Optimal Time and Message Complexities. PODC 2017: 157-163 - [c47]Leonid Barenboim, Michael Elkin, Tzalik Maimon:
Deterministic Distributed (Delta + o(Delta))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity. PODC 2017: 175-184 - [c46]Michael Elkin, Ofer Neiman:
Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. SODA 2017: 652-669 - [c45]Michael Elkin:
Distributed exact shortest paths in sublinear time. STOC 2017: 757-770 - [i28]Michael Elkin:
Distributed Exact Shortest Paths in Sublinear Time. CoRR abs/1703.01939 (2017) - [i27]Michael Elkin:
A Simple Deterministic Distributed MST Algorithm, with Near-Optimal Time and Message Complexities. CoRR abs/1703.02411 (2017) - [i26]Michael Elkin, Ofer Neiman:
Linear-Size Hopsets with Small Hopbound, and Distributed Routing with Low Memory. CoRR abs/1704.08468 (2017) - [i25]Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, Ofer Neiman:
Ramsey Spanning Trees and their Applications. CoRR abs/1707.08769 (2017) - [i24]Leonid Barenboim, Michael Elkin, Uri Goldenberg:
Locally-Iterative Distributed (Delta + 1)-Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models. CoRR abs/1712.00285 (2017) - 2016
- [j38]Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider:
The Locality of Distributed Symmetry Breaking. J. ACM 63(3): 20:1-20:45 (2016) - [j37]Michael Elkin, Shay Solomon:
Fast Constructions of Lightweight Spanners for General Graphs. ACM Trans. Algorithms 12(3): 29:1-29:21 (2016) - [j36]Michael Elkin, Seth Pettie:
A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. ACM Trans. Algorithms 12(4): 50:1-50:31 (2016) - [j35]Boaz Ben-Moshe, Michael Elkin, Lee-Ad Gottlieb, Eran Omri:
Optimizing budget allocation for center and median points. Theor. Comput. Sci. 627: 13-25 (2016) - [j34]Michael Elkin, Ofer Neiman, Christian Wulff-Nilsen:
Space-efficient path-reporting approximate distance oracles. Theor. Comput. Sci. 651: 1-10 (2016) - [c44]Michael Elkin, Ofer Neiman:
Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. FOCS 2016: 128-137 - [c43]Michael Elkin, Ofer Neiman:
Distributed Strong Diameter Network Decomposition: Extended Abstract. PODC 2016: 211-216 - [c42]Michael Elkin, Ofer Neiman:
On Efficient Distributed Construction of Near Optimal Routing Schemes: Extended Abstract. PODC 2016: 235-244 - [r6]Michael Elkin:
Low Stretch Spanning Trees. Encyclopedia of Algorithms 2016: 1156-1159 - [r5]Michael Elkin:
Sparse Graph Spanners. Encyclopedia of Algorithms 2016: 2041-2043 - [r4]Michael Elkin:
Synchronizers, Spanners. Encyclopedia of Algorithms 2016: 2189-2191 - [i23]Michael Elkin, Ofer Neiman:
On Efficient Distributed Construction of Near Optimal Routing Schemes. CoRR abs/1602.02293 (2016) - [i22]Michael Elkin, Ofer Neiman:
Distributed Strong Diameter Network Decomposition. CoRR abs/1602.05437 (2016) - [i21]Michael Elkin, Arnold Filtser, Ofer Neiman:
Terminal Embeddings. CoRR abs/1603.02321 (2016) - [i20]Michael Elkin, Ofer Neiman:
Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. CoRR abs/1605.04538 (2016) - [i19]Michael Elkin, Ofer Neiman:
Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. CoRR abs/1607.08337 (2016) - [i18]Leonid Barenboim, Michael Elkin, Tzalik Maimon:
Deterministic Distributed (Delta + o(Δ))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity. CoRR abs/1610.06759 (2016) - 2015
- [j33]Michael Elkin, Shay Solomon:
Optimal Euclidean Spanners: Really Short, Thin, and Lanky. J. ACM 62(5): 35:1-35:45 (2015) - [j32]Michael Elkin, Shay Solomon:
Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones. SIAM J. Comput. 44(4): 996-1025 (2015) - [j31]Michael Elkin, Ofer Neiman, Shay Solomon:
Light Spanners. SIAM J. Discret. Math. 29(3): 1312-1321 (2015) - [c41]Michael Elkin, Arnold Filtser, Ofer Neiman:
Terminal Embeddings. APPROX-RANDOM 2015: 242-264 - [c40]Leonid Barenboim, Michael Elkin, Cyril Gavoille:
A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation - (Extended Abstract). SIROCCO 2015: 209-223 - [c39]Michael Elkin, Seth Pettie, Hsin-Hao Su:
(2Δ - l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting. SODA 2015: 355-370 - [c38]Michael Elkin, Seth Pettie:
A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. SODA 2015: 805-821 - [c37]Michael Elkin, Arnold Filtser, Ofer Neiman:
Prioritized Metric Structures and Embedding. STOC 2015: 489-498 - [i17]Michael Elkin, Arnold Filtser, Ofer Neiman:
Prioritized Metric Structures and Embedding. CoRR abs/1502.05543 (2015) - [i16]Leonid Barenboim, Michael Elkin, Cyril Gavoille:
A Fast Network-Decomposition Algorithm and its Applications to Constant-Time Distributed Computation. CoRR abs/1505.05697 (2015) - [i15]Michael Elkin, Seth Pettie:
A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. CoRR abs/1506.08392 (2015) - 2014
- [j30]Leonid Barenboim, Michael Elkin:
Combinatorial algorithms for distributed graph coloring. Distributed Comput. 27(2): 79-93 (2014) - [j29]Leonid Barenboim, Michael Elkin, Fabian Kuhn:
Distributed (Delta+1)-Coloring in Linear (in Delta) Time. SIAM J. Comput. 43(1): 72-95 (2014) - [j28]Shay Solomon, Michael Elkin:
Balancing Degree, Diameter, and Weight in Euclidean Spanners. SIAM J. Discret. Math. 28(3): 1173-1198 (2014) - [c36]Michael Elkin, Ofer Neiman, Shay Solomon:
Light Spanners. ICALP (1) 2014: 442-452 - [c35]Michael Elkin, Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan:
Can quantum communication speed up distributed computation? PODC 2014: 166-175 - [i14]Michael Elkin, Ofer Neiman, Shay Solomon:
Light Spanners. CoRR abs/1404.7703 (2014) - [i13]Boaz Ben-Moshe, Michael Elkin, Lee-Ad Gottlieb, Eran Omri:
Optimizing Budget Allocation in Graphs. CoRR abs/1406.2107 (2014) - [i12]Michael Elkin, Ofer Neiman, Christian Wulff-Nilsen:
Space-Efficient Path-Reporting Approximate Distance Oracles. CoRR abs/1410.0768 (2014) - 2013
- [b1]Leonid Barenboim, Michael Elkin:
Distributed Graph Coloring: Fundamentals and Recent Developments. Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool Publishers 2013, ISBN 9781627050180, pp. 1-171 - [j27]Leonid Barenboim, Michael Elkin:
Distributed deterministic edge coloring using bounded neighborhood independence. Distributed Comput. 26(5-6): 273-287 (2013) - [j26]Johannes Schneider, Michael Elkin, Roger Wattenhofer:
Symmetry breaking depending on the chromatic number or the neighborhood growth. Theor. Comput. Sci. 509: 40-50 (2013) - [c34]Michael Elkin, Shay Solomon:
Fast Constructions of Light-Weight Spanners for General Graphs. SODA 2013: 513-525 - [c33]Michael Elkin, Shay Solomon:
Optimal euclidean spanners: really short, thin and lanky. STOC 2013: 645-654 - 2012
- [c32]Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider:
The Locality of Distributed Symmetry Breaking. FOCS 2012: 321-330 - [i11]Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider:
Fast Distributed Algorithms for Maximal Matching and Maximal Independent Set. CoRR abs/1202.1983 (2012) - [i10]Michael Elkin, Shay Solomon:
Fast Constructions of Light-Weight Spanners for General Graphs. CoRR abs/1207.1668 (2012) - [i9]Michael Elkin, Shay Solomon:
Optimal Euclidean spanners: really short, thin and lanky. CoRR abs/1207.1831 (2012) - [i8]Michael Elkin, Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan:
Quantum Distributed Network Computing: Lower Bounds and Techniques. CoRR abs/1207.5211 (2012) - 2011
- [j25]Leonid Barenboim, Michael Elkin:
Deterministic Distributed Vertex Coloring in Polylogarithmic Time. J. ACM 58(5): 23:1-23:25 (2011) - [j24]Michael Elkin, Shay Solomon:
Narrow-Shallow-Low-Light Trees with and without Steiner Points. SIAM J. Discret. Math. 25(1): 181-210 (2011) - [j23]Michael Elkin:
Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Trans. Algorithms 7(2): 20:1-20:17 (2011) - [j22]Michael Elkin, Yuval Lando, Zeev Nutov, Michael Segal, Hanan Shpungin:
Novel algorithms for the network lifetime problem in wireless settings. Wirel. Networks 17(2): 397-410 (2011) - [c31]Boaz Ben-Moshe, Eran Omri, Michael Elkin:
Optimizing Budget Allocation in Graphs. CCCG 2011 - [c30]Michael Elkin, Shay Solomon:
Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones. FOCS 2011: 373-382 - [c29]Leonid Barenboim, Michael Elkin:
Distributed deterministic edge coloring using bounded neighborhood independence. PODC 2011: 129-138 - [c28]Leonid Barenboim, Michael Elkin:
Combinatorial Algorithms for Distributed Graph Coloring. DISC 2011: 66-81 - [i7]Shay Solomon, Michael Elkin:
Balancing Degree, Diameter and Weight in Euclidean Spanners. CoRR abs/1108.6022 (2011) - 2010
- [j21]Leonid Barenboim, Michael Elkin:
Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. Distributed Comput. 22(5-6): 363-379 (2010) - [j20]Yefim Dinitz, Michael Elkin, Shay Solomon:
Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners. Discret. Comput. Geom. 43(4): 736-783 (2010) - [c27]Shay Solomon, Michael Elkin:
Balancing Degree, Diameter and Weight in Euclidean Spanners. ESA (1) 2010: 48-59 - [c26]Leonid Barenboim, Michael Elkin:
Deterministic distributed vertex coloring in polylogarithmic time. PODC 2010: 410-419 - [c25]Michael Elkin:
An Improved Construction of Progression-Free Sets. SODA 2010: 886-905 - [i6]Leonid Barenboim, Michael Elkin:
Deterministic Distributed Vertex Coloring in Polylogarithmic Time. CoRR abs/1003.1608 (2010) - [i5]Leonid Barenboim, Michael Elkin:
Distributed Deterministic Edge Coloring using Bounded Neighborhood Independence. CoRR abs/1010.2454 (2010)
2000 – 2009
- 2009
- [c24]Michael Elkin, Shay Solomon:
Narrow-Shallow-Low-Light Trees with and without Steiner Points. ESA 2009: 215-226 - [c23]Leonid Barenboim, Michael Elkin:
Distributed (delta+1)-coloring in linear (in delta) time. STOC 2009: 111-120 - 2008
- [j19]Eitan Bachmat, Michael Elkin:
Bounds on the performance of back-to-front airplane boarding policies. Oper. Res. Lett. 36(5): 597-601 (2008) - [j18]Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng:
Lower-Stretch Spanning Trees. SIAM J. Comput. 38(2): 608-628 (2008) - [c22]Michael Elkin, Yuval Lando, Zeev Nutov, Michael Segal, Hanan Shpungin:
Novel Algorithms for the Network Lifetime Problem in Wireless Settings. ADHOC-NOW 2008: 425-438 - [c21]Yefim Dinitz, Michael Elkin, Shay Solomon:
Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners. FOCS 2008: 519-528 - [c20]Leonid Barenboim, Michael Elkin:
Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition. PODC 2008: 25-34 - [r3]Michael Elkin:
Low Stretch Spanning Trees. Encyclopedia of Algorithms 2008 - [r2]Michael Elkin:
Sparse Graph Spanners. Encyclopedia of Algorithms 2008 - [r1]Michael Elkin:
Synchronizers, Spanners. Encyclopedia of Algorithms 2008 - [i4]Yefim Dinitz, Michael Elkin, Shay Solomon:
Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners. CoRR abs/0801.3581 (2008) - [i3]Leonid Barenboim, Michael Elkin:
Distributed (Delta + 1)-coloring in linear (in Delta) time. CoRR abs/0812.1379 (2008) - 2007
- [j17]Michael Elkin, Christian Liebchen, Romeo Rizzi:
New length bounds for cycle bases. Inf. Process. Lett. 104(5): 186-193 (2007) - [j16]Michael Elkin, David Peleg:
The Hardness of Approximating Spanner Problems. Theory Comput. Syst. 41(4): 691-729 (2007) - [j15]Michael Elkin, Guy Kortsarz:
An improved algorithm for radio broadcast. ACM Trans. Algorithms 3(1): 8:1-8:21 (2007) - [c19]Michael Elkin:
Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners. ICALP 2007: 716-727 - [c18]Michael Elkin:
A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners. PODC 2007: 185-194 - 2006
- [j14]Michael Elkin, Guy Kortsarz:
An Approximation Algorithm for the Directed Telephone Multicast Problem. Algorithmica 45(4): 569-583 (2006) - [j13]Michael Elkin, Jian Zhang:
Efficient algorithms for constructing (1+epsilon, beta)-spanners in the distributed and streaming models. Distributed Comput. 18(5): 375-385 (2006) - [j12]Michael Elkin, Guy Kortsarz:
Sublogarithmic approximation for telephone multicast. J. Comput. Syst. Sci. 72(4): 648-659 (2006) - [j11]Michael Elkin:
A faster distributed protocol for constructing a minimum spanning tree. J. Comput. Syst. Sci. 72(8): 1282-1308 (2006) - [j10]Michael Elkin:
An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem. SIAM J. Comput. 36(2): 433-456 (2006) - [j9]Don Coppersmith, Michael Elkin:
Sparse Sourcewise and Pairwise Distance Preservers. SIAM J. Discret. Math. 20(2): 463-501 (2006) - [i2]Michael Elkin:
A near-optimal fully dynamic distributed algorithm for maintaining sparse spanners. CoRR abs/cs/0611001 (2006) - 2005
- [j8]Michael Elkin, Guy Kortsarz:
A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem. SIAM J. Comput. 35(3): 672-689 (2005) - [j7]Michael Elkin, Guy Kortsarz:
Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem. SIAM J. Discret. Math. 19(4): 881-899 (2005) - [j6]Béla Bollobás, Don Coppersmith, Michael Elkin:
Sparse Distance Preservers and Additive Spanners. SIAM J. Discret. Math. 19(4): 1029-1055 (2005) - [j5]Michael Elkin:
Computing almost shortest paths. ACM Trans. Algorithms 1(2): 283-323 (2005) - [j4]Michael Elkin, David Peleg:
Approximating k-spanner problems for kge2. Theor. Comput. Sci. 337(1-3): 249-277 (2005) - [c17]Michael Elkin, Guy Kortsarz:
Improved schedule for radio broadcast. SODA 2005: 222-231 - [c16]Don Coppersmith, Michael Elkin:
Sparse source-wise and pair-wise distance preservers. SODA 2005: 660-669 - [c15]Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng:
Lower-stretch spanning trees. STOC 2005: 494-503 - 2004
- [j3]Michael Elkin, Guy Kortsarz:
Logarithmic inapproximability of the radio broadcast problem. J. Algorithms 52(1): 8-25 (2004) - [j2]Michael Elkin, David Peleg:
(1+epsilon, beta)-Spanner Constructions for General Graphs. SIAM J. Comput. 33(3): 608-631 (2004) - [j1]Michael Elkin:
Distributed approximation: a survey. SIGACT News 35(4): 40-57 (2004) - [c14]Michael Elkin, Guy Kortsarz:
Polylogarithmic Inapproximability of the Radio Broadcast Problem. APPROX-RANDOM 2004: 105-116 - [c13]Michael Elkin, Jian Zhang:
Efficient algorithms for constructing (1+, varepsilon;, beta)-spanners in the distributed and streaming models. PODC 2004: 160-168 - [c12]Michael Elkin:
A faster distributed protocol for constructing a minimum spanning tree. SODA 2004: 359-368 - [c11]Michael Elkin:
Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. STOC 2004: 331-340 - [i1]Michael Elkin, Daniel A. Spielman, Shang-Hua Teng:
Lower-Stretch Spanning Trees. CoRR cs.DS/0411064 (2004) - 2003
- [c10]Michael Elkin, Guy Kortsarz:
Approximation Algorithm for Directed Telephone Multicast Problem. ICALP 2003: 212-223 - [c9]Michael Elkin, Guy Kortsarz:
Sublogarithmic approximation for telephone multicast: path out of jungle. SODA 2003: 76-85 - [c8]Béla Bollobás, Don Coppersmith, Michael Elkin:
Sparse distance preservers and additive spanners. SODA 2003: 414-423 - 2002
- [c7]Michael Elkin, Guy Kortsarz:
Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem. STOC 2002: 438-447 - 2001
- [c6]Michael Elkin, David Peleg:
Approximating k-Spanner Problems for k>2. IPCO 2001: 90-104 - [c5]Michael Elkin:
Computing almost shortest paths. PODC 2001: 53-62 - [c4]Michael Elkin, David Peleg:
The Client-Server 2-Spanner Problem with Applications to Network Design. SIROCCO 2001: 117-132 - [c3]Michael Elkin, David Peleg:
(1+epsilon, beta)-spanner constructions for general graphs. STOC 2001: 173-182 - 2000
- [c2]Michael Elkin, David Peleg:
Strong Inapproximability of the Basic k-Spanner Problem. ICALP 2000: 636-647 - [c1]Michael Elkin, David Peleg:
The Hardness of Approximating Spanner Problems. STACS 2000: 370-381
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-01-21 00:00 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
