Michael Elkin

2008
38	EE	Yefim Dinitz, Michael Elkin, Shay Solomon: Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners CoRR abs/0801.3581: (2008)
2007
37	EE	Michael Elkin: Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners. ICALP 2007: 716-727
36	EE	Michael Elkin: A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners. PODC 2007: 185-194
35	EE	Michael Elkin, Guy Kortsarz: An improved algorithm for radio broadcast. ACM Transactions on Algorithms 3(1): (2007)
34	EE	Michael Elkin, Christian Liebchen, Romeo Rizzi: New length bounds for cycle bases. Inf. Process. Lett. 104(5): 186-193 (2007)
33	EE	Michael Elkin, David Peleg: The Hardness of Approximating Spanner Problems. Theory Comput. Syst. 41(4): 691-729 (2007)
2006
32	EE	Michael Elkin, Guy Kortsarz: An Approximation Algorithm for the Directed Telephone Multicast Problem. Algorithmica 45(4): 569-583 (2006)
31	EE	Michael Elkin: A near-optimal fully dynamic distributed algorithm for maintaining sparse spanners CoRR abs/cs/0611001: (2006)
30	EE	Michael Elkin, Jian Zhang: Efficient algorithms for constructing (1+epsilon, beta)-spanners in the distributed and streaming models. Distributed Computing 18(5): 375-385 (2006)
29	EE	Michael Elkin, Guy Kortsarz: Sublogarithmic approximation for telephone multicast. J. Comput. Syst. Sci. 72(4): 648-659 (2006)
28	EE	Michael Elkin: A faster distributed protocol for constructing a minimum spanning tree. J. Comput. Syst. Sci. 72(8): 1282-1308 (2006)
27	EE	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)
2005
26	EE	Michael Elkin, Guy Kortsarz: Improved schedule for radio broadcast. SODA 2005: 222-231
25	EE	Don Coppersmith, Michael Elkin: Sparse source-wise and pair-wise distance preservers. SODA 2005: 660-669
24	EE	Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng: Lower-stretch spanning trees. STOC 2005: 494-503
23	EE	Michael Elkin: Computing almost shortest paths. ACM Transactions on Algorithms 1(2): 283-323 (2005)
22	EE	Michael Elkin, Guy Kortsarz: A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem. SIAM J. Comput. 35(3): 672-689 (2005)
21	EE	Béla Bollobás, Don Coppersmith, Michael Elkin: Sparse Distance Preservers and Additive Spanners. SIAM J. Discrete Math. 19(4): 1029-1055 (2005)
20	EE	Michael Elkin, Guy Kortsarz: Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem. SIAM J. Discrete Math. 19(4): 881-899 (2005)
19	EE	Michael Elkin, David Peleg: Approximating k-spanner problems for kge2. Theor. Comput. Sci. 337(1-3): 249-277 (2005)
2004
18	EE	Michael Elkin, Guy Kortsarz: Polylogarithmic Inapproximability of the Radio Broadcast Problem. APPROX-RANDOM 2004: 105-116
17	EE	Michael Elkin, Jian Zhang: Efficient algorithms for constructing (1+, varepsilon;, beta)-spanners in the distributed and streaming models. PODC 2004: 160-168
16	EE	Michael Elkin: A faster distributed protocol for constructing a minimum spanning tree. SODA 2004: 359-368
15	EE	Michael Elkin: Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. STOC 2004: 331-340
14	EE	Michael Elkin, Daniel A. Spielman, Shang-Hua Teng: Lower-Stretch Spanning Trees CoRR cs.DS/0411064: (2004)
13	EE	Michael Elkin, Guy Kortsarz: Logarithmic inapproximability of the radio broadcast problem. J. Algorithms 52(1): 8-25 (2004)
12	EE	Michael Elkin, David Peleg: (1+epsilon, beta)-Spanner Constructions for General Graphs. SIAM J. Comput. 33(3): 608-631 (2004)
11	EE	Michael Elkin: Distributed approximation: a survey. SIGACT News 35(4): 40-57 (2004)
2003
10	EE	Michael Elkin, Guy Kortsarz: Approximation Algorithm for Directed Telephone Multicast Problem. ICALP 2003: 212-223
9	EE	Béla Bollobás, Don Coppersmith, Michael Elkin: Sparse distance preservers and additive spanners. SODA 2003: 414-423
8	EE	Michael Elkin, Guy Kortsarz: Sublogarithmic approximation for telephone multicast: path out of jungle. SODA 2003: 76-85
2002
7	EE	Michael Elkin, Guy Kortsarz: Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem. STOC 2002: 438-447
2001
6	EE	Michael Elkin, David Peleg: Approximating k-Spanner Problems for k>2. IPCO 2001: 90-104
5	EE	Michael Elkin: Computing almost shortest paths. PODC 2001: 53-62
4		Michael Elkin, David Peleg: The Client-Server 2-Spanner Problem with Applications to Network Design. SIROCCO 2001: 117-132
3	EE	Michael Elkin, David Peleg: (1+epsilon, beta)-spanner constructions for general graphs. STOC 2001: 173-182
2000
2	EE	Michael Elkin, David Peleg: Strong Inapproximability of the Basic k-Spanner Problem. ICALP 2000: 636-647
1	EE	Michael Elkin, David Peleg: The Hardness of Approximating Spanner Problems. STACS 2000: 370-381

Coauthor Index

1	Béla Bollobás	[9] [21]
2	Don Coppersmith	[9] [21] [25]
3	Yefim Dinitz	[38]
4	Yuval Emek	[24]
5	Guy Kortsarz	[7] [8] [10] [13] [18] [20] [22] [26] [29] [32] [35]
6	Christian Liebchen	[34]
7	David Peleg	[1] [2] [3] [4] [6] [12] [19] [33]
8	Romeo Rizzi	[34]
9	Shay Solomon	[38]
10	Daniel A. Spielman	[14] [24]
11	Shang-Hua Teng	[14] [24]
12	Jian Zhang	[17] [30]

Colors in the list of coauthors