| Publication | Date of Publication | Type |
|---|
| \((1+\varepsilon)\)-approximate shortest paths in dynamic streams | 2024-08-22 | Paper |
| Almost shortest paths with near-additive error in weighted graphs | 2024-05-27 | Paper |
| Centralized, parallel, and distributed multi-source shortest paths via hopsets and rectangular matrix multiplication | 2024-04-23 | Paper |
Ultra-Sparse Near-Additive Emulators
Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing | 2024-03-26 | Paper |
Brief Announcement: (1+ε)-Approximate Shortest Paths in Dynamic Streams.
Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing | 2024-03-26 | Paper |
Brief Announcement: (1+ε)-Approximate Shortest Paths in Dynamic Streams.
Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing | 2024-03-26 | Paper |
| scientific article; zbMATH DE number 7774272 (Why is no real title available?) | 2023-12-08 | Paper |
Improved weighted additive spanners
Distributed Computing | 2023-09-11 | Paper |
Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC
Distributed Computing | 2022-10-14 | Paper |
Lossless prioritized embeddings
SIAM Journal on Discrete Mathematics | 2022-07-13 | Paper |
Distributed strong diameter network decomposition
Theoretical Computer Science | 2022-06-13 | Paper |
Locally-iterative Distributed (Δ + 1)-coloring and Applications
Journal of the ACM | 2022-03-31 | Paper |
Near isometric terminal embeddings for doubling metrics
Algorithmica | 2021-11-19 | Paper |
| Near-additive spanners and near-exact hopsets, a unified view | 2021-08-30 | Paper |
Near-additive spanners and near-exact hopsets, a unified view
(available as arXiv preprint) | 2021-08-30 | Paper |
Ramsey spanning trees and their applications
ACM Transactions on Algorithms | 2021-05-03 | Paper |
Distributed Construction of Light Networks
Proceedings of the 39th Symposium on Principles of Distributed Computing | 2021-03-15 | Paper |
Lossless Prioritized Embeddings
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Near-additive spanners in low polynomial deterministic CONGEST time
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing | 2021-01-20 | Paper |
Distributed exact shortest paths in sublinear time
Journal of the ACM | 2020-11-11 | Paper |
A simple deterministic distributed MST algorithm with near-optimal time and message complexities
Journal of the ACM | 2020-11-11 | Paper |
Near isometric terminal embeddings for doubling metrics
(available as arXiv preprint) | 2020-08-18 | Paper |
Locally-iterative distributed \((\Delta+1)\)-coloring below Szegedy-Vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing | 2019-09-19 | Paper |
Near-optimal distributed routing with low memory
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing | 2019-09-19 | Paper |
Hopsets with constant hopbound, and applications to approximate shortest paths
SIAM Journal on Computing | 2019-09-16 | Paper |
Fast constructions of light-weight spanners for general graphs
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
Efficient algorithms for constructing very sparse spanners and emulators
ACM Transactions on Algorithms | 2019-03-28 | Paper |
A fast network-decomposition algorithm and its applications to constant-time distributed computation
Theoretical Computer Science | 2018-11-29 | Paper |
Fast constructions of lightweight spanners for general graphs
ACM Transactions on Algorithms | 2018-11-05 | Paper |
A linear-size logarithmic stretch path-reporting distance oracle for general graphs
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Optimal Euclidean Spanners
Journal of the ACM | 2018-08-02 | Paper |
Efficient algorithms for constructing very sparse spanners and emulators
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Prioritized metric structures and embedding
SIAM Journal on Computing | 2018-07-04 | Paper |
On efficient distributed construction of near optimal routing schemes
Distributed Computing | 2018-04-11 | Paper |
| Ramsey spanning trees and their applications | 2018-03-15 | Paper |
A simple deterministic distributed MST algorithm, with near-optimal time and message complexities
Proceedings of the ACM Symposium on Principles of Distributed Computing | 2017-10-11 | Paper |
Deterministic distributed \((\Delta + o(\Delta))\)-edge-coloring, and vertex-coloring of graphs with bounded diversity
Proceedings of the ACM Symposium on Principles of Distributed Computing | 2017-10-11 | Paper |
A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
\((2\Delta-1)\)-edge-coloring is much easier than maximal matching in the distributed setting
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
On efficient distributed construction of near optimal routing schemes (extended abstract)
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing | 2017-09-29 | Paper |
Distributed Strong Diameter Network Decomposition
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing | 2017-09-29 | Paper |
Terminal embeddings
Theoretical Computer Science | 2017-09-28 | Paper |
| Terminal embeddings | 2017-08-31 | Paper |
Distributed exact shortest paths in sublinear time
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Space-efficient path-reporting approximate distance oracles
Theoretical Computer Science | 2017-03-16 | Paper |
Optimizing budget allocation for center and median points
Theoretical Computer Science | 2016-04-01 | Paper |
Computing almost shortest paths (extended abstract)
Proceedings of the twentieth annual ACM symposium on Principles of distributed computing | 2016-03-04 | Paper |
A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
Structural Information and Communication Complexity | 2016-01-08 | Paper |
Distributed deterministic edge coloring using bounded neighborhood independence
Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing | 2015-09-11 | Paper |
Can quantum communication speed up distributed computation?
Proceedings of the 2014 ACM symposium on Principles of distributed computing | 2015-09-03 | Paper |
Computing almost shortest paths
ACM Transactions on Algorithms | 2015-09-02 | Paper |
An improved algorithm for radio broadcast
ACM Transactions on Algorithms | 2015-09-02 | Paper |
Prioritized metric structures and embedding
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Steiner shallow-light trees are exponentially lighter than spanning ones
SIAM Journal on Computing | 2015-08-18 | Paper |
| A faster distributed protocol for constructing a minimum spanning tree | 2015-08-03 | Paper |
Efficient algorithms for constructing \((1+{\epsilon}, {\beta})\)-spanners in the distributed and streaming models
Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing | 2015-08-03 | Paper |
Light spanners
SIAM Journal on Discrete Mathematics | 2015-07-31 | Paper |
Deterministic distributed vertex coloring in polylogarithmic time
Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing | 2015-03-02 | Paper |
(1 + εΒ) -spanner constructions for general graphs
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
Distributed \(({\Delta}+1)\)-coloring in linear (in \({\Delta})\) time
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
Balancing degree, diameter, and weight in Euclidean spanners
SIAM Journal on Discrete Mathematics | 2014-12-22 | Paper |
Sublogarithmic distributed \textsc{MIS} algorithm for sparse graphs using Nash-Williams decomposition
Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing | 2014-12-12 | Paper |
| Improved schedule for radio broadcast | 2014-10-13 | Paper |
| Sparse source-wise and pair-wise distance preservers | 2014-10-13 | Paper |
Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
ACM Transactions on Algorithms | 2014-09-09 | Paper |
Optimal Euclidean spanners, really short, thin and lanky
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Combinatorial algorithms for distributed graph coloring
Distributed Computing | 2014-07-11 | Paper |
Light spanners
Automata, Languages, and Programming | 2014-07-01 | Paper |
Distributed Graph Coloring: Fundamentals and Recent Developments
Synthesis Lectures on Distributed Computing Theory | 2014-06-20 | Paper |
Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
SIAM Journal on Computing | 2014-06-04 | Paper |
| An improved construction of progression-free sets | 2014-05-22 | Paper |
Distributed deterministic edge coloring using bounded neighborhood independence
Distributed Computing | 2014-03-28 | Paper |
A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing | 2014-03-13 | Paper |
Deterministic distributed vertex coloring in polylogarithmic time
Journal of the ACM | 2014-02-17 | Paper |
Symmetry breaking depending on the chromatic number or the neighborhood growth
Theoretical Computer Science | 2014-01-13 | Paper |
Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
Distributed Computing | 2013-06-13 | Paper |
An improved construction of progression-free sets
Israel Journal of Mathematics | 2012-11-19 | Paper |
Energy fluctuations shape free energy of nonspecific biomolecular interactions
Journal of Statistical Physics | 2012-04-04 | Paper |
Combinatorial algorithms for distributed graph coloring
Lecture Notes in Computer Science | 2011-10-28 | Paper |
Narrow-Shallow-Low-Light Trees with and without Steiner Points
SIAM Journal on Discrete Mathematics | 2011-10-27 | Paper |
Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
Distributed Computing | 2010-09-09 | Paper |
Balancing degree, diameter and weight in Euclidean spanners
Lecture Notes in Computer Science | 2010-09-06 | Paper |
Lower-stretch spanning trees
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Low-light trees, and tight lower bounds for Euclidean spanners
Discrete & Computational Geometry | 2010-05-21 | Paper |
New length bounds for cycle bases
Information Processing Letters | 2010-03-24 | Paper |
Narrow-Shallow-Low-Light Trees with and without Steiner Points
Lecture Notes in Computer Science | 2009-10-29 | Paper |
Lower-Stretch Spanning Trees
SIAM Journal on Computing | 2009-04-30 | Paper |
Bounds on the performance of back-to-front airplane boarding policies
Operations Research Letters | 2008-11-27 | Paper |
The hardness of approximating spanner problems
Theory of Computing Systems | 2007-12-19 | Paper |
Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
Automata, Languages and Programming | 2007-11-28 | Paper |
Sparse Sourcewise and Pairwise Distance Preservers
SIAM Journal on Discrete Mathematics | 2007-05-22 | Paper |
An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
SIAM Journal on Computing | 2007-05-03 | Paper |
A faster distributed protocol for constructing a minimum spanning tree
Journal of Computer and System Sciences | 2006-12-07 | Paper |
An approximation algorithm for the directed telephone multicast problem
Algorithmica | 2006-09-26 | Paper |
Sublogarithmic approximation for telephone multicast
Journal of Computer and System Sciences | 2006-06-30 | Paper |
A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem
SIAM Journal on Computing | 2006-06-01 | Paper |
Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem
SIAM Journal on Discrete Mathematics | 2006-06-01 | Paper |
Sparse Distance Preservers and Additive Spanners
SIAM Journal on Discrete Mathematics | 2006-06-01 | Paper |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2005-08-25 | Paper |
Approximating \(k\)-spanner problems for \(k>2\)
Theoretical Computer Science | 2005-06-30 | Paper |
$(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
SIAM Journal on Computing | 2005-02-21 | Paper |
Logarithmic inapproximability of the radio broadcast problem
Journal of Algorithms | 2004-11-23 | Paper |
| scientific article; zbMATH DE number 2079323 (Why is no real title available?) | 2004-07-28 | Paper |
| scientific article; zbMATH DE number 2079365 (Why is no real title available?) | 2004-07-28 | Paper |
| scientific article; zbMATH DE number 2038712 (Why is no real title available?) | 2004-02-08 | Paper |
| scientific article; zbMATH DE number 1757950 (Why is no real title available?) | 2002-06-20 | Paper |
| scientific article; zbMATH DE number 1670859 (Why is no real title available?) | 2001-12-09 | Paper |
| scientific article; zbMATH DE number 1629828 (Why is no real title available?) | 2001-11-01 | Paper |
