 | 2012 |
|---|
| 67 |       | Leonid Barenboim,
Michael Elkin,
Seth Pettie,
Johannes Schneider:
Fast Distributed Algorithms for Maximal Matching and Maximal Independent Set
CoRR abs/1202.1983: (2012) |
| 2011 |
|---|
| 66 | | Boaz Ben-Moshe,
Eran Omri,
Michael Elkin:
Optimizing Budget Allocation in Graphs.
CCCG 2011 |
| 65 | | Leonid Barenboim,
Michael Elkin:
Combinatorial Algorithms for Distributed Graph Coloring.
DISC 2011: 66-81 |
| 64 | | Michael Elkin,
Shay Solomon:
Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones.
FOCS 2011: 373-382 |
| 63 | | Leonid Barenboim,
Michael Elkin:
Distributed deterministic edge coloring using bounded neighborhood independence.
PODC 2011: 129-138 |
| 62 | | Michael Elkin:
Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners.
ACM Transactions on Algorithms 7(2): 20 (2011) |
| 61 | | Shay Solomon,
Michael Elkin:
Balancing Degree, Diameter and Weight in Euclidean Spanners
CoRR abs/1108.6022: (2011) |
| 60 | | Leonid Barenboim,
Michael Elkin:
Deterministic Distributed Vertex Coloring in Polylogarithmic Time.
J. ACM 58(5): 23 (2011) |
| 59 | | Michael Elkin,
Shay Solomon:
Narrow-Shallow-Low-Light Trees with and without Steiner Points.
SIAM J. Discrete Math. 25(1): 181-210 (2011) |
| 58 | | Michael Elkin,
Yuval Lando,
Zeev Nutov,
Michael Segal,
Hanan Shpungin:
Novel algorithms for the network lifetime problem in wireless settings.
Wireless Networks 17(2): 397-410 (2011) |
| 2010 |
|---|
| 57 | | Shay Solomon,
Michael Elkin:
Balancing Degree, Diameter and Weight in Euclidean Spanners.
ESA (1) 2010: 48-59 |
| 56 | | Leonid Barenboim,
Michael Elkin:
Deterministic distributed vertex coloring in polylogarithmic time.
PODC 2010: 410-419 |
| 55 | | Michael Elkin:
An Improved Construction of Progression-Free Sets.
SODA 2010: 886-905 |
| 54 | | Leonid Barenboim,
Michael Elkin:
Deterministic Distributed Vertex Coloring in Polylogarithmic Time
CoRR abs/1003.1608: (2010) |
| 53 | | Leonid Barenboim,
Michael Elkin:
Distributed Deterministic Edge Coloring using Bounded Neighborhood Independence
CoRR abs/1010.2454: (2010) |
| 52 | | Yefim Dinitz,
Michael Elkin,
Shay Solomon:
Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners.
Discrete & Computational Geometry 43(4): 736-783 (2010) |
| 51 | | Leonid Barenboim,
Michael Elkin:
Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition.
Distributed Computing 22(5-6): 363-379 (2010) |
| 2009 |
|---|
| 50 | | Michael Elkin,
Shay Solomon:
Narrow-Shallow-Low-Light Trees with and without Steiner Points.
ESA 2009: 215-226 |
| 49 | | Leonid Barenboim,
Michael Elkin:
Distributed (delta+1)-coloring in linear (in delta) time.
STOC 2009: 111-120 |
| 2008 |
|---|
| 48 | | 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 | | Yefim Dinitz,
Michael Elkin,
Shay Solomon:
Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners.
FOCS 2008: 519-528 |
| 46 | | Leonid Barenboim,
Michael Elkin:
Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition.
PODC 2008: 25-34 |
| 45 | | Michael Elkin:
Low Stretch Spanning Trees.
Encyclopedia of Algorithms 2008 |
| 44 | | Michael Elkin:
Sparse Graph Spanners.
Encyclopedia of Algorithms 2008 |
| 43 | | Michael Elkin:
Synchronizers, Spanners.
Encyclopedia of Algorithms 2008 |
| 42 | | Yefim Dinitz,
Michael Elkin,
Shay Solomon:
Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners
CoRR abs/0801.3581: (2008) |
| 41 | | Leonid Barenboim,
Michael Elkin:
Distributed (Delta + 1)-coloring in linear (in Delta) time
CoRR abs/0812.1379: (2008) |
| 40 | | Eitan Bachmat,
Michael Elkin:
Bounds on the performance of back-to-front airplane boarding policies.
Oper. Res. Lett. 36(5): 597-601 (2008) |
| 39 | | Michael Elkin,
Yuval Emek,
Daniel A. Spielman,
Shang-Hua Teng:
Lower-Stretch Spanning Trees.
SIAM J. Comput. 38(2): 608-628 (2008) |
| 2007 |
|---|
| 38 | | Michael Elkin:
Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners.
ICALP 2007: 716-727 |
| 37 | | Michael Elkin:
A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners.
PODC 2007: 185-194 |
| 36 | | Michael Elkin,
Guy Kortsarz:
An improved algorithm for radio broadcast.
ACM Transactions on Algorithms 3(1): (2007) |
| 35 | | Michael Elkin,
Christian Liebchen,
Romeo Rizzi:
New length bounds for cycle bases.
Inf. Process. Lett. 104(5): 186-193 (2007) |
| 34 | | Michael Elkin,
David Peleg:
The Hardness of Approximating Spanner Problems.
Theory Comput. Syst. 41(4): 691-729 (2007) |
| 2006 |
|---|
| 33 | | Michael Elkin,
Guy Kortsarz:
An Approximation Algorithm for the Directed Telephone Multicast Problem.
Algorithmica 45(4): 569-583 (2006) |
| 32 | | Michael Elkin:
A near-optimal fully dynamic distributed algorithm for maintaining sparse spanners
CoRR abs/cs/0611001: (2006) |
| 31 | | 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 | | Michael Elkin,
Guy Kortsarz:
Sublogarithmic approximation for telephone multicast.
J. Comput. Syst. Sci. 72(4): 648-659 (2006) |
| 29 | | Michael Elkin:
A faster distributed protocol for constructing a minimum spanning tree.
J. Comput. Syst. Sci. 72(8): 1282-1308 (2006) |
| 28 | | 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 | | Don Coppersmith,
Michael Elkin:
Sparse Sourcewise and Pairwise Distance Preservers.
SIAM J. Discrete Math. 20(2): 463-501 (2006) |
| 2005 |
|---|
| 26 | | Michael Elkin,
Guy Kortsarz:
Improved schedule for radio broadcast.
SODA 2005: 222-231 |
| 25 | | Don Coppersmith,
Michael Elkin:
Sparse source-wise and pair-wise distance preservers.
SODA 2005: 660-669 |
| 24 | | Michael Elkin,
Yuval Emek,
Daniel A. Spielman,
Shang-Hua Teng:
Lower-stretch spanning trees.
STOC 2005: 494-503 |
| 23 | | Michael Elkin:
Computing almost shortest paths.
ACM Transactions on Algorithms 1(2): 283-323 (2005) |
| 22 | | Michael Elkin,
Guy Kortsarz:
A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem.
SIAM J. Comput. 35(3): 672-689 (2005) |
| 21 | | Béla Bollobás,
Don Coppersmith,
Michael Elkin:
Sparse Distance Preservers and Additive Spanners.
SIAM J. Discrete Math. 19(4): 1029-1055 (2005) |
| 20 | | Michael Elkin,
Guy Kortsarz:
Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem.
SIAM J. Discrete Math. 19(4): 881-899 (2005) |
| 19 | | Michael Elkin,
David Peleg:
Approximating k-spanner problems for kge2.
Theor. Comput. Sci. 337(1-3): 249-277 (2005) |
| 2004 |
|---|
| 18 | | Michael Elkin,
Guy Kortsarz:
Polylogarithmic Inapproximability of the Radio Broadcast Problem.
APPROX-RANDOM 2004: 105-116 |
| 17 | | Michael Elkin,
Jian Zhang:
Efficient algorithms for constructing (1+, varepsilon;, beta)-spanners in the distributed and streaming models.
PODC 2004: 160-168 |
| 16 | | Michael Elkin:
A faster distributed protocol for constructing a minimum spanning tree.
SODA 2004: 359-368 |
| 15 | | Michael Elkin:
Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem.
STOC 2004: 331-340 |
| 14 | | Michael Elkin,
Daniel A. Spielman,
Shang-Hua Teng:
Lower-Stretch Spanning Trees
CoRR cs.DS/0411064: (2004) |
| 13 | | Michael Elkin,
Guy Kortsarz:
Logarithmic inapproximability of the radio broadcast problem.
J. Algorithms 52(1): 8-25 (2004) |
| 12 | | Michael Elkin,
David Peleg:
(1+epsilon, beta)-Spanner Constructions for General Graphs.
SIAM J. Comput. 33(3): 608-631 (2004) |
| 11 | | Michael Elkin:
Distributed approximation: a survey.
SIGACT News 35(4): 40-57 (2004) |
| 2003 |
|---|
| 10 | | Michael Elkin,
Guy Kortsarz:
Approximation Algorithm for Directed Telephone Multicast Problem.
ICALP 2003: 212-223 |
| 9 | | Béla Bollobás,
Don Coppersmith,
Michael Elkin:
Sparse distance preservers and additive spanners.
SODA 2003: 414-423 |
| 8 | | Michael Elkin,
Guy Kortsarz:
Sublogarithmic approximation for telephone multicast: path out of jungle.
SODA 2003: 76-85 |
| 2002 |
|---|
| 7 | | Michael Elkin,
Guy Kortsarz:
Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem.
STOC 2002: 438-447 |
| 2001 |
|---|
| 6 | | Michael Elkin,
David Peleg:
Approximating k-Spanner Problems for k>2.
IPCO 2001: 90-104 |
| 5 | | 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 | | Michael Elkin,
David Peleg:
(1+epsilon, beta)-spanner constructions for general graphs.
STOC 2001: 173-182 |
| 2000 |
|---|
| 2 | | Michael Elkin,
David Peleg:
Strong Inapproximability of the Basic k-Spanner Problem.
ICALP 2000: 636-647 |
| 1 | | Michael Elkin,
David Peleg:
The Hardness of Approximating Spanner Problems.
STACS 2000: 370-381 |
Data released under the ODC-BY 1.0 license — See also our legal information page