caa a22 4500 445355107 CHVBK 20180317142857.0 cr unu---uuuuu 170323e20111001xx s 000 0 eng 10.1007/s00446-011-0132-x doi (NATIONALLICENCE)springer-10.1007/s00446-011-0132-x Distributed discovery of large near-cliques [Elektronische Daten] [Zvika Brakerski, Boaz Patt-Shamir] Given an undirected graph and $${0\le\epsilon\le1}$$, a set of nodes is called an $${\epsilon}$$-near clique if all but an $${\epsilon}$$ fraction of the pairs of nodes in the set have a link between them. In this paper we present a fast synchronous network algorithm that uses small messages and finds a near-clique. Specifically, we present a constant-time algorithm that finds, with constant probability of success, a linear size $${\epsilon}$$-near clique if there exists an $${\epsilon^3}$$-near clique of linear size in the graph. The algorithm uses messages of O(log n) bits. The failure probability can be reduced to n −Ω(1) by increasing the time complexity by a logarithmic factor, and the algorithm also works if the graph contains a clique of size Ω(n/(log log n)α) for some $${\alpha \in (0,1)}$$. Our approach is based on a new idea of adapting property testing algorithms to the distributed setting. Springer-Verlag, 2011 Brakerski Zvika Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel aut Patt-Shamir Boaz Department of Electrical Engineering, Tel Aviv University, 69978, Tel Aviv, Israel aut Distributed Computing Springer-Verlag 24/2(2011-10-01), 79-89 0178-2770 24:2<79 2011 24 446 https://doi.org/10.1007/s00446-011-0132-x text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00446-011-0132-x text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Brakerski Zvika Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel aut NATIONALLICENCE 700 1- Patt-Shamir Boaz Department of Electrical Engineering, Tel Aviv University, 69978, Tel Aviv, Israel aut NATIONALLICENCE 773 0- Distributed Computing Springer-Verlag 24/2(2011-10-01), 79-89 0178-2770 24:2<79 2011 24 446 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer