Records 
Author 
Montealegre, R.; PerezSalazar, S.; Rapaport, I.; Todinca, I. 
Title 
Graph reconstruction in the congested clique 
Type 

Year 
2020 
Publication 
Journal Of Computer And System Sciences 
Abbreviated Journal 
J. Comput. Syst. Sci. 
Volume 
113 
Issue 

Pages 
117 
Keywords 
Distributed computing; Congested clique; Round complexity; Reconstruction problem; Graph classes 
Abstract 
In this paper we study the reconstruction problem in the congested clique model. Given a class of graphs g, the problem is defined as follows: if G is not an element of g, then every node must reject; if G is an element of g, then every node must end up knowing all the edges of G. The cost of an algorithm is the total number of bits received by any node through one link. It is not difficult to see that the cost of any algorithm that solves this problem is Omega(log vertical bar g(n)vertical bar/n), where g(n) is the subclass of all nnode labeled graphs in g. We prove that the lower bound is tight and that it is possible to achieve it with only 2 rounds. (C) 2020 Elsevier Inc. All rights reserved. 
Address 
[Montealegre, R.] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: p.montealegre@edu.uai; 
Corporate Author 

Thesis 

Publisher 
Academic Press Inc Elsevier Science 
Place of Publication 

Editor 

Language 
English 
Summary Language 

Original Title 

Series Editor 

Series Title 

Abbreviated Series Title 

Series Volume 

Series Issue 

Edition 

ISSN 
00220000 
ISBN 

Medium 

Area 

Expedition 

Conference 

Notes 
WOS:000539435200001 
Approved 

Call Number 
UAI @ eduardo.moreno @ 
Serial 
1190 
Permanent link to this record 



Author 
Montealegre, R.; PerezSalazar, S.; Rapaport, I.; Todinca, I. 
Title 
Graph reconstruction in the congested clique 
Type 

Year 
2020 
Publication 
Journal Of Computer And System Sciences 
Abbreviated Journal 
J. Comput. Syst. Sci. 
Volume 
113 
Issue 

Pages 
117 
Keywords 
Distributed computing; Congested clique; Round complexity; Reconstruction problem; Graph classes 
Abstract 
In this paper we study the reconstruction problem in the congested clique model. Given a class of graphs g, the problem is defined as follows: if G is not an element of g, then every node must reject; if G is an element of g, then every node must end up knowing all the edges of G. The cost of an algorithm is the total number of bits received by any node through one link. It is not difficult to see that the cost of any algorithm that solves this problem is Omega(log vertical bar g(n)vertical bar/n), where g(n) is the subclass of all nnode labeled graphs in g. We prove that the lower bound is tight and that it is possible to achieve it with only 2 rounds. (C) 2020 Elsevier Inc. All rights reserved. 
Address 
[Montealegre, R.] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: p.montealegre@edu.uai; 
Corporate Author 

Thesis 

Publisher 
Academic Press Inc Elsevier Science 
Place of Publication 

Editor 

Language 
English 
Summary Language 

Original Title 

Series Editor 

Series Title 

Abbreviated Series Title 

Series Volume 

Series Issue 

Edition 

ISSN 
00220000 
ISBN 

Medium 

Area 

Expedition 

Conference 

Notes 
WOS:000539435200001 
Approved 

Call Number 
UAI @ alexi.delcanto @ 
Serial 
1229 
Permanent link to this record 