| 2008 |
|---|
| 48 | EE | 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 |
| 47 | EE | Yefim Dinitz,
Michael Elkin,
Shay Solomon:
Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners.
FOCS 2008: 519-528 |
| 46 | EE | Leonid Barenboim,
Michael Elkin:
Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition.
PODC 2008: 25-34 |
| 45 | EE | Michael Elkin:
Low Stretch Spanning Trees.
Encyclopedia of Algorithms 2008 |
| 44 | EE | Michael Elkin:
Sparse Graph Spanners.
Encyclopedia of Algorithms 2008 |
| 43 | EE | Michael Elkin:
Synchronizers, Spanners.
Encyclopedia of Algorithms 2008 |
| 42 | EE | Yefim Dinitz,
Michael Elkin,
Shay Solomon:
Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners
CoRR abs/0801.3581: (2008) |
| 41 | EE | Leonid Barenboim,
Michael Elkin:
Distributed (Delta + 1)-coloring in linear (in Delta) time
CoRR abs/0812.1379: (2008) |
| 40 | EE | Eitan Bachmat,
Michael Elkin:
Bounds on the performance of back-to-front airplane boarding policies.
Oper. Res. Lett. 36(5): 597-601 (2008) |
| 39 | EE | Michael Elkin,
Yuval Emek,
Daniel A. Spielman,
Shang-Hua Teng:
Lower-Stretch Spanning Trees.
SIAM J. Comput. 38(2): 608-628 (2008) |
| 2007 |
|---|
| 38 | EE | Michael Elkin:
Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners.
ICALP 2007: 716-727 |
| 37 | EE | Michael Elkin:
A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners.
PODC 2007: 185-194 |
| 36 | EE | Michael Elkin,
Guy Kortsarz:
An improved algorithm for radio broadcast.
ACM Transactions on Algorithms 3(1): (2007) |
| 35 | EE | Michael Elkin,
Christian Liebchen,
Romeo Rizzi:
New length bounds for cycle bases.
Inf. Process. Lett. 104(5): 186-193 (2007) |
| 34 | EE | Michael Elkin,
David Peleg:
The Hardness of Approximating Spanner Problems.
Theory Comput. Syst. 41(4): 691-729 (2007) |
| 2006 |
|---|
| 33 | EE | Michael Elkin,
Guy Kortsarz:
An Approximation Algorithm for the Directed Telephone Multicast Problem.
Algorithmica 45(4): 569-583 (2006) |
| 32 | EE | Michael Elkin:
A near-optimal fully dynamic distributed algorithm for maintaining sparse spanners
CoRR abs/cs/0611001: (2006) |
| 31 | 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) |
| 30 | EE | Michael Elkin,
Guy Kortsarz:
Sublogarithmic approximation for telephone multicast.
J. Comput. Syst. Sci. 72(4): 648-659 (2006) |
| 29 | EE | Michael Elkin:
A faster distributed protocol for constructing a minimum spanning tree.
J. Comput. Syst. Sci. 72(8): 1282-1308 (2006) |
| 28 | 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) |
| 27 | EE | Don Coppersmith,
Michael Elkin:
Sparse Sourcewise and Pairwise Distance Preservers.
SIAM J. Discrete Math. 20(2): 463-501 (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 |
