Publications

Book

  • D. Peleg, Distributed Computing: A Locality-Sensitive Approach, SIAM, Philadelphia, PA, 2000.

Refereed Journals

  1. D. Peleg, A Generalized Closure and Complement Phenomenon, DM  50, (1984), 285-293.

  2. D. Harel and D. Peleg, On Static Logics, Dynamic Logics and Complexity Classes, Info. & Contr. 60, (1984), 86-102.
  3. D. Harel and D. Peleg, Process Logic with Regular Formulas, TCS 38, (1985), 307-322.
  4. D. Harel and D. Peleg, More on Looping vs. Repeating in Dynamic Logic, IPL 20, (1985), 87-90.
  5. D. Peleg, Concurrent Dynamic Logic, J. ACM 34, (1987), 450-479.
  6. D. Peleg, Communication in Concurrent Dynamic Logic, JCSS 35, (1987), 23-58.
  7.  D. Peleg and B. Simons, On Fault Tolerant Routings in General Networks, I&C 74, (1987), 33-49.
  8. J. Intrator and D. Peleg, An Ecient Algorithm for the Long Transportation Problem, Asia-Pacic J. of Operational Research 4, (1987), 57-68.
  9. D. Peleg and E. Upfal, The Generalized Packet Routing Problem, TCS 53, (1987), 281-293.
  10.  D. Peleg, Concurrent Program Schemes and Their Logics, TCS 55, (1987), 1-45.
  11. C. Dwork, D. Peleg, N. Pippenger and E. Upfal, Fault Tolerance in Networks of Bounded Degree, SICOMP 17, (1988), 975-988.
  12. D. Peleg and A. Van Gelder, Packet Distribution on a Ring, JPDC  6, (1989), 558-567.
  13. D. Peleg and E. Upfal, The Token Distribution Problem, SICOMP  18, (1989), 229-243.
  14. D. Peleg and A.A. Schaer, Graph Spanners, JGT  13, (1989), 99-116.
  15. D. Peleg and J.D. Ullman, An Optimal Synchronizer for the Hypercube, SICOMP 18, (1989), 740-747.
  16. D. Peleg and E. Upfal, A Tradeo Between Space and Eciency for Routing Tables, J. ACM 36, (1989), 510-530.
  17. D. Peleg and A.A. Schaer, Time Bounds on Fault Tolerant Broadcasting, Networks 19, (1989), 803-822.
  18. D. Peleg and E. Upfal, Constructing Disjoint Paths on Expander Graphs, Combinatorica 9, (1989), 289-313.
  19. B. Awerbuch, A. Bar-Noy, N. Linial and D. Peleg, Compact Distributed Data Structures for Adaptive Routing, CWI Quarterly  2, (1989), 277-305.
  20. D. Peleg, Time-Optimal Leader Election in General Networks (Research Note), JPDC 8, (1990), 96-99.
  21. D. Peleg and E. Upfal, A Time-Randomness Tradeo for Oblivious Routing, SICOMP 19, (1990), 256-266.
  22. B. Awerbuch, O. Goldreich, D. Peleg and R. Vainish, A Tradeo Between Information and Communication in Broadcast Protocols, J. ACM 37, (1990), 238-256.
  23.  H. Attiya, A. Bar-Noy, D. Dolev, D. Peleg and R. Reischuk, Renaming in an Asynchronous Environment, J. ACM 37, (1990), 524-548.
  24. B. Awerbuch, A. Bar-Noy, N. Linial and D. Peleg, Improved Routing Strategies with Succinct Tables, JALG 11, (1990), 307-341.
  25. U. Feige, D. Peleg, P. Raghavan and E. Upfal, Randomized Broadcast in Networks, J. RSA 1, (1990), 447-460.
  26. A. Bar-Noy and D. Peleg, Square Meshes are Not Always Optimal, IEEE Trans. Computers 40, (1991), 196-204.
  27. M. Grigni and D. Peleg, Tight Bounds on Minimum Broadcast Networks, SIDMA 4, (1991), 207-222.
  28. Y. Ben-Asher, D. Peleg, R. Ramaswami and A. Schuster, The Power of Reconguration, JPDC 13, (1991), 139-153.
  29. N. Alon, A. Bar-Noy, N. Linial and D. Peleg, A Lower Bound for Radio Broadcast, JCSS 43, (1991), 290-298.
  30.  A. Bar-Noy, D. Dolev, D. Koller and D. Peleg, Fault-Tolerant Critical Section Management in Asynchronous Environments, I&C 95, (1991), 1-20.
  31. B. Awerbuch and D. Peleg, Routing with Polynomial Communication-Space Trade-o, SIDMA 5, (1992), 151-162.
  32. N. Alon, A. Bar-Noy, N. Linial and D. Peleg, Single Round Simulation on Radio Networks, JALG 13, (1992), 188-210.
  33.  D. Peleg, Distance-Dependent Distributed Directories, I&C 103 (1993), 270-298.
  34.  J. Bar-Ilan, G. Kortsarz and D. Peleg, How to Allocate Network Centers, JALG 15, (1993), 385-415.
  35.  B. Patt and D. Peleg, Time-Space Tradeos for Set Operations, TCS 110, (1993), 99-129.
  36. B. Awerbuch, S. Kutten and D. Peleg, On Buer-Economical Store-and-Forward Deadlock Prevention, IEEE Trans. Commun., 42, (1994), 2934-2937. 
  37. G. Kortsarz and D. Peleg, Trac-Light Scheduling on the Grid, DAM 53, (1994), 211-234.
  38. G. Kortsarz and D. Peleg, Generating Sparse 2-Spanners, JALG 17, (1994), 222-236.
  39. U. Feige, D. Peleg, P. Raghavan and E. Upfal, Computing with Noisy Information, SICOMP 23, (1994), 1001-1018.
  40. B. Awerbuch, B. Berger, L. Cowen and D. Peleg, Low Diameter Graph Decomposition is in NC, J. RSA 5, (1994), 442-452.
  41. J. Bar-Ilan, G. Kortsarz and D. Peleg, Information Centre Allocation, The Electronic Library, 12, (1994), 361-365.
  42.  I. Cidon, S. Kutten, Y. Mansour and D. Peleg, Greedy Packet Scheduling, SICOMP 24, (1995), 148-57.
  43. D. Peleg, A Note on Optimal Time Broadcast in Faulty Hypercubes, JPDC 26, (1995), 132-135.
  44. D. Peleg, On the Maximum Density of 0-1 Matrices with No Forbidden Rectangles, DM  140, (1995), 269-274.
  45.  N. Alon, R.M. Karp, D. Peleg and D. West, A Graph-Theoretic Game and its Application to the k-Server Problem, SICOMP 24, (1995), 78-100.
  46. Y. Ben-Asher, K.-J. Lange, D. Peleg and A. Schuster, The Complexity of Reconguring Network Models, I&C 121, (1995), 41-58.
  47. B. Awerbuch and D. Peleg, Online Tracking of Mobile Users, J. ACM, 42, (1995), 1021-1058
  48.  G. Kortsarz and D. Peleg, Approximation Algorithms for Minimum Time Broadcast, SIDMA 8, (1995), 401-427.
  49. D. Peleg and A. Wool, The Availability of Quorum Systems, I&C 123, (1995), 210-223.
  50. J. Bar-Ilan and D. Peleg, Scheduling Jobs Using Common Resources, I&C 125, (1996), 52-61.
  51.  B. Awerbuch, B. Berger, L. Cowen and D. Peleg, Fast Distributed Network Decompositions and Covers, JPDC 39, (1996), 105-114.
  52. D. Peleg and A. Wool, Crumbling walls: a class of practical and ecient quorum systems, DC 10, (1997), 87{97.
  53.  D. Peleg and A. Wool, The Availability of Crumbling Wall Quorum Systems, DAM 74, (1997), 69{83.
  54. D. Peleg, G. Schechtman and A. Wool, Randomized Approximation of Bounded Multicovering Problems, Algorith-mica 18, (1997), 44-66.
  55. R. Holzman, Y. Marcus and D. Peleg, Load Balancing in Quorum Systems, SIDMA 10, (1997), 223-245.
  56. J. Garay, S. Kutten and D. Peleg, A Sub-Linear Time Distributed Algorithm for Minimum-Weight Spanning Trees, SICOMP 27, (1998), 302-316.
  57. G. Kortsarz and D. Peleg, Generating Low-Degree 2-Spanners, SICOMP 27, (1998), 1438-1456.
  58. S. Kutten and D. Peleg, Fast distributed construction of k-dominating sets and applications, JALG 28, (1998), 40-66.
  59. E. Kranakis, D. Krizanc, A. Pelc and D. Peleg, Approximate Maxima Finding of Continuous Functions under Restricted Budget, TCS 203, (1998), 151-162.
  60. D. Peleg, Size Bounds for Dynamic Monopolies, DAM 86, (1998), 263-273.
  61. B. Awerbuch, B. Berger, L. Cowen and D. Peleg, Near-Linear Time Construction of Sparse Neighborhood Covers, SICOMP 28, (1998), 263-277.
  62. B. Awerbuch, I. Cidon, S. Kutten, Y. Mansour and D. Peleg, Optimal Broadcast with Partial Knowledge, SICOMP b, (1998), 511-524.
  63. C. Laforest, A.L. Liestman, D. Peleg, T.C. Shermer and D. Sotteau, Edge Disjoint Spanners of Complete Graphs and Complete Digraphs, DM 203, (1999), 133-159.
  64. C. Gavoille and D. Peleg, The Compactness of Interval Routing, SIDMA 12, (1999), 459-473.
  65. S. Dolev, E. Kranakis, D. Krizanc and D. Peleg, Bubbles: Adaptive Routing Scheme for High-Speed Dynamic Networks, SICOMP 29, (1999), 804-833.
  66. G. Kortsarz and D. Peleg, Approximating the Weight of Shallow Steiner Trees, DAM 93, (1999), 265-285.
  67. S. Kutten and D. Peleg, Fault-Local Distributed Mending, JALG 30, (1999), 144-165.
  68. D. Peleg, Proximity-Preserving Labeling Schemes, JGT 33, (2000), 167-176.
  69. R. Focardi, F.L. Luccio and D. Peleg, Feedback vertex set in hypercbes, IPL 76, (2000), 1-5.
  70. S. Kutten and D. Peleg, Tight fault locality, SICOMP 30, (2000), 247-268.
  71. D. Peleg and V. Rubinovich, A near-tight lower bound on the time complexity of distributed MST construction, SICOMP 30, (2000), 1427-1442.
  72. J. Bar-Ilan, G. Kortsarz and D. Peleg, Generalized Submodular Cover Problems and Applications, TCS 250, (2001), 179-200.
  73. U. Feige, G. Kortsarz and D. Peleg, The Dense k-Subgraph Problem, Algorithmica 29, (2001), 410-421.
  74. L. Gasieniec, A. Pelc and D. Peleg, The wakeup problem in synchronous broadcast systems, SIDMA 14, (2001), 207-222.
  75. C. Gavoille and D. Peleg, The Compactness of Interval Routing for Almost All Graphs, SICOMP 31, (2001), 706-721.
  76. Y. Hassin and D. Peleg, Distributed Probabilistic Polling and Applications to Proportionate Agreement, I&C 171, (2001), 248-268.
  77. Y. Hassin and D. Peleg, Sparse Communication Networks and Ecient Routing in the Plane, DC 14, (2001), 205-215.
  78. P. Fraigniaud, A. Pelc, D. Peleg and S. Perennes, Assigning Labels in Unknown Anonymous Networks, DC 14, (2001), 163-183.
  79. D. Peleg and E. Reshef, Low complexity variants of the Arrow Distributed Directory, JCSS 63, (2001), 474-485.
  80. D. Peleg, Local Majorities, Coalitions and Monopolies in Graphs: A Review, TCS 282, (2002), 231-257. 
  81. 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.
  82. L. Drori and D. Peleg, Faster Exact Solutions for Some NP-Hard Problems, TCS 287, (2002), 473-499.
  83. D. Peleg and A. Wool, How to be an Ecient Snoop, or the Probe Complexity of Quorum Systems, SIDMA 15, (2002), 416-433.
  84. J.-C. Bermond, J. Bond, D. Peleg and S. Perennes, The Power of Small Coalitions in Graphs, DAM 127, (2003), 399-414.
  85. J.-C. Bermond, N. Marlin, D. Peleg and S. Perennes, Directed Virtual Path Layouts in ATM networks, TCS 291, (2003), 3-28.
  86. T. Eilam, C. Gavoille and D. Peleg, Compact Routing Schemes with Low Stretch Factor, JALG 46, (2003), 97-114.
  87. C. Gavoille and D. Peleg, Compact and Localized Distributed Data Structures, DC 16, (2003), 111-120.
  88. S. Kutten, D. Peleg and U. Vishkin, Deterministic Resource Discovery in Distributed Networks, TOCS 36, (2003), 479-495.
  89. A. Korman, D. Peleg and Y. Rodeh, Labeling Schemes for Dynamic Tree Networks, TOCS 37, (2004), 49-75.
  90.  C. Gavoille, D. Peleg, S. Perennes and R. Raz, Distance Labeling in Graphs, JALG 53, (2004), 85-112.
  91. M. Elkin and D. Peleg, (1 + ; )-Spanner Constructions for General Graphs, SICOMP 33, (2004), 608-631.
  92. M. Katz, N.A. Katz, A. Korman and D. Peleg, Labeling Schemes for Flow and Connectivity, SICOMP 34, (2004), 23-40.
  93. A. Pelc and D. Peleg, Broadcasting with locally bounded Byzantine faults, IPL 93, (2005), 109-115.
  94. D. Peleg and U. Pincas, Virtual path layouts optimizing total hop count on ATM tree networks, JDA 3, (2005), 101-112.
  95. N. Lev-Tov and D. Peleg, Polynomial Time Approximation Schemes for Base Station Coverage with Minimum Total Radii, Computer Networks 47, (2005), 489-501.
  96. R. Cohen and D. Peleg, Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems, SICOMP 34, (2005), 1516-1528.
  97. D. Peleg, Informative Labeling Schemes for Graphs, TCS 340, (2005), 577-593.
  98. M. Katz, N. Katz and D. Peleg, Distance Labeling Schemes for Well-Separated Graph Classes, DAM 145, (2005), 384-402.
  99. M. Elkin and D. Peleg, Approximating k-Spanner Problems for k > 2, TCS 337, (2005), 249-277.
  100. P. Fraigniaud, D. Ilcinkas, G. Peer, A. Pelc and D. Peleg, Graph Exploration by a Finite Automaton, TCS 345, (2005), 331-344.
  101. Z. Lotker, B. Patt-Shamir, E. Pavlov and D. Peleg, MST Construction in O(loglog n) Communication Rounds, SICOMP 35, (2005), 120-131.
  102. N. Agmon and D. Peleg, Fault-Tolerant Gathering Algorithms for Autonomous Mobile Robots, SICOMP 36, (2006), 56-82.
  103. Y. Hassin and D. Peleg, Average Probe Complexity in Quorum Systems, JCSS 72, (2006), 592-616.
  104. Z. Lotker, B. Patt-Shamir and D. Peleg, Distributed MST for Constant Diameter Graphs, DC 18, (2006), 453-460.
  105. S. Kutten and D. Peleg, Asynchronous Resource Discovery in Peer to Peer Networks Computer Networks 51, (2007), 190-206.
  106. T. Eilam, C. Gavoille and D. Peleg, Average Stretch Analysis of Compact Routing Schemes, DAM 155, (2007), 598-610.
  107. D. Peleg, Approximation algorithms for the Label-CoverMAX and Red-Blue Set Cover Problems, JDA 5, (2007), 55-64.
  108. R. Matichin and D. Peleg, Approximation Algorithm for Hotlink Assignment in the Greedy Model, TCS 383, (2007), 102-110.
  109. L. Gasieniec, D. Peleg and Q. Xin, Faster Communication in Known Topology Radio Networks, DC 19, (2007), 289-300.
  110. A. Pelc and D. Peleg, Feasibility and Complexity of Broadcasting with Random Transmission Failures, TCS 370, (2007), 279-292.
  111. M. Elkin and D. Peleg, The Hardness of Approximating Spanner Problems, TOCS 41, (2007), 691-729.
  112. O. Gerstel, S. Kutten, E.S. Laber, R. Matichin, D. Peleg, A.A. Pessoa and C. Souza, Reducing Human Interactions in Web Directory Searches, ACM Trans. Information Systems 25, (2007).
  113. A. Korman and D. Peleg, Labeling Schemes for Weighted Dynamic Trees, I&C 205, (2007), 1721-1740.
  114. R. Cohen and D. Peleg, Convergence of Autonomous Mobile Robots With Inaccurate Sensors and Movements, SICOMP 38, (2008), 276-302.
  115. R. Cohen and D. Peleg, Local Spreading Algorithms for Autonomous Robot Systems, TCS 399, (2008), 71-82.
  116. A. Korman and D. Peleg, Compact Separator Decompositions in Dynamic Trees and Applications to Labeling Schemes, DC 21, (2008), 141-161.
  117. Y. Emek and D. Peleg, Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs, SICOMP 38, (2008), 176-1781.
  118. L. Gasieniec, E. Kantor, D.R. Kowalski, D. Peleg and C. Su, Time ecient k-shot broadcasting in known topology radio networks, DC 21, (2008), 117-127.
  119. A. Korman and D. Peleg, Dynamic Routing Schemes for Graphs with Low Local Density, ACM TALG 4, (2008), 41:1-41:18.
  120. R. Cohen, P. Fraigniaud, D. Ilcinkas, A. Korman and D. Peleg, Label-Guided Graph Exploration by a Finite Automaton, ACM TALG 4, (2008), 42:1-42:18.
  121. R. Cohen, P. Fraigniaud, D. Ilcinkas, A. Korman and D. Peleg, Labeling Schemes for Tree Representation, Algorith- mica 53, (2009), 1-15.
  122. Y. Zhang, E. Manisterski, S. Kraus, V.S. Subrahmanian and D. Peleg, Computing the Fault Tolerant Capability of Multiagent Deployment, Articial Intelligence 173, (2009), 437-465.
  123. N. Lev-Tov and D. Peleg, Con ict Free Coloring of Unit Disks, DAM 157, (2009), 1521-1532.
  124. E. Kantor and D. Peleg, Approximate Hierarchical Facility Location and Applications to the Bounded Depth Steiner Tree and Range Assignment Problems, JDA 7, (2009), 341-362.
  125. A. Efrima and D. Peleg, Distributed Algorithms for Partitioning A Swarm of Autonomous Mobile Robots, TCS 14, (2009), 1355-1368.
  126. Y. Emek, L. Gasieniec, E. Kantor, A. Pelc, D. Peleg and C. Su, Broadcasting in UDG Radio Networks with Unknown Topology, DC 21, (2009), 331-351.
  127. Y. Emek and D. Peleg, A tight Upper Bound on the Probabilistic Embedding of Series-Parallel Graphs, SIDMA 23, (2009), 1827-1841.
  128. A. Korman, D. Peleg and Y. Rodeh, Constructing Labeling Schemes Through Universal Matrices, Algorithmica 57, (2010), 641-652.
  129. A. Korman, S. Kutten and D. Peleg, Proof Labeling Schemes, DC 22, (2010), 215-233.
  130. D. Adjiashvili and D. Peleg, Equal-Area Locus-Based Convex Polygon Decomposition, TCS 411, (2010), 1648-1667.
  131. S. Chechik, M. Langberg, D. Peleg and L. Roditty, Fault-Tolerant Spanners for General Graphs, SICOMP 39, (2010), 3403-3423.
  132. D. Peleg and L. Roditty, Localized spanner construction for Ad Hoc Networks with Variable Transmission Range, ACM Trans. on Sensor Networks 7, (2010).
  133. Y. Emek, D. Peleg and L. Roditty, A Near-Linear Time Algorithm for Computing Replacement Paths in Planar Directed Graphs, ACM TALG 6, (2010).
  134. O. Weimann and D. Peleg, A note on exact distance labeling, IPL 111, (2011), 671-673.
  135. S. Chechik, M. Langberg, D. Peleg and L. Roditty, f-Sensitivity Distance Oracles and Routing Schemes, Algorithmica 63, (2012), 861-882.
  136. S. Chechik, Y. Emek, B. Patt-Shamir and D. Peleg, Sparse Reliable Graph Backbones, I&C 210, (2012), 31-39.
  137. O. Amini, D. Peleg, S. Perennes, I. Sau and S. Saurabh, On the approximability of some degree-constrained subgraph problems DAM 160, (2012), 1661-1679.
  138. C. Avin, Y. Emek, E. Kantor, Z. Lotker, D. Peleg and L. Roditty, SINR Diagrams: Convexity and Its Applications in Wireless Networks. J. ACM 59, (2012).
  139. A. Das Sarma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg and R. Wattenhofer, Distributed Verication and Hardness of Distributed Approximation, SICOMP 41, (2012), 1235-1265.
  140. D. Peleg, I. Sau and M. Shalom, On Approximating the d-Girth of a Graph, DAM 161, (2013), 2587-2596.
  141. D. Peleg and L. Roditty, Relaxed spanners for directed disk graphs, Algorithmica 65, (2013), 146-158.
  142. L. Kor, A. Korman and D. Peleg, Tight Bounds For Distributed MST Verication, TOCS 53, (2013), 318-340.
  143. P. Fraigniaud, A. Korman and D. Peleg, Towards a Complexity Theory for Local Distributed Computing, J. ACM 60(5), (2013), 35.
  144. Y. Dieudonne, A. Pelc and D. Peleg, Gathering despite mischief, ACM TALG 11, (2014), 28pp.
  145. S. Chechik and D. Peleg, Robust Fault Tolerant Uncapacitated Facility Location, TCS 543, (2014), 9-23.
  146. P. Fraigniaud, M. Goos, A. Korman, M. Parter and D. Peleg, Randomized Distributed Decision, DC 27, (2014), 419-434.
  147. C. Avin, M. Borokhovich, Y. Haddad, E. Kantor, Z. Lotker, M. Parter and D. Peleg, Testing the Irreducibility of Nonsquare Perron-Frobenius Systems, IPL 114, (2014), 728-733.
  148. S. Chechik and D. Peleg, The Fault Tolerant Capacitated k-Center Problem, TCS 566, (2015), 12-25.
  149. S. Kutten, G. Pandurangan, D. Peleg, P. Robinson and A. Trehan, Sublinear Bounds for Randomized Leader Election, TCS 561, (2015).
  150. G. Braunschvig, A. Brutzkus, D. Peleg and A. Sealfon, Truth Tellers and Liars With Fewer Questions, DM 338,(2015), 1310-1316.
  151. S. Kutten, G. Pandurangan, D. Peleg, P. Robinson and A. Trehan, On the Complexity of Universal Leader Election, J. ACM 62(1), (2015), 7:1-7:27.
  152. E. Kantor, Z. Lotker, M. Parter and D. Peleg, The Topology of Wireless Communication, J. ACM 62(5), (2015), 37:1-7:32.
  153. G. Braunschvig, S. Chechik, D. Peleg and A. Sealfon, Fault Tolerant Additive and (; )-Spanners, TCS 580, (2015), 94-100.
  154. I. Abraham, S. Chechik, C. Gavoille and D. Peleg, Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension, ACM TALG 12, (2016), 22:1-17.
  155. B. Haeupler, G. Pandurangan, D. Peleg, R. Rajaraman and Z. Sun, Discovery through Gossip, J. RSA 48, (2016), 565-587.
  156. E. Kantor and D. Peleg, Ecient k-shot Broadcasting in Radio Networks, DAM 202, (2016), 79-94.
  157. C. Avin, Z. Lotker, D. Peleg and I. Turkel, On Social Networks of Program Committees, Social Network Analysis and Mining 6 (1), (2016), 1-20.
  158. Y. Emek, E. Kantor and D. Peleg, On the Eect of the Deployment Setting on Broadcasting in Euclidean Radio Networks, DC accepted for publication.
  159. C. Avin, M. Borokhovich, Z. Lotker and D. Peleg, Distributed Computing on Core-Periphery Networks: Axiom-based Design, JPDC accepted for publication.
  160. C. Avin, A. Cohen, Y. Haddad, E. Kantor, Z. Lotker, M. Parter and D. Peleg, SINR Diagram with Interference Cancellation, AHNJ accepted for publication.
  161. S. Chechik, M. Johnson, M. Parter and D. Peleg, Secluded Connectivity Problems, Algorithmica, accepted for publication.