Peleg David

Research output

Research output per year 1985 2011 2012 2013 2014 2015 2016 2017 2025

• 77 Article
• 73 Conference contribution
• 29 Paper
• 8 Conference article
• 15 More
  • 5 Chapter
  • 5 Editorial
  • 2 Meeting Abstract
  • 1 Book
  • 1 Foreword/postscript
  • 1 Special issue

Research output per year

Research output per year

Search results

• 2025

  Approximate realizations for outerplanaric degree sequences

  Bar-Noy, A., Böhnlein, T., Peleg, D., Ran, Y. & Rawitz, D., Mar 2025, In: Journal of Computer and System Sciences. 148, 20 p., 103588.

  Weizmann Institute of Science, Bar-Ilan University

  Research output: Contribution to journal › Article › peer-review

  Open Access
• 2024

  Graph realization of distance sets

  Bar-Noy, A., Peleg, D., Perry, M. & Rawitz, D., 1 Dec 2024, In: Theoretical Computer Science. 1019, 114810.

  Weizmann Institute of Science, Bar-Ilan University

  Research output: Contribution to journal › Article › peer-review

  Open Access

• Weighted microscopic image reconstruction

  Bar-Noy, A., Böhnlein, T., Lotker, Z., Peleg, D. & Rawitz, D., 15 Mar 2024, In: Discrete Applied Mathematics. 345, p. 17-33 17 p.

  Weizmann Institute of Science, Bar-Ilan University

  Research output: Contribution to journal › Article › peer-review
• 2023

  Composed Degree-Distance Realizations of Graphs

  Bar-Noy, A., Peleg, D., Perry, M. & Rawitz, D., Mar 2023, In: Algorithmica. 85, 3, p. 665-687 23 p.

  Bar-Ilan University, Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  • Specification 100%
  • Profile 95%
  • Specifications 72%
  • Graph in graph theory 51%
  • Range of data 34%

• Forcibly bipartite and acyclic (uni-)graphic sequences

  Bar-Noy, A., Böhnlein, T., Peleg, D. & Rawitz, D., Jul 2023, In: Discrete Mathematics. 346, 7, 8 p., 113460.

  Weizmann Institute of Science, Bar-Ilan University

  Research output: Contribution to journal › Article › peer-review

  • Graphics 100%
  • Degree Sequence 30%
  • Graph in graph theory 24%
  • Simple Graph 12%
  • Counting 11%

• Graph realizations: Maximum degree in vertex neighborhoods

  Bar-Noy, A., Choudhary, K., Peleg, D. & Rawitz, D., Sep 2023, In: Discrete Mathematics. 346, 9, 16 p., 113483.

  Weizmann Institute of Science, Bar-Ilan University

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Maximum Degree 100%
  • Vertex of a graph 59%
  • Graph in graph theory 48%
  • Realizability 30%
  • Simple Graph 24%

• The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication

  Kantor, E., Lotker, Z., Parter, M. & Peleg, D., 9 Mar 2023, In: ACM Transactions on Algorithms. 19, 1, 1.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  Open Access

• The power of small coalitions under two-tier majority on regular graphs

  Chebotarev, P. & Peleg, D., 15 Dec 2023, In: Discrete Applied Mathematics. 340, p. 239-258 20 p.

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Coalitions 100%
  • Valuation 81%
  • Vote 79%
  • Regular Graph 79%
  • Vertex of a graph 23%
• 2022

  Distributed Graph Realizations

  Augustine, J., Choudhary, K., Cohen, A., Peleg, D., Sivasubramaniam, S. & Sourav, S., 1 Jun 2022, In: IEEE Transactions on Parallel and Distributed Systems. 33, 6, p. 1321-1337 17 p.

  Tel Aviv University, Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Degree Sequence 100%
  • Overlay Networks 96%
  • Overlay networks 64%
  • Graph in graph theory 59%
  • Connectivity 48%

• Hotelling games in fault-prone settings

  Avin, C., Cohen, A., Lotker, Z. & Peleg, D., 24 Jun 2022, In: Theoretical Computer Science. 922, p. 96-107 12 p.

  Ben-Gurion University of the Negev, Bar-Ilan University, Weizmann Institute of Science, Tel Aviv University

  Research output: Contribution to journal › Article › peer-review

  • Fault 100%
  • Game 69%
  • Voronoi Cell 40%
  • Nash Equilibrium 31%
  • Line 19%

• The generalized microscopic image reconstruction problem

  Bar-Noy, A., Böhnlein, T., Lotker, Z., Peleg, D. & Rawitz, D., 15 Nov 2022, In: Discrete Applied Mathematics. 321, p. 402-416 15 p.

  Weizmann Institute of Science, Bar-Ilan University

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Image Reconstruction 100%
  • Probe 93%
  • Image reconstruction 80%
  • Graph in graph theory 21%
  • Grid 12%
• 2021

  Nonuniform SINR+Voronoi diagrams are effectively uniform

  Kantor, E., Lotker, Z., Parter, M. & Peleg, D., 22 Jul 2021, In: Theoretical Computer Science. 878-879, p. 53-66 14 p.

  Weizmann Institute of Science, Bar-Ilan University

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Voronoi Diagram 100%
  • Oils and fats 95%
  • Diagram 70%
  • Voronoi Cell 46%
  • Power control 37%
• 2020

  Efficiently realizing interval sequences

  BAR-NOY, AMOTZ., CHOUDHARY, KEERTI., PELEG, DAVID. & RAWITZ, DROR., 2020, In: SIAM Journal on Discrete Mathematics. 34, 4, p. 2318-2337 20 p.

  Bar-Ilan University, Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Interval 100%
  • Graphics 84%
  • Computing 35%
  • Certificate 17%
  • Realizability 16%

• Fault Tolerant Approximate BFS Structures with Additive Stretch

  Parter, M. & Peleg, D., 1 Dec 2020, In: Algorithmica. 82, 12, p. 3458-3491 34 p.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  • Fault-tolerant 100%
  • Stretch 95%
  • Computer science 26%
  • Vertex of a graph 22%
  • Spanning tree 20%

• Message lower bounds via efficient network synchronization

  Pandurangan, G., Peleg, D. & Scquizzato, M., 2 Mar 2020, In: Theoretical Computer Science. 810, p. 82-95 14 p.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Synchronization 100%
  • Lower bound 63%
  • Communication Complexity 54%
  • Message passing 51%
  • Communication 48%

• Mixed fault tolerance in server assignment: Combining reinforcement and backup

  Navon, T. & Peleg, D., 6 Oct 2020, In: Theoretical Computer Science. 836, p. 76-93 18 p.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Fault Tolerance 100%
  • Reinforcement 95%
  • Server 78%
  • Fault tolerance 72%
  • Assignment 67%

• Mixed preferential attachment model: Homophily and minorities in social networks

  Avin, C., Daltrophe, H., Keller, B., Lotker, Z., Mathieu, C., Peleg, D. & Pignolet, Y. A., 1 Oct 2020, In: Physica A: Statistical Mechanics and its Applications. 555, 15 p., 124723.

  Bar-Ilan University, Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  • Preferential Attachment 100%
  • Social Networks 88%
  • minorities 82%
  • attachment 72%
  • Affine transformation 27%

• Vertex-weighted realizations of graphs

  Bar-Noy, A., Peleg, D. & Rawitz, D., 6 Feb 2020, In: Theoretical Computer Science. 807, p. 56-72 17 p.

  Weizmann Institute of Science, Bar-Ilan University

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Vertex of a graph 100%
  • Requirements 99%
  • Graph in graph theory 81%
  • Degree Sequence 41%
  • Odd 37%
• 2019

  Distributed distance computation and routing with small messages

  Lenzen, C., Patt-Shamir, B. & Peleg, D., 8 Apr 2019, In: Distributed Computing. 32, 2, p. 133-157 25 p.

  Weizmann Institute of Science, Tel Aviv University

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Routing 100%
  • Network Algorithms 67%
  • Vertex of a graph 51%
  • Efficient Solution 48%
  • Shortest path 48%
• 2018

  Elites in social networks: An axiomatic approach to power balance and Price's square root law

  Avin, C., Lotker, Z., Peleg, D., Pignolet, Y. A. & Turkel, I., 1 Oct 2018, In: PLoS ONE. 13, 10, 35 p., e0205820.

  Ben-Gurion University of the Negev, Weizmann Institute of Science, Bar-Ilan University

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • social networks 100%
  • Social Networking 87%
  • Partition 76%
  • Psychological Power 72%
  • Respect 16%

• Fault-Tolerant approximate BFS structures

  Parter, M. & Peleg, D., Jan 2018, In: ACM Transactions on Algorithms. 14, 1, 15 p., 10.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Fault-tolerant 100%
  • Fault 18%
  • Multiplicative 12%
  • Spanners 10%
  • Constructible 9%

• Improved approximation algorithms for weighted 2-path partitions

  Bar-Noy, A., Peleg, D., Rabanca, G. & Vigan, I., 20 Apr 2018, In: Discrete Applied Mathematics. 239, p. 15-37 23 p.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Approximation algorithms 100%
  • Approximation Algorithms 81%
  • Partition 68%
  • Path 63%
  • Weighted Graph 27%

• The Topology of Wireless Communication on a Line

  Kantor, E., Lotker, Z., Parter, M. & Peleg, D., 8 Feb 2018, In: Theoretical Computer Science. 711, p. 105-108 4 p.

  Ben-Gurion University of the Negev, Weizmann Institute of Science, Technion - Israel Institute of Technology

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Wireless Communication 100%
  • Diagram 61%
  • Topology 50%
  • Wireless Networks 48%
  • Line 47%
• 2017

  Distributed computing on core–periphery networks: Axiom-based design

  Avin, C., Borokhovich, M., Lotker, Z. & Peleg, D., 1 Jan 2017, In: Journal of Parallel and Distributed Computing. 99, p. 51-67 17 p.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Distributed Computing 100%
  • Distributed computer systems 75%
  • Axiom 62%
  • Design 44%
  • Parallel algorithms 33%

• Isolated polyhydramnios in the third trimester: is a gestational diabetes evaluation of value?^*

  Peleg, D., Stahl-Rosenzweig, T., Kurzweil, Y. & Yogev, Y., 2 Nov 2017, In: Gynecological Endocrinology. 33, 11, p. 849-852 4 p.

  Bar-Ilan University, Tel Aviv University

  Research output: Contribution to journal › Article › peer-review

  • Polyhydramnios 100%
  • Gestational Diabetes 82%
  • Third Pregnancy Trimester 78%
  • Glucose 27%
  • Fasting 23%

• Secluded Connectivity Problems

  Chechik, S., Johnson, M. P., Parter, M. & Peleg, D., 1 Nov 2017, In: Algorithmica. 79, 3, p. 708-741 34 p.

  Tel Aviv University, Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  • Connectivity 100%
  • Polynomials 84%
  • Path 75%
  • NP-hard 71%
  • Steiner Tree 46%

• SINR diagram with interference cancellation

  Avin, C., Cohen, A., Haddad, Y., Kantor, E., Lotker, Z., Parter, M. & Peleg, D., 1 Jan 2017, In: Ad Hoc Networks. 54, p. 1-16 16 p.

  Ben-Gurion University of the Negev

  Research output: Contribution to journal › Article › peer-review

  Open Access

• SINR diagram with interference cancellation

  Avin, C., Cohen, A., Haddad, Y., Kantor, E., Lotker, Z., Parter, M. & Peleg, D., 1 Jan 2017, In: Ad Hoc Networks. 54, p. 1-16 16 p.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Wireless networks 100%
  • Polynomials 98%
• 2016

  Discovery Through Gossip

  Haeupler, B., Pandurangan, G., Peleg, D., Rajaraman, R. & Sun, Z., 1 May 2016, In: Random Structures and Algorithms. 48, 3, p. 565-587 23 p.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Gossip 100%
  • Directed graphs 76%
  • Vertex of a graph 37%
  • Overlay networks 26%
  • Peer to peer networks 26%

• Efficient k-shot broadcasting in radio networks

  Kantor, E. & Peleg, D., 31 Mar 2016, In: Discrete Applied Mathematics. 202, p. 79-94 16 p.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Radio Networks 100%
  • Broadcasting 83%
  • Vertex of a graph 15%
  • Topology 14%
  • Lower bound 9%

• Following the evolution of glassy states under external perturbations: the full replica symmetry breaking solution

  Haeupler, B., Pandurangan, G., Peleg, D., Rajaraman, R. & Sun, Z., May 2016, In: Journal Of Statistical Mechanics-Theory And Experiment. 2016, 5, 50 p., 53302.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  • Symmetry Breaking 100%
  • Replica 85%
  • Perturbation 72%
  • replicas 68%
  • Metastable States 58%

• Forbidden-set distance labels for graphs of bounded doubling dimension

  Abraham, I., Chechik, S., Gavoille, C. & Peleg, D., Feb 2016, In: ACM Transactions on Algorithms. 12, 2, 22.

  Tel Aviv University, Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  • Labeling Scheme 100%
  • Doubling 95%
  • Stretch 53%
  • Graph in graph theory 40%
  • Vertex of a graph 25%

• Notions of Connectivity in Overlay Networks [arXiv]

  Fraigniaud, P., Korman, A., Kutten, S., Peleg, D. & Yuval, E., Jan 2016, In: arXiv. 18, 17 p.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  • Overlay networks 100%
  • Network layers 91%
  • Wavelength division multiplexing 22%
  • Telecommunication networks 17%
  • Polynomials 15%

• On social networks of program committees: Structure and effect on paper acceptance fairness

  Avin, C., Lotker, Z., Peleg, D., Turke, I. & Turkel, I., 1 Dec 2016, In: Social Network Analysis and Mining. 6, 1, 18.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  • fairness 100%
  • social network 82%
  • acceptance 75%
  • coverage 32%
  • trend 12%

• On the effect of the deployment setting on broadcasting in Euclidean radio networks

  Emek, Y., Kantor, E. & Peleg, D., 1 Nov 2016, In: Distributed Computing. 29, 6, p. 409-434 26 p.

  Technion - Israel Institute of Technology, Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  • Radio Networks 100%
  • Broadcasting 83%
  • Euclidean 51%
  • Grid 22%
  • Time Complexity 21%

• Sparse fault-tolerant BFS structures

  Parter, M. & Peleg, D., Oct 2016, In: ACM Transactions on Algorithms. 13, 1, 11.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  • Breadth-first Search 100%
  • Fault-tolerant 83%
  • Vertex of a graph 34%
  • Search Trees 29%
  • Path 11%

• The domination game: proving the 3/5 conjecture on isolate-free forests

  Marcus, N. & Peleg, D., Mar 2016, In: arXiv. 5, 47 p., 1603.01181.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review
• 2015

  Fault tolerant additive and (μ, α)-spanners

  Braunschvig, G., Chechik, S., Peleg, D. & Sealfon, A., 17 May 2015, In: Theoretical Computer Science. 580, p. 94-100 7 p.

  Weizmann Institute of Science, Tel Aviv University

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Spanners 100%
  • Fault-tolerant 94%
  • Stretch 35%
  • Graph in graph theory 27%
  • Multiplicative 24%

• The fault-tolerant capacitated K-center problem

  Chechik, S. & Peleg, D., 2015, In: Theoretical Computer Science. 566, C, p. 12-25 14 p.

  Tel Aviv University, Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Fault-tolerant 100%
  • Center Problem 98%
  • Polynomials 60%
  • Vertex of a graph 29%
  • Weighted Graph 13%

• The Topology of Wireless Communication

  Kantor, E., Lotker, Z., Parter, M. & Peleg, D., 1 Oct 2015, In: Journal of the ACM. 62, 5, 37.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • wireless communication 100%
  • Partition 80%
  • Fat 80%
  • Communication 74%
  • topology 70%

• Tight bounds for distributed minimum-weight spanning tree verification [arXiv]

  Kor, L., Korman, A. & Peleg, D., Dec 2015, In: arXiv. 21 p.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  • Parallel algorithms 100%

• Truth tellers and liars with fewer questions

  Braunschvig, G., Peleg, D., Brutzkus, A. & Sealfon, A., 6 Aug 2015, In: Discrete Mathematics. 338, 8, p. 1310-1316 7 p.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Truth 100%
  • Binary 36%
• 2014

  Gathering despite mischief

  Dieudonné, Y., Pelc, A. & Peleg, D., 11 Aug 2014, In: ACM Transactions on Algorithms. 11, 1, 1.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  • Unknown 100%
  • Deterministic Algorithm 69%
  • Termination 64%
  • Arbitrary 63%
  • Mobile Agent 48%

• Immunity against local influence

  Peleg, D., 2014, In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8001, p. 168-179 12 p.

  Research output: Contribution to journal › Article › peer-review

  • Local Influence 100%
  • Coalitions 91%
  • Immunity 90%
  • Gain control 83%
  • Influence 22%

• Randomized distributed decision

  Fraigniaud, P., Göös, M., Korman, A., Parter, M. & Peleg, D., 23 Nov 2014, In: Distributed Computing. 27, 6, p. 419-434 16 p.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  • Language 100%
  • Distributed Computing 95%
  • Boosting 92%
  • Monte Carlo Algorithm 84%
  • Randomisation 74%

• Robust fault tolerant uncapacitated facility location

  Chechik, S. & Peleg, D., 2014, In: Theoretical Computer Science. 543, C, p. 9-23 15 p.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Facility Location 100%
  • Fault-tolerant 97%
  • Costs 31%
  • Facility Location Problem 21%
  • Minimise 13%

• Testing the irreducibility of nonsquare Perron-Frobenius systems

  Avin, C., Borokhovich, M., Haddad, Y., Kantor, E., Lotker, Z., Parter, M. & Peleg, D., 1 Jan 2014, In: Information Processing Letters. 114, 12, p. 728-733 6 p.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review
• 2013

  Brief announcement: Distributed MST in core-periphery networks

  Avin, C., Borokhovich, M., Lotker, Z. & Peleg, D., 1 Dec 2013, In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8205 LNCS

  Bar-Ilan University

  Research output: Contribution to journal › Article › peer-review

  • Parallel algorithms 100%

• On approximating the d-girth of a graph

  Peleg, D., Sau, I. & Shalom, M., Nov 2013, In: Discrete Applied Mathematics. 161, 16-17, p. 2587-2596 10 p.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  Open Access

  • Approximation algorithms 100%
  • Girth 97%
  • Hardness 72%
  • Subgraph 45%
  • Graph in graph theory 42%

• Relaxed spanners for directed disk graphs

  Peleg, D. & Roditty, L., Jan 2013, In: Algorithmica. 65, 1, p. 146-158 13 p.

  Bar-Ilan University, Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  • Spanners 100%
  • Spanner 99%
  • Ad hoc networks 72%
  • Ad Hoc Networks 60%
  • Radius 45%