David Peleg

Research interests

Publications

• Distributed Verification and Hardness of Distributed Approximation

  SIAM Journal on Computing · 2012 · https://doi.org/10.1137/11085178x

• Proof labeling schemes

  Distributed Computing · 2010 · https://doi.org/10.1007/s00446-010-0095-3

• Fault-Tolerant Gathering Algorithms for Autonomous Mobile Robots

  SIAM Journal on Computing · 2006 · https://doi.org/10.1137/050645221

• Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems

  SIAM Journal on Computing · 2005 · https://doi.org/10.1137/s0097539704446475

• Graph exploration by a finite automaton

  Theoretical Computer Science · 2005 · https://doi.org/10.1016/j.tcs.2005.07.014

• Distance labeling in graphs

  Journal of Algorithms · 2004 · https://doi.org/10.1016/j.jalgor.2004.05.002

• Local majorities, coalitions and monopolies in graphs: a review

  Theoretical Computer Science · 2002 · https://doi.org/10.1016/s0304-3975(01)00055-x

• Sparse partitions

  Journal · 2002 · https://doi.org/10.1109/fscs.1990.89571

• The Dense k -Subgraph Problem

  Algorithmica · 2001 · https://doi.org/10.1007/s004530010050

• A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction

  SIAM Journal on Computing · 2000 · https://doi.org/10.1137/s0097539700369740

• Distributed Computing: A Locality-Sensitive Approach

  Society for Industrial and Applied Mathematics eBooks · 2000 · https://doi.org/10.1137/1.9780898719772

• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees

  SIAM Journal on Computing · 1998 · https://doi.org/10.1137/s0097539794261118

• Fast Distributed Construction of Smallk-Dominating Sets and Applications

  Journal of Algorithms · 1998 · https://doi.org/10.1006/jagm.1998.0929

• A Graph-Theoretic Game and Its Application to the k -Server Problem

  SIAM Journal on Computing · 1995 · https://doi.org/10.1137/s0097539792224474

• Computing with Noisy Information

  SIAM Journal on Computing · 1994 · https://doi.org/10.1137/s0097539791195877

• How to Allocate Network Centers

  Journal of Algorithms · 1993 · https://doi.org/10.1006/jagm.1993.1047

• Routing with Polynomial Communication-Space Trade-Off

  SIAM Journal on Discrete Mathematics · 1992 · https://doi.org/10.1137/0405013

• A lower bound for radio broadcast

  Journal of Computer and System Sciences · 1991 · https://doi.org/10.1016/0022-0000(91)90015-w

• Concurrent online tracking of mobile users

  Journal · 1991 · https://doi.org/10.1145/115992.116013

• The power of reconfiguration

  Journal of Parallel and Distributed Computing · 1991 · https://doi.org/10.1016/0743-7315(91)90084-m

• Renaming in an asynchronous environment

  Journal of the ACM · 1990 · https://doi.org/10.1145/79147.79158

• Randomized broadcast in networks

  Random Structures and Algorithms · 1990 · https://doi.org/10.1002/rsa.3240010406

• A trade-off between space and efficiency for routing tables

  Journal of the ACM · 1989 · https://doi.org/10.1145/65950.65953

• An Optimal Synchronizer for the Hypercube

  SIAM Journal on Computing · 1989 · https://doi.org/10.1137/0218050

• Graph spanners

  Journal of Graph Theory · 1989 · https://doi.org/10.1002/jgt.3190130114

Current projects

No projects listed.