Michael Elkin

Uri Goldenberg

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

2017

Terminal embeddings.

[BibT_eX]

[DOI]

Arnold Filtser

Theor. Comput. Sci., 2017

Locally-Iterative Distributed (Delta + 1)-Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models.

[BibT_eX]

[DOI]

Uri Goldenberg

CoRR, 2017

Linear-Size Hopsets with Small Hopbound, and Distributed Routing with Low Memory.

[BibT_eX]

[DOI]

CoRR, 2017

Deterministic Distributed (Delta + o(Delta))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity.

[BibT_eX]

[DOI]

Tzalik Maimon

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

2016

Synchronizers, Spanners.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Sparse Graph Spanners.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Low Stretch Spanning Trees.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Space-efficient path-reporting approximate distance oracles.

[BibT_eX]

[DOI]

Christian Wulff-Nilsen

Theor. Comput. Sci., 2016

Optimizing budget allocation for center and median points.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

Fast Constructions of Lightweight Spanners for General Graphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs.

[BibT_eX]

[DOI]

Seth Pettie

ACM Trans. Algorithms, 2016

The Locality of Distributed Symmetry Breaking.

[BibT_eX]

[DOI]

J. ACM, 2016

Deterministic Distributed (Delta + o(Δ))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity.

[BibT_eX]

[DOI]

Tzalik Maimon

CoRR, 2016

On Efficient Distributed Construction of Near Optimal Routing Schemes: Extended Abstract.

[BibT_eX]

[DOI]

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Distributed Strong Diameter Network Decomposition: Extended Abstract.

[BibT_eX]

[DOI]

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

2015

Light Spanners.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2015

Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones.

[BibT_eX]

[DOI]

SIAM J. Comput., 2015

Optimal Euclidean Spanners: Really Short, Thin, and Lanky.

[BibT_eX]

[DOI]

J. ACM, 2015

(2Δ - l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting.

[BibT_eX]

[DOI]

Seth Pettie

Hsin-Hao Su

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation - (Extended Abstract).

[BibT_eX]

[DOI]

Cyril Gavoille

Proceedings of the Structural Information and Communication Complexity, 2015

2014

Balancing Degree, Diameter, and Weight in Euclidean Spanners.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2014

Distributed (Delta+1)-Coloring in Linear (in Delta) Time.

[BibT_eX]

[DOI]

Fabian Kuhn

SIAM J. Comput., 2014

Combinatorial algorithms for distributed graph coloring.

[BibT_eX]

[DOI]

Distributed Comput., 2014

Optimizing Budget Allocation in Graphs.

[BibT_eX]

[DOI]

CoRR, 2014

Can quantum communication speed up distributed computation?

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

2013

Distributed Graph Coloring: Fundamentals and Recent Developments

[BibT_eX]

[DOI]

Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool Publishers, ISBN: 978-3-031-02009-4, 2013

Symmetry breaking depending on the chromatic number or the neighborhood growth.

[BibT_eX]

[DOI]

Johannes Schneider

Roger Wattenhofer

Theor. Comput. Sci., 2013

Distributed deterministic edge coloring using bounded neighborhood independence.

[BibT_eX]

[DOI]

Distributed Comput., 2013

Fast Constructions of Light-Weight Spanners for General Graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

Quantum Distributed Network Computing: Lower Bounds and Techniques

[BibT_eX]

[DOI]

CoRR, 2012

Fast Distributed Algorithms for Maximal Matching and Maximal Independent Set

[BibT_eX]

[DOI]

CoRR, 2012

2011

Novel algorithms for the network lifetime problem in wireless settings.

[BibT_eX]

[DOI]

Wirel. Networks, 2011

Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2011

Narrow-Shallow-Low-Light Trees with and without Steiner Points.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2011

Deterministic Distributed Vertex Coloring in Polylogarithmic Time.

[BibT_eX]

[DOI]

J. ACM, 2011

Optimizing Budget Allocation in Graphs.

[BibT_eX]

[DOI]

Boaz Ben-Moshe

Eran Omri

Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

2010

Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners.

[BibT_eX]

[DOI]

Yefim Dinitz

Discret. Comput. Geom., 2010

Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition.

[BibT_eX]

[DOI]

Distributed Comput., 2010

An Improved Construction of Progression-Free Sets.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009

Distributed (delta+1)-coloring in linear (in delta) time.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

2008

Synchronizers, Spanners.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Sparse Graph Spanners.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Low Stretch Spanning Trees.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Lower-Stretch Spanning Trees.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

Bounds on the performance of back-to-front airplane boarding policies.

[BibT_eX]

[DOI]

Eitan Bachmat

Oper. Res. Lett., 2008

Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners

[BibT_eX]

[DOI]

Yefim Dinitz

CoRR, 2008

Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners.

[BibT_eX]

[DOI]

Yefim Dinitz

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

An improved algorithm for radio broadcast.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2007

The Hardness of Approximating Spanner Problems.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2007

New length bounds for cycle bases.

[BibT_eX]

[DOI]

Christian Liebchen

Romeo Rizzi

Inf. Process. Lett., 2007

A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, 2007

2006

Sparse Sourcewise and Pairwise Distance Preservers.

[BibT_eX]

[DOI]

Don Coppersmith

SIAM J. Discret. Math., 2006

An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 2006

Sublogarithmic approximation for telephone multicast.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2006

A faster distributed protocol for constructing a minimum spanning tree.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2006

Efficient algorithms for constructing (1+epsilon, beta)-spanners in the distributed and streaming models.

[BibT_eX]

[DOI]

Jian Zhang

Distributed Comput., 2006

A near-optimal fully dynamic distributed algorithm for maintaining sparse spanners

[BibT_eX]

[DOI]

CoRR, 2006

An Approximation Algorithm for the Directed Telephone Multicast Problem.

[BibT_eX]

[DOI]

Algorithmica, 2006

2005

Approximating k-spanner problems for kge2.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

Computing almost shortest paths.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2005

Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2005

Sparse Distance Preservers and Additive Spanners.

[BibT_eX]

[DOI]

Béla Bollobás

Don Coppersmith

SIAM J. Discret. Math., 2005

A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

Improved schedule for radio broadcast.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Sparse source-wise and pair-wise distance preservers.

[BibT_eX]

[DOI]

Don Coppersmith

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004

Distributed approximation: a survey.

[BibT_eX]

[DOI]

SIGACT News, 2004

(1+epsilon, beta)-Spanner Constructions for General Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2004

Logarithmic inapproximability of the radio broadcast problem.

[BibT_eX]

[DOI]

J. Algorithms, 2004

Lower-Stretch Spanning Trees

[BibT_eX]

[DOI]

Daniel A. Spielman

Shang-Hua Teng

CoRR, 2004

Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Efficient algorithms for constructing (1+, varepsilon;, beta)-spanners in the distributed and streaming models.

[BibT_eX]

[DOI]

Jian Zhang

Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

Polylogarithmic Inapproximability of the Radio Broadcast Problem.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2004

2003

Sublogarithmic approximation for telephone multicast: path out of jungle.

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Approximation Algorithm for Directed Telephone Multicast Problem.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

2001

The Client-Server 2-Spanner Problem with Applications to Network Design.

[BibT_eX]

Proceedings of the SIROCCO 8, 2001

Approximating k-Spanner Problems for k>2.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2001

2000

Strong Inapproximability of the Basic k-Spanner Problem.

[BibT_eX]

[DOI]