Michael Elkin

Uri Goldenberg

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

Near Isometric Terminal Embeddings for Doubling Metrics.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Computational Geometry, 2018

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

Distributed exact shortest paths in sublinear time.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Efficient Algorithms for Constructing Very Sparse Spanners and Emulators.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

A Simple Deterministic Distributed MST Algorithm, with Near-Optimal Time and Message Complexities.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 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

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

Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Prioritized Metric Structures and Embedding.

[BibT_eX]

[DOI]

Arnold Filtser

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 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 Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs.

[BibT_eX]

[DOI]

Seth Pettie

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

Terminal Embeddings.

[BibT_eX]

[DOI]

Arnold Filtser

Proceedings of the Approximation, 2015

2014

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

[BibT_eX]

[DOI]

Fabian Kuhn

SIAM J. 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

Light Spanners.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 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

Optimal euclidean spanners: really short, thin and lanky.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 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

The Locality of Distributed Symmetry Breaking.

[BibT_eX]

[DOI]

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

Combinatorial Algorithms for Distributed Graph Coloring.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 25th International Symposium, 2011

Distributed deterministic edge coloring using bounded neighborhood independence.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

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

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 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

An Improved Construction of Progression-Free Sets.

[BibT_eX]

[DOI]

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

Deterministic distributed vertex coloring in polylogarithmic time.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

Balancing Degree, Diameter and Weight in Euclidean Spanners.

[BibT_eX]

[DOI]

Proceedings of the 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

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

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 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

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

Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, 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

Novel Algorithms for the Network Lifetime Problem in Wireless Settings.

[BibT_eX]

[DOI]

Proceedings of the Ad-hoc, Mobile and Wireless Networks, 7th International Conference, 2008

2007

An improved algorithm for radio broadcast.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 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

Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 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

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

Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2005

Lower-stretch spanning trees.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 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

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

A faster distributed protocol for constructing a minimum spanning tree.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

Sparse distance preservers and additive spanners.

[BibT_eX]

[DOI]

Béla Bollobás

Don Coppersmith

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

2002

Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

2001

(1+epsilon, beta)-spanner constructions for general graphs.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

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

[BibT_eX]

Proceedings of the SIROCCO 8, 2001

Computing almost shortest paths.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing, 2001

Approximating k-Spanner Problems for k>2.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2001

2000

The Hardness of Approximating Spanner Problems.

[BibT_eX]

[DOI]

Proceedings of the STACS 2000, 2000

Strong Inapproximability of the Basic k-Spanner Problem.

[BibT_eX]

[DOI]