Publications by Prof. David Peleg

Contents: Book, Journal Papers, Conference Proceedings, Others

A. Book

  1. D. Peleg, Distributed Computing: A Locality-Sensitive Approach, SIAM, Philadelphia, PA, 2000.
B. Journal papers
  1. L. Gasieniec, D. Peleg and Q. Xin, Faster Communication in Known Topology Radio Networks, Distributed Computing Special Issue of PODC'05 papers, accepted for publication.
  2. R. Matichin and D. Peleg, Approximation Algorithm for Hotlink Assignment in the Greedy Model, Theoretical Computer Science, Special Issue of SIROCCO'04 papers, accepted for publication.
  3. M. Elkin and D. Peleg, The Hardness of Approximating Spanner Problems, Theory of Computing Systems, accepted for publication.
  4. A. Pelc and D. Peleg, Feasibility and Complexity of Broadcasting with Random Transmission Failures, Theoretical Computer Science, accepted for publication.
  5. D. Peleg, Approximation algorithms for the Label-Cover$_{MAX}$ and Red-Blue Set Cover Problems, J. Discrete Algorithms 5, (2007), 55-64.
  6. S. Kutten and D. Peleg, Asynchronous Resource Discovery in Peer to Peer Networks Computer Networks 51, (2007), 190-206.
  7. T. Eilam, C. Gavoille and D. Peleg, Average Stretch Analysis of Compact Routing Schemes, Discrete Applied Mathematics 155, (2007), 598-610.
  8. Z. Lotker, B. Patt-Shamir and D. Peleg, Distributed MST for Constant Diameter Graphs, Distributed Computing 18, (2006), 453-460.
  9. N. Agmon and D. Peleg, Fault-Tolerant Gathering Algorithms for Autonomous Mobile Robots, SIAM J. on Computing 36, (2006), 56-82.
  10. Y. Hassin and D. Peleg, Average Probe Complexity in Quorum Systems, J. Comput. Syst. Science72, (2006), 592-616.
  11. R. Cohen and D. Peleg, Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems, SIAM J. on Computing 34, (2005), 1516-1528.
  12. Z. Lotker, B. Patt-Shamir, E. Pavlov and D. Peleg, MST Construction in O(loglog n) Communication Rounds, SIAM J. on Computing 35, (2005), 4120-131.
  13. M. Elkin and D. Peleg, Approximating k-Spanner Problems for k>2, Theoretical Computer Science 337, (2005), 249-277.
  14. P. Fraigniaud, D. Ilcinkas, G. Peer, A. Pelc and D. Peleg, Graph Exploration by a Finite Automaton, Theoretical Computer Science, Special Issue of MFCS'04 papers 345, (2005), 331-344.
  15. N. Lev-Tov and D. Peleg, Polynomial Time Approximation Schemes for Base Station Coverage with Minimum Total Radii, Computer Networks 47, (2005), 489-501.
  16. D. Peleg and U. Pincas, Virtual path layouts optimizing total hop count on ATM tree networks, J. Discrete Algorithms 3, (2005), 101-112.
  17. M. Katz, N. Katz and D. Peleg, Distance Labeling Schemes for Well-Separated Graph Classes, Discrete Applied Mathematics 145, (2005), 384-402.
  18. D. Peleg, Informative Labeling Schemes for Graphs, Theoretical Computer Science, Special Issue of MFCS'00 papers 340, (2005), 577-593.
  19. A. Pelc and D. Peleg, Broadcasting with locally bounded Byzantine faults, Information Processing Letters 93, (2005), 109-115.
  20. M. Katz, N.A. Katz, A. Korman and D. Peleg, Labeling Schemes for Flow and Connectivity, SIAM J. on Computing 34, (2004), 40-23.
  21. M. Elkin and D. Peleg, (1+epsilon,beta)-Spanner Constructions for General Graphs, SIAM J. on Computing 33, (2004), 608-631.
  22. C. Gavoille, D. Peleg, S. P\'{e}rennes and R. Raz, Distance Labeling in Graphs, J. of Algorithms 53, (2004), 85-112.
  23. A. Korman, D. Peleg and Y. Rodeh, Labeling Schemes for Dynamic Tree Networks, Theory of Computing Systems, Special Issue of STACS'02 papers 37, (2004), 49-75.
  24. C. Gavoille and D. Peleg, Compact and Localized Distributed Data Structures, Distributed Computing, PODC Jubilee Special Issue, 16, (2003), 111-120.
  25. S. Kutten, D. Peleg and U. Vishkin, Deterministic Resource Discovery in Distributed Networks, Theory of Computing Systems 36, Special Issue of SPAA'01 papers, (2003), 479-495.
  26. T. Eilam, C. Gavoille and D. Peleg, Compact Routing Schemes with Low Stretch Factor, J. of Algorithms 46, (2003), 97-114.
  27. J.-C. Bermond, N. Marlin, D. Peleg and S. Pérennes, Directed Virtual Path Layouts in ATM networks, Theoretical Computer Science Special Issue of DISC'98 papers 291, (2003), 3-28.
  28. J.-C. Bermond, J. Bond, D. Peleg and S. Pérennes, The Power of Small Coalitions in Graphs, Discrete Applied Mathematics 127, (2003), 399-414.
  29. D. Peleg and A. Wool, How to be an Efficient Snoop, or the Probe Complexity of Quorum Systems, SIAM J. on Discrete Mathematics 15, (2002), 416-433.
  30. L. Drori and D. Peleg, Faster Exact Solutions for Some NP-Hard Problems, Theoretical Computer Science 287, Special Issue of ESA'99 papers, (2002), 473-499.
  31. P. Bose, C. Kaklamanis, L.M. Kirousis, E. Kranakis, D. Krizanc and D. Peleg, Station Layouts in the Presence of Location Constraints, J. of Interconnection Networks 3, (2002), 1-19.
  32. D. Peleg, Local Majorities, Coalitions and Monopolies in Graphs: A Review, Theoretical Computer Science 282, (2002), 231-257.
  33. D. Peleg and E. Reshef, Low complexity variants of the Arrow Distributed Directory, J. Comput. Syst. Science 63, (2001), 474-485.
  34. P. Fraigniaud, A. Pelc, D. Peleg and S. Pérennes, Assigning Labels in Unknown Anonymous Networks, Distributed Computing 14, (2001), 163-183.
  35. Y. Hassin and D. Peleg, Sparse Communication Networks and Efficient Routing in the Plane, Distributed Computing Special Issue of PODC'00 papers 14, (2001), 205-215.
  36. Y. Hassin and D. Peleg, Distributed Probabilistic Polling and Applications to Proportionate Agreement, Information and Computation 171, (2001), 248-268.
  37. C. Gavoille and D. Peleg, The Compactness of Interval Routing for Almost All Graphs, SIAM J. on Computing 31, (2001), 706-721.
  38. L. Gasieniec, A. Pelc and D. Peleg, The wakeup problem in synchronous broadcast systems, SIAM J. on Discrete Mathematics 14, (2001), 207-222.
  39. U. Feige, G. Kortsarz and D. Peleg, The Dense k-Subgraph Problem, Algorithmica 29, (2001), 410-421.
  40. J. Bar-Ilan, G. Kortsarz and D. Peleg, Generalized Submodular Cover Problems and Applications, Theoretical Computer Science 250, (2001), 179-200.
  41. D. Peleg and V. Rubinovich, A near-tight lower bound on the time complexity of distributed MST construction, SIAM J. on Computing 30, (2000), 1427-1442.
  42. S. Kutten and D. Peleg, Tight fault locality, SIAM J. on Computing 30, (2000), 247-268.
  43. R. Focardi, F.L. Luccio and D. Peleg, Feedback vertex set in hypercubes, Information Processing Letters 76, (2000), 1-5.
  44. D. Peleg, Proximity-Preserving Labeling Schemes, J. of Graph Theory 33, (2000), 167-176.
  45. S. Kutten and D. Peleg, Fault-Local Distributed Mending, J. of Algorithms 30, (1999), 144-165.
  46. G. Kortsarz and D. Peleg, Approximating the Weight of Shallow Steiner Trees, Discrete Applied Mathematics 93, (1999), 265-285.
  47. S. Dolev, E. Kranakis, D. Krizanc and D. Peleg, Bubbles: Adaptive Routing Scheme for High-Speed Dynamic Networks, SIAM J. on Computing 29, (1999), 804-833.
  48. C. Gavoille and D. Peleg, The Compactness of Interval Routing, SIAM J. on Discrete Mathematics 12, (1999), 459-473.
  49. C. Laforest, A.L. Liestman, D. Peleg, T.C. Shermer and D. Sotteau, Edge Disjoint Spanners of Complete Graphs and Complete Digraphs, Discrete Mathematics 203, (1999), 133-159.
  50. B. Awerbuch, I. Cidon, S. Kutten, Y. Mansour and D. Peleg, Optimal Broadcast with Partial Knowledge, SIAM J. on Computing 28, (1998), 511-524.
  51. B. Awerbuch, B. Berger, L. Cowen and D. Peleg, Near-Linear Time Construction of Sparse Neighborhood Covers, SIAM J. on Computing 28, (1998), 263-277.
  52. D. Peleg, Size Bounds for Dynamic Monopolies, Discrete Applied Mathematics 86, (1998), 263-273.
  53. E. Kranakis, D. Krizanc, A. Pelc and D. Peleg, Approximate Maxima Finding of Continuous Functions under Restricted Budget, Theoretical Computer Science 203, (1998), 151-162.
  54. S. Kutten and D. Peleg, Fast distributed construction of k-dominating sets and applications, J. of Algorithms 28, (1998), 40-66.
  55. G. Kortsarz and D. Peleg, Generating Low-Degree 2-Spanners, SIAM J. on Computing 27, (1998), 1438-1456.
  56. J. Garay, S. Kutten and D. Peleg, A Sub-Linear Time Distributed Algorithm for Minimum-Weight Spanning Trees, SIAM J. on Computing 27, (1998), 302-316.
  57. R. Holzman, Y. Marcus and D. Peleg, Load Balancing in Quorum Systems, SIAM J. on Discrete Mathematics 10, (1997), 223-245.
  58. D. Peleg, G. Schechtman and A. Wool, Randomized Approximation of Bounded Multicovering Problems, Algorithmica 18, Special Issue on Approximation Algorithms, (1997), 44-66.
  59. D. Peleg and A. Wool, The Availability of Crumbling Wall Quorum Systems, Discrete Applied Mathematics 74, (1997), 69-83.
  60. D. Peleg and A. Wool, Crumbling walls: a class of practical and efficient quorum systems, Distributed Computing 10, Special Issue of PODC'95 papers, (1997), 87-97.
  61. B. Awerbuch, B. Berger, L. Cowen and D. Peleg, Fast Distributed Network Decompositions and Covers, J. of Parallel and Distributed Computing 39, (1996), 105-114.
  62. J. Bar-Ilan and D. Peleg, Scheduling Jobs Using Common Resources, Information and Computation 125, (1996), 52-61.
  63. D. Peleg and A. Wool, The Availability of Quorum Systems, Information and Computation 123, (1995), 210-223.
  64. G. Kortsarz and D. Peleg, Approximation Algorithms for Minimum Time Broadcast, SIAM J. on Discrete Mathematics, 8, (1995), 401-427.
  65. B. Awerbuch and D. Peleg, Online Tracking of Mobile Users, J. ACM, 42, (1995), 1021-1058.
  66. Y. Ben-Asher, K.-J. Lange, D. Peleg and A. Schuster, The Complexity of Reconfiguring Network Models, Information and Computation, 121, (1995), 41-58.
  67. N. Alon, R.M. Karp, D. Peleg and D. West, A Graph-Theoretic Game and its Application to the k-Server Problem, SIAM J. on Computing, 24, (1995), 78-100.
  68. D. Peleg, On the Maximum Density of 0-1 Matrices with No Forbidden Rectangles, Discrete Mathematics 140, (1995), 269-274.
  69. D. Peleg, A Note on Optimal Time Broadcast in Faulty Hypercubes, J. of Parallel and Distributed Computing 26, (1995), 132-135.
  70. I. Cidon, S. Kutten, Y. Mansour and D. Peleg, Greedy Packet Scheduling, SIAM J. on Computing, 24, (1995), 148-157.
  71. J. Bar-Ilan, G. Kortsarz and D. Peleg, Information Centre Allocation, The Electronic Library, 12, (1994), 361-365.
  72. B. Awerbuch, B. Berger, L. Cowen and D. Peleg, Low Diameter Graph Decomposition is in NC, J. on Random Structures and Algorithms, 5, (1994), 442-452.
  73. U. Feige, D. Peleg, P. Raghavan and E. Upfal, Computing with Noisy Information, SIAM J. on Computing, 23, (1994), 1001-1018.
  74. G. Kortsarz and D. Peleg, Generating Sparse 2-Spanners, J. of Algorithms, 17, (1994), 222-236.
  75. G. Kortsarz and D. Peleg, Traffic-Light Scheduling on the Grid, Discrete Applied Mathematics 53, Special Issue on Broadcasting and Gossiping, (1994), 211-234.
  76. B. Awerbuch, S. Kutten and D. Peleg, On Buffer-Economical Store-and-Forward Deadlock Prevention, IEEE Trans. on Communication, 42, (1994), 2934-2937.
  77. B. Patt and D. Peleg, Time-Space Tradeoffs for Set Operations, Theoretical Computer Science 110, (1993), 99-129.
  78. J. Bar-Ilan, G. Kortsarz and D. Peleg, How to Allocate Network Centers, J. of Algorithms 15, (1993), 385-415.
  79. D. Peleg, Distance-Dependent Distributed Directories, Information and Computation 103 (1993), 270-298.
  80. N. Alon, A. Bar-Noy, N. Linial and D. Peleg, Single Round Simulation on Radio Networks, J. of Algorithms 13, (1992), 188-210.
  81. B. Awerbuch and D. Peleg, Routing with Polynomial Communication-Space Trade-off, SIAM J. on Discrete Mathematics 5, (1992), 151-162.
  82. A. Bar-Noy, D. Dolev, D. Koller and D. Peleg, Fault-Tolerant Critical Section Management in Asynchronous Environments, Information and Computation 95, (1991), 1-20.
  83. N. Alon, A. Bar-Noy, N. Linial and D. Peleg, A Lower Bound for Radio Broadcast, J. Comput. Syst. Science 43, (1991), 290-298.
  84. Y. Ben-Asher, D. Peleg, R. Ramaswami and A. Schuster, The Power of Reconfiguration, J. of Parallel and Distributed Computing 13, Special Issue on the Frontiers of Massively Parallel Computation, (1991), 139-153.
  85. M. Grigni and D. Peleg, Tight Bounds on Minimum Broadcast Networks, SIAM J. on Discrete Mathematics 4, (1991), 207-222.
  86. A. Bar-Noy and D. Peleg, Square Meshes are Not Always Optimal, IEEE Trans. on Computers 40, (1991), 196-204.
  87. U. Feige, D. Peleg, P. Raghavan and E. Upfal, Randomized Broadcast in Networks, J. on Random Structures & Algorithms 1, (1990), 447-460.
  88. B. Awerbuch, A. Bar-Noy, N. Linial and D. Peleg, Improved Routing Strategies with Succinct Tables, J. of Algorithms 11, (1990), 307-341.
  89. H. Attiya, A. Bar-Noy, D. Dolev, D. Peleg and R. Reischuk, Renaming in an Asynchronous Environment, J. ACM 37, (1990), 524-548.
  90. B. Awerbuch, O. Goldreich, D. Peleg and R. Vainish, A Tradeoff Between Information and Communication in Broadcast Protocols, J. ACM 37, (1990), 238-256.
  91. D. Peleg and E. Upfal, A Time-Randomness Tradeoff for Oblivious Routing, SIAM J. on Computing 19, (1990), 256-266.
  92. D. Peleg, Time-Optimal Leader Election in General Networks (Research Note), J. of Parallel and Distributed Computing 8, (1990), 96-99.
  93. B. Awerbuch, A. Bar-Noy, N. Linial and D. Peleg, Compact Distributed Data Structures for Adaptive Routing, CWI Quarterly 2, (1989), 277-305.
  94. D. Peleg and E. Upfal, Constructing Disjoint Paths on Expander Graphs, Combinatorica 9, (1989), 289-313.
  95. D. Peleg and A.A. Schäffer, Time Bounds on Fault Tolerant Broadcasting, Networks 19, (1989), 803-822.
  96. D. Peleg and E. Upfal, A Tradeoff Between Space and Efficiency for Routing Tables, J. ACM 36, (1989), 510-530.
  97. D. Peleg and J.D. Ullman, An Optimal Synchronizer for the Hypercube, SIAM J. on Computing 18, (1989), 740-747.
  98. D. Peleg and A.A. Schäffer, Graph Spanners, J. of Graph Theory 13, (1989), 99-116.
  99. D. Peleg and E. Upfal, The Token Distribution Problem, SIAM J. on Computing 18, (1989), 229-243.
  100. D. Peleg and A. Van Gelder, Packet Distribution on a Ring, J. of Parallel and Distributed Computing 6, (1989), 558-567.
  101. C. Dwork, D. Peleg, N. Pippenger and E. Upfal, Fault Tolerance in Networks of Bounded Degree, SIAM J. on Computing 17, (1988), 975-988.
  102. D. Peleg, Concurrent Program Schemes and Their Logics, Theoretical Computer Science 55, (1987), 1-45.
  103. D. Peleg and E. Upfal, The Generalized Packet Routing Problem, Theoretical Computer Science 53, (1987), 281-293.
  104. J. Intrator and D. Peleg, An Efficient Algorithm for the Long Transportation Problem, Asia-Pacific J. of Operational Research 4, (1987), 57-68.
  105. D. Peleg and B. Simons, On Fault Tolerant Routings in General Networks, Information and Computation 74, (1987), 33-49.
  106. D. Peleg, Communication in Concurrent Dynamic Logic, J. Comput. Syst. Science 35, (1987), 23-58.
  107. D. Peleg, Concurrent Dynamic Logic, J. ACM 34, (1987), 450-479.
  108. D. Harel and D. Peleg, More on Looping vs. Repeating in Dynamic Logic, Information Processing Letters 20, (1985), 87-90.
  109. D. Harel and D. Peleg, Process Logic with Regular Formulas, Theoretical Computer Science 38, (1985), 307-322.
  110. D. Harel and D. Peleg, On Static Logics, Dynamic Logics and Complexity Classes, Information and Control 60, (1984), 86-102.
  111. D. Peleg, A Generalized Closure and Complement Phenomenon, Discrete Mathematics 50, (1984), 285-293.


C. Conference Proceedings

  1. A. Efrima and D. Peleg, Distributed Algorithms for Partitioning A Swarm of Autonomous Mobile Robots, 14th SIROCCO, June 2007, Italy.
  2. A. Efrima and D. Peleg, Distributed Models and Algorithms for Mobile Robot Systems, 33rd SOFSEM, Jan. 2007, Czech Republic, LNCS 4362, 70-87.
  3. A. Korman, D. Peleg and Y. Rodeh, Constructing Labeling Schemes Through Universal Matrices, 17th ISAAC, Kolkatta, India, Dec. 2006, 409-418.
  4. D. Peleg, Recent Advances on Approximation Algorithms for Minimum Energy Range Assignment Problems in Ad-Hoc Wireless Networks, 3rd CAAN, Chester, England, July 2006, 1-4.
  5. A. Korman and D. Peleg, Dynamic Routing Schemes for General Graphs, 33rd ICALP, Venice, Italy, July 2006, 619-930.
  6. R. Cohen and D. Peleg, Local Algorithms for Autonomous Robot Systems, SIROCCO 13th, LNCS 4056, Chester, England, June 2006, 29-43.
  7. E. Kantor and D. Peleg, Approximate Hierarchical Facility Location and Applications to the Shallow Steiner Tree and Range Assignment Problems, 6th CIAC, Rome, Italy, May 2006, 211-222.
  8. R. Cohen and D. Peleg, Convergence of Autonomous Mobile Robots With Inaccurate Sensors and Movements, 23rd STACS, Marseille, France, Feb. 2006, 549-560. (Also as Research Report MCS04-08, the Weizmann Institute of Science, 2004.)
  9. Y. Emek and D. Peleg, A tight Upper Bounds on the Probabilistic Embedding of Series-Parallel Graphs, 17th SODA, Miami, Jan. 2006, 1045-1053.
  10. R. Cohen, P. Fraigniaud, D. Ilcinkas, A. Korman and D. Peleg, Labeling Schemes for Tree Representation, 7th IWDC, Dec. 2005, Kharagpur, India, 13-24.
  11. D. Peleg, Distributed Coordination Algorithms for Mobile Robot Swarms: New Directions and Challenges, IWDC 7th, Dec. 2005, Kharagpur, India, 1-12.
  12. A. Korman, S. Kutten and D. Peleg, Proof Labeling Schemes, PODC2 4th, Las vegas, Nevada, July 2005, 9-18.
  13. L. Gasieniec, D. Peleg and Q. Xin, Faster Communication in Known Topology Radio Networks, 24th PODC, Las vegas, Nevada, July 2005, 129-137.
  14. A. Pelc and D. Peleg, Feasibility and Complexity of Broadcasting with Random Transmission Failures, 24th PODC, Las vegas, Nevada, July 2005, 334-341.
  15. R. Cohen, P. Fraigniaud, D. Ilcinkas, A. Korman and D. Peleg, Label-Guided Graph Exploration by a Finite Automaton, ICALP 32nd, July 2005, Lisboa, Portugal, 335-346.
  16. B. Awerbuch, B. Patt-Shamir, D. Peleg and M. Tuttle, Adaptive Collaboration in Peer-to-Peer Systems, 25th ICDCS, Columbus, Ohio, June 2005, 71-80.
  17. S. Kutten, H. Ono, D. Peleg, K. Sadakane and M. Yamashita Energy-Optimal Online Algorithms for Broadcasting in Wireless Networks, 2nd WONS, St. Moritz, Switzerland, Jan. 2005.
  18. B. Awerbuch, B. Patt-Shamir, D. Peleg and M. Tuttle, Improved Recommendation Systems, 16th SODA, Vancouver, Canada, Jan. 2005.
  19. R. Cohen and D. Peleg, Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems, 12th ESA, Bergen, Norway, Sept. 2004, 228-239.
  20. P. Fraigniaud, D. Ilcinkas, G. Peer, A. Pelc and D. Peleg, Graph Exploration by a Finite Automaton, 29th MFCS, Prague, Czech Republic, Aug. 2004, Springer Verlag, LNCS.
  21. R. Matichin and D. Peleg, Approximation Algorithm for Hotlink Assignment in the Greedy Model, 11th SIROCCO, Bratislava, Slovakia, June 2004, 233-244.
  22. R. Cohen and D. Peleg, Robot Convergence via Center-of-Gravity Algorithms, 11th SIROCCO, Bratislava, Slovakia, June 2004, 79-88.
  23. B. Awerbuch, B. Patt-Shamir, D. Peleg and M. Tuttle, Collaboration of Untrusting Peers with Changing Interests, 5th EC, New York, New York, May 2004.
  24. C. Ambuhl, A.E.F. Clementi, M. Di Ianni, N. Lev-Tov, A. Monti, D. Peleg, G. Rossi and R. Silvestri, Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks, 21st STACS, Montpellier, France, March 2004.
  25. Y. Emek and D. Peleg, Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs, 15th SODA, New Orleans, Louisiana, January 2004.
  26. N. Agmon and D. Peleg, Fault-Tolerant Gathering Algorithms for Autonomous Mobile Robots, 15th SODA, New Orleans, Louisiana, January 2004.
  27. O. Gerstel, S. Kutten, R. Matichin and D. Peleg, Hotlink Enhancement Algorithms for Web Directories, 14th ISAAC, Kyoto, Japan, December 2003.
  28. R. Matichin and D. Peleg, Approximation Algorithm for Hotlink Assignments in Web Directories, 8th WADS, Ottawa, Canada, August 2003.
  29. A. Korman and D. Peleg, Labeling Schemes for Weighted Dynamic Trees, 30th ICALP, Eindhoven, The Netherlands, July 2003.
  30. Z. Lotker, B. Patt-Shamir, E. Pavlov and D. Peleg, MST Construction in O(loglog n) Communication Rounds, 15th SPAA, San Diego, California, June 2003.
  31. S. Kutten and D. Peleg, Asynchronous Resource Discovery in Peer to Peer Networks, 21st SRDS, Osaka, Japan, Oct. 2002.
  32. D. Peleg, Low stretch spanning trees, 27th MFCS, Warsaw, Poland, Aug. 2002, Springer Verlag, LNCS, 68-80.
  33. N. Lev-Tov and D. Peleg, Exact Algorithms and Approximation Schemes for Base Station Placement Problems, 8th SWAT, Turku, Finland, July 2002, 90-99.
  34. A. Korman, D. Peleg and Y. Rodeh, Labeling Schemes for Dynamic Tree Networks, 19th STACS, Antibes, France, Mar. 2002, 76-87.
  35. M. Katz, N.A. Katz, A. Korman and D. Peleg, Labeling Schemes for Flow and Connectivity, 13th SODA, San Francisco, CA, Jan. 2002, 927-936. (Also as Research Report MCS01-10, the Weizmann Institute of Science, 2001.)
  36. D. Peleg and U. Pincas, The Average Hop Count Measure for Virtual Path Layouts, 15th DISC, Lisbon, Portugal, Oct. 2001, 255-269.
  37. C. Gavoille, M. Katz, N.A. Katz, C. Paul and D. Peleg, Approximate Distance Labeling Schemes, 9th ESA, Aarhus, Denmark, Aug. 2001, 476-488. (Also as Research Report RR-1250-00, LaBRI, University of Bordeaux, France, Dec. 2000.)
  38. M. Elkin and D. Peleg, The Client-Server 2-Spanner Problem and Applications to Network Design, 8th SIROCCO, Vall de Nuria, Spain, June 2001, 117-132. (Also as Research Report MCS99-24, the Weizmann Institute of Science, 1999.)
  39. Cyril Gavoille, David Peleg, André Raspaud and Eric Sopéna, Small k-Dominating Sets in Planar Graphs with Applications, 27th WG, Boltenhagen, Germany, June 2001. (Also as Research Report RR-1258-01, LaBRI, University of Bordeaux, France, May. 2001.)
  40. Zvi Lotker, Boaz Patt-Shamir and D. Peleg, Distributed MST for Constant Diameter Graphs, 20th PODC, Newport, Rhode Island, August 2000.
  41. Y. Hassin and D. Peleg, Average Probe Complexity in Quorum Systems, 20th PODC, Newport, Rhode Island, August 2000, 180-189. (Also as Research Report MCS01-01, the Weizmann Institute of Science, 2001.)
  42. S. Kutten, D. Peleg and U. Vishkin, Deterministic Resource Discovery in Distributed Networks, 13th SPAA, Crete, Greece, July 2001, 77-83.
  43. M. Elkin and D. Peleg, (1+epsilon,beta)-Spanner Constructions for General Graphs, 33rd STOC, Crete, Greece, July 2001. (Also as Research Report MCS00-17, the Weizmann Institute of Science, 2000.)
  44. M. Elkin and D. Peleg, Approximating k-Spanner Problems for k>2, 8th IPCO, Utrecht, The Netherlands, June 2001. (Also as Research Report MCS00-14, the Weizmann Institute of Science, 2000.)
  45. C. Gavoille, D. Peleg, S. Pérennes and R. Raz, Distance Labeling in Graphs, 12th SODA, Washington, DC, Jan. 2001, 210-219. (Also as Research Report RR-1239-00, LaBRI, University of Bordeaux, France, Apr. 2000.)
  46. Y. Atzmony and D. Peleg, Distributed Algorithms for English Auctions, 14th DISC, Toledo, Spain, Oct. 2000.
  47. D. Peleg, Informative Labeling Schemes for Graphs, 25th MFCS, Bratislava, Slovakia, Aug. 2000, Springer Verlag, LNCS 1893, 579-588.
  48. Y. Hassin and D. Peleg, Sparse Communication Networks and Efficient Routing in the Plane, 19th PODC, Portland, Oregon, July 2000, 41-50.
  49. L. Gasieniec, A. Pelc and D. Peleg, The wakeup problem in synchronous broadcast systems, 19th PODC, Portland, Oregon, July 2000.
  50. P. Fraigniaud, A. Pelc, D. Peleg and S. Pérennes, Assigning Labels in Unknown Anonymous Networks, 19th PODC, Portland, Oregon, July 2000.
  51. M. Elkin and D. Peleg, Strong Inapproximability of the Basic k-Spanner Problem, 27th ICALP, Geneva, Switzerland, July 2000, 636-647. (Also as Research Report MCS99-23, the Weizmann Institute of Science, 1999.)
  52. D. Peleg, Approximation algorithms for the Label-CoverMAXand Red-Blue Set Cover Problems, 7th SWAT, Bergen, Norway, July 2000.
  53. Yehuda Hassin and David Peleg, Extremal Bounds for Proabilistic Polling in Graphs, 7th SIROCCO, L'Aquila, Italy, June 2000, Carleton Univ. Press, 167-180.
  54. M. Katz, N. Katz and D. Peleg, Distance Labeling Schemes for Well-Separated Graph Classes, 17th STACS, Lille, France, Feb. 2000, 516-528. (Also as Research Report MCS99-26, the Weizmann Institute of Science, 1999.)
  55. M. Elkin and D. Peleg, The Hardness of Approximating Spanner Problems, 17th STACS, Lille, France, Feb. 2000, 370-381. (Also as Research Report MCS99-14, the Weizmann Institute of Science, 1999.)
  56. P. Bose, C. Kaklamanis, L.M. Kirousis, E. Kranakis, D. Krizanc and D. Peleg, Station Layouts in the Presence of Location Constraints, 10th ISAAC, 1999.
  57. D. Peleg and V. Rubinovich, A near-tight lower bound on the time complexity of distributed MST construction, 40th FOCS, NY, NY, Oct. 1999, 253-261.
  58. L. Drori and D. Peleg, Faster Exact Solutions for Some NP-Hard Problems, 7th ESA, Prague, Czech Republic, July 1999.
  59. D. Peleg and E. Reshef, A Variant of the Arrow Distributed Directory with Low Average Complexity, 26th ICALP, Prague, Czech Republic, July 1999, 615-624.
  60. Y. Hassin and D. Peleg, Distributed Probabilistic Polling and Applications to Proportionate Agreement, 26th ICALP, Prague, Czech Republic, July 1999, 402-411.
  61. D. Peleg, Proximity-Preserving Labeling Schemes and Their Applications, 25th WG, June 1999, Ascona, Switzerland, 30-41.
  62. Y. Mansour and D. Peleg, An Approximation Algorithm for Minimum-Cost Network Design, Proc. DIMACS Workshop on Robust Communication Networks: Interconnection and Survivability, Piscataway, NJ, Nov. 1998, AMS, DIMACS series Vol. 53, 97-106.
  63. J.-C. Bermond, N. Marlin, D. Peleg and S. Pérennes, Virtual Path Layouts in Simple ATM networks, Proc. Sixth IFIP Workshop on Performance Modelling and Evaluation of ATM Networks, Ilkley, U.K., July 1998.
  64. J.-C. Bermond, N. Marlin, D. Peleg and S. Pérennes, Directed Virtual Path Layouts in ATM networks, 12th DISC, Andros, Greece, Oct. 1998, 75-88.
  65. C. Gavoille and D. Peleg, The Compactness of Interval Routing for Almost All Graphs, 12th DISC, Andros, Greece, Oct. 1998, 161-174.
  66. P. de la Torre, L. Narayanan and D. Peleg, Thy Neighbor's Interval is Greener: A Proposal for Exploiting Interval Routing Schemes (Position paper), 5th SIROCCO, Amalfi, Italy, June 1998.
  67. D. Peleg and E. Reshef, Deterministic Polylog Approximation for Minimum Communication Spanning Trees, 25th ICALP, Aalborg, Denmark, July 1998, 670-681. (Also as Research Report MCS98-01, the Weizmann Institute of Science, 1998.)
  68. D. Peleg, Distributed Matroid Basis Completion via Elimination Upcast and Distributed Correction of Minimum-Weight Spanning Trees, 25th ICALP, Aalborg, Denmark, July 1998, 164-175. (Also as Research Report MCS98-02, the Weizmann Institute of Science, 1998.)
  69. D. Peleg, Algorithmic aspects of dynamic coalitions and monopolies in graphs, Proc. Fun with Algorithms, Elba, Italy, June 1998.
  70. T. Eilam, C. Gavoille and D. Peleg, Compact Routing Schemes with Low Average Stretch Factor, 17th PODC, Puerto Vallarta, June 1998, 11-20.
  71. D. Peleg, Approximating Minimum Communication Spanning Trees, 4th SIROCCO, Ascona, Switzerland, July 1997. (See also Technical Report CS97-10, the Weizmann Institute of Science, 1997.)
  72. D. Peleg, Size Bounds for Dynamic Monopolies, 4th SIROCCO, Ascona, Switzerland, July 1997, Carleton Univ. Press, 151-161.
  73. G. Kortsarz and D. Peleg, Approximating Shallow-Light Trees, 8th SODA, New Orleans, Louisiana, Jan. 1997, 103-110.
  74. E. Kranakis, D. Krizanc, A. Pelc and D. Peleg, Approximate Maxima Finding of Continuous Functions under Restricted Budget, 22nd WG, June 1996, Como, Italy.
  75. D. Peleg, Local Majority Voting, Small Coalitions and Controlling Monopolies in Graphs: A Review, 3rd SIROCCO, Siena, Italy, June 1996, Carleton Univ. Press, 170-179.
  76. J.-C. Bermond, J. Bond, D. Peleg and S. Pérennes, Tight Bounds on the Size of 2-Monopolies, 3rd SIROCCO, Siena, Italy, June 1996, Carleton Univ. Press, 152-169.
  77. J. Bar-Ilan, G. Kortsarz and D. Peleg, Generalized Submodular Cover Problems and Applications, 4th ISTCS, Jerusalem, Israel, June 1996.
  78. D. Peleg and A. Wool, How to be an Efficient Snoop, or the Probe Complexity of Quorum Systems, 15th PODC, Philadelphia, May 1996, 290-299.
  79. S. Kutten and D. Peleg, Tight fault locality, 36th FOCS, Milwaukee, Oct. 1995.
  80. B. Awerbuch, S. Kutten, Y. Mansour and D. Peleg, Optimal Broadcast with Partial Knowledge, 9th WDAG, Le Mont Saint Michel, France, Sept. 1995.
  81. R. Holzman, Y. Marcus and D. Peleg, Load Balancing in Quorum Systems, 4th WADS, Kingston, Canada, August 1995, 38-49.
  82. S. Kutten and D. Peleg, Fault-Local Distributed Mending, 14th PODC, Ottawa, Canada, August 1995, 20-27.
  83. S. Kutten and D. Peleg, Fast distributed construction of k-dominating sets and applications, 14th PODC, Ottawa, Canada, August 1995, 238-249.
  84. D. Peleg and A. Wool, Crumbling walls: a class of practical and efficient quorum systems, 14th PODC, Ottawa, Canada, August 1995, 120-129.
  85. J.-C. Bermond and D. Peleg, The Power of Small Coalitions in Graphs, 2nd SIROCCO, Olympia, Greece, June 1995, Carleton Univ. Press, 173-184. (Also as Technical Report CS95-12, the Weizmann Institute of Science, 1995.)
  86. S. Dolev, E. Kranakis, D. Krizanc and D. Peleg, Bubbles: Adaptive Routing Scheme for High-Speed Dynamic Networks, 27th STOC, 1995.
  87. G. Kortsarz and D. Peleg, Generating Low-Degree 2-Spanners, 5th SODA, Arlington, Virginia, Jan. 1994, 556-563.
  88. J. Garay, S. Kutten and D. Peleg, A Sub-Linear Time Distributed Algorithm for Minimum-Weight Spanning Trees, 34th FOCS, Palo-Alto, Calif., Nov. 1993, 659-668.
  89. G. Kortsarz and D. Peleg, On Choosing a Dense Subgraph, 34th FOCS, Palo-Alto, Calif., Nov. 1993, 692-701. (Also as Technical Report CS92-32, the Weizmann Institute of Science, 1992.)
  90. B. Awerbuch, B. Berger, L. Cowen and D. Peleg, Near-Linear Cost Sequential and Distributed Constructions of Sparse Neighborhood Covers, 34th FOCS, Palo-Alto, Calif., Nov. 1993, 638-647.
  91. N. Linial, D. Peleg, Y. Rabinovich and M. Saks, Sphere Packing and Local Majorities in Graphs, 2nd ISTCS, Natanya, Israel, June 1993, IEEE Comp. Soc. Press, 141-149.
  92. D. Peleg, G. Schechtman and A. Wool, Approximating Bounded 0-1 Integer Linear Programs, 2nd ISTCS, Natanya, Israel, June 1993, IEEE Comp. Soc. Press, 69-77.
  93. J. Bar-Ilan and D. Peleg, Distributed Resource Allocation Algorithms, 6th WDAG, Haifa, Israel, Nov. 1992, Springer Verlag, LNCS 647, 277-291.
  94. G. Kortsarz and D. Peleg, Traffic-Light Scheduling on the Grid, 6th WDAG, Haifa, Israel, Nov. 1992, Springer Verlag, LNCS 647, 238-252.
  95. B. Awerbuch, B. Berger, L. Cowen and D. Peleg, Fast Network Decomposition, 11th PODC Vancouver, Canada, August 1992, 169-177.
  96. B. Awerbuch, B. Berger, L. Cowen and D. Peleg, Low Diameter Graph Decomposition is in NC, 3rd SWAT, Helsinki, Finland, July 1992, 83-93.
  97. G. Kortsarz and D. Peleg, Generating Sparse 2-Spanners, 3rd SWAT, Helsinki, Finland, July 1992, 73-82.
  98. Y. Ben-Asher, D. Peleg and A. Schuster, The Complexity of Reconfiguring Network Models, 1st ISTCS, 1992, 79-90.
  99. G. Kortsarz and D. Peleg, Approximation Algorithms for Minimum Time Broadcast, 1st ISTCS, 1992, 67-78.
  100. B. Awerbuch, S. Kutten and D. Peleg, Competitive Distributed Job Load Balancing, 24th STOC, May 1992, 571-580.
  101. B. Awerbuch, B. Patt-Shamir, D. Peleg and M. Saks, Adapting to Asynchronous Dynamic Networks, 24th STOC, May 1992, 557-570.
  102. N. Alon, R.M. Karp, D. Peleg and D. West, A Graph-Theoretic Game and its Application to the k-Server Problem, Proc. DIMACS Workshop on Online Algorithms, ACM, 1991, 1-9.
  103. B. Awerbuch and D. Peleg, Concurrent Online Tracking of Mobile Users, Proc. SIGCOMM, Zurich, Sept. 1991, 221-233.
  104. J. Bar-Ilan and D. Peleg, Approximation Algorithms for Selecting Network Centers, 2nd WADS, Ottawa, Canada, August 1991, 343-354.
  105. K. Gilon and D. Peleg, Compact Deterministic Distributed Dictionaries, 10th PODC, Montreal, Canada, August 1991, 81-94. (Also as Technical Report CS93-3, the Weizmann Institute of Science, 1993.)
  106. B. Awerbuch, I. Cidon, S. Kutten, Y. Mansour and D. Peleg, Broadcast with Partial Knowledge, 10th PODC, Montreal, Canada, August 1991, 153-163.
  107. B. Awerbuch, S. Kutten and D. Peleg, Efficient Deadlock-Free Routing, 10th PODC, Montreal, Canada, August 1991, 177-188.
  108. Y. Ben-Asher, D. Peleg, R. Ramaswami and A. Schuster, The Power of Reconfiguration, 18th ICALP, July 1991, Madrid, Spain.
  109. B. Awerbuch, S. Kutten and D. Peleg, On Buffer-Economical Store-and-Forward Deadlock Prevention, INFOCOM, Bal-Harbour, Florida, April 1991, 410-414.
  110. B. Awerbuch and D. Peleg, Network Synchronization with Polylogarithmic Overhead, 31st FOCS, Oct. 1990, 514-522. (Also as Technical Report CS90-19, the Weizmann Institute of Science, August 1990.)
  111. B. Awerbuch and D. Peleg, Sparse Partitions, 31st FOCS, Oct. 1990, 503-513.
  112. I. Cidon, S. Kutten, Y. Mansour and D. Peleg, Greedy Packet Scheduling, 4th WDAG, Bari, Italy, Sept. 1990, 169-184.
  113. D. Peleg, Distributed Data Structures: A Complexity Oriented View, 4th WDAG, Bari, Italy, Sept. 1990, 71-89.
  114. B. Awerbuch, A. Baratz and D. Peleg, Cost-sensitive analysis of communication protocols, 9th PODC, August 1990, pp. 177-187. (Also as Technical Report MIT/LCS/TM-453, 1991.)
  115. U. Feige, D. Peleg, P. Raghavan and E. Upfal, The Complexity of Randomized Broadcast, 1st SIGAL Symp. on Algorithms, Tokyo, Japan, August 1990, Springer-Verlag Lecture Notes in Computer Science, Vol. 450 (T. Asano, T. Ibaraki, H. Imai and T. Nishizeki, Editors), 128-137.
  116. U. Feige, D. Peleg, P. Raghavan and E. Upfal, Computing with Unreliable Information, 22nd STOC, May 1990, 128-137.
  117. A. Bar-Noy, D. Dolev, D. Koller and D. Peleg, Fault-Tolerant Critical Section Management in Asynchronous Environments, 3rd WDAG, Nice, France, Oct. 1989.
  118. A. Bar-Noy and D. Peleg, Square Meshes are Not Always Optimal, 1st SPAA, June 1989, 138-147.
  119. N. Alon, A. Bar-Noy, N. Linial and D. Peleg, On the Complexity of Radio Communication, 21st STOC, Seattle, WA, May 1989, 274-285.
  120. B. Awerbuch, A. Bar-Noy, N. Linial and D. Peleg, Compact Distributed Data Structures for Adaptive Routing, 21st STOC, Seattle, WA, May 1989, 479-489.
  121. B. Awerbuch, O. Goldreich, D. Peleg and R. Vainish, A Tradeoff Between Information and Communication in Broadcast Protocols, AWOC 1988, Springer Verlag, LNCS 319, 369-379.
  122. D. Krizanc, D. Peleg and E. Upfal, A Time-Randomness Tradeoff for Oblivious Routing, 20th STOC, pp. 93-102, 1988.
  123. D. Peleg and E. Upfal, A Tradeoff Between Space and Efficiency for Routing Tables, 20th STOC, pp. 43-52, 1988.
  124. H. Attiya, A. Bar-Noy, D. Dolev, D. Koller, D. Peleg and R. Reischuk, Achievable Cases in an Asynchronous Environment, 28th FOCS, pp. 337-346, 1987.
  125. D. Peleg and J.D. Ullman, An Optimal Synchronizer for the Hypercube, 6th PODC, pp. 77-85, Aug. 1987.
  126. D. Peleg and E. Upfal, Constructing Disjoint Paths on Expander Graphs, 19th STOC, pp. 264-273, 1987.
  127. D. Peleg and E. Upfal, The Token Distribution Problem, 27th FOCS, pp. 418-427, 1986.
  128. D. Peleg and B. Simons, On Fault Tolerant Routings in General Networks, 5th PODC, pp. 98-107, Aug. 1986.
  129. C. Dwork, D. Peleg, N. Pippenger and E. Upfal, Fault Tolerance in Networks of Bounded Degree, 18th STOC, pp. 370-379, 1986.
  130. D. Peleg, Concurrent Dynamic Logic, 17th STOC, pp. 232-239, 1985.


D. Others

  1. D. Peleg and D. Tendler, Low Stretch Spanning Trees for Planar Graphs, Research Report MCS01-14, the Weizmann Institute of Science, 2001.
  2. L. Drori and D. Peleg, Faster Solutions for Exact Hitting Set and Exact SAT, Technical Report MCS99-15, the Weizmann Institute of Science, Sept. 1999.
  3. D. Peleg, Graph Immunity Against Local Influence, Technical Report CS96-11, the Weizmann Institute of Science, 1996.
  4. D. Peleg and H. Regev, The hardness of Minimum Capacity Network Design, Technical Report CS95-17, the Weizmann Institute of Science, 1995.
  5. K. Gilon and D. Peleg, Embedding Techniques for Distributed Dictionaries, Technical Report CS93-2, the Weizmann Institute of Science, 1993.
  6. Y. Marcus and D. Peleg, Construction Methods for Quorum Systems, Technical Report CS92-33, the Weizmann Institute of Science, 1992.
  7. B. Awerbuch, A. Baratz and D. Peleg, Efficient Broadcast and Light-Weight Spanners, Manuscript, 1991.
  8. B. Awerbuch and D. Peleg, Locality-Sensitive Resource Allocation, Technical Report CS90-27, the Weizmann Institute of Science, November 1990.
  9. B. Awerbuch and D. Peleg, Efficient Distributed Construction of Sparse Covers, Technical Report CS90-17, the Weizmann Institute of Science, July 1990.
  10. B. Awerbuch and D. Peleg, Non-Obtrusive Synchronizers, Technical Report MIT/LCS/TM-426, April 1990.
  11. D. Peleg, Complexity Considerations for Distributed Data Structures, Technical report CS89-31, the Weizmann Institute of Science, December 1989.
  12. D. Peleg, Sparse Graph Partitions, Technical report CS89-01, the Weizmann Institute of Science, February 1989.
  13. D. Peleg and E. Upfal, Efficient Message Passing Using Succinct Routing Tables, Research Report RJ 5768, IBM Almaden, August 1987.
  14. D. Harel and D. Peleg, Order Relations and Tuple Languages: Extending the Database Relational Model to Capture More, Manuscript, The Weizmann Institute of Science, Rehovot, Israel, 1983.
  15. Y. Choueka and D. Peleg, A Note on omega-regular Languages, Bulletin of the EATCS 21, (1983), 21-23.