
Records 
Links 

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 




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 
Becker, F.; Montealecre, P.; Rapaport, I.; Todinca, I. 


Title 
The Impact Of Locality In The Broadcast Congested Clique Model 
Type 


Year 
2020 
Publication 
Siam Journal On Discrete Mathematics 
Abbreviated Journal 
SIAM Discret. Math. 


Volume 
34 
Issue 
1 
Pages 
682700 


Keywords 
broadcast congested clique; induced cycles; graph degeneracy 


Abstract 
The broadcast congested clique model (BCLIQUE) is a messagepassing model of distributed computation where n nodes communicate with each other in synchronous rounds. First, in this paper we prove that there is a oneround, deterministic algorithm that reconstructs the input graph G if the graph is ddegenerate, and rejects otherwise, using bandwidth b = O(d . log n). Then, we introduce a new parameter to the model. We study the situation where the nodes, initially, instead of knowing their immediate neighbors, know their neighborhood up to a fixed radius r. In this new framework, denoted BCLIQuE[r], we study the problem of detecting, in G, an induced cycle of length at most k (CYCLE <= k) and the problem of detecting an induced cycle of length at least k +1 (CYCLE>k). We give upper and lower bounds. We show that if each node is allowed to see up to distance r = left perpendicular k/2 right perpendicular + 1, then a polylogarithmic bandwidth is sufficient for solving CYCLE>k with only two rounds. Nevertheless, if nodes were allowed to see up to distance r = left perpendicular k/3 right perpendicular, then any oneround algorithm that solves CYCLE>k needs the bandwidth b to be at least Omega(n/ log n). We also show the existence of a oneround, deterministic BCLIQUE algorithm that solves CYCLE <= k with bandwitdh b = O(n(1/left perpendicular k/2 right perpendicular). log n). On the negative side, we prove that, if epsilon <= 1/3 and 0 < r <= k/4, then any epsilonerror, Rround, bbandwidth algorithm in the BCLIQUE[r] model that solves problem CYCLE(<= k )satisfies R . b = Omega(n(1/left perpendicular k/2 right perpendicular)). 


Address 
[Becker, F.; Todinca, I] Univ Orleans, INSA Ctr Val Loire, LIFO EA 4022, Orleans, France, Email: florent.becker@univorleans.fr; 


Corporate Author 

Thesis 



Publisher 
Siam Publications 
Place of Publication 

Editor 



Language 
English 
Summary Language 

Original Title 



Series Editor 

Series Title 

Abbreviated Series Title 



Series Volume 

Series Issue 

Edition 



ISSN 
08954801 
ISBN 

Medium 



Area 

Expedition 

Conference 



Notes 
WOS:000546886700033 
Approved 



Call Number 
UAI @ eduardo.moreno @ 
Serial 
1182 

Permanent link to this record 




Author 
Liedloff, M.; Montealegre, P.; Todinca, I. 


Title 
Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques 
Type 


Year 
2019 
Publication 
Algorithmica 
Abbreviated Journal 
Algorithmica 


Volume 
81 
Issue 
3 
Pages 
9861005 


Keywords 
FPT algorithms; Treewidth; Potential maximal cliques 


Abstract 
Let P(G,X) be a property associating a boolean value to each pair (G,X) where G is a graph and X is a vertex subset. Assume that P is expressible in counting monadic second order logic (CMSO) and let t be an integer constant. We consider the following optimization problem: given an input graph G=(V,E), find subsets XFV such that the treewidth of G[F] is at most t, property P(G[F],X) is true and X is of maximum size under these conditions. The problem generalizes many classical algorithmic questions, e.g., Longest Induced Path, Maximum Induced Forest, IndependentHPacking, etc. Fomin et al. (SIAM J Comput 44(1):5487, 2015) proved that the problem is polynomial on the class of graph Gpoly, i.e. the graphs having at most poly(n) minimal separators for some polynomial poly. Here we consider the class Gpoly+kv, formed by graphs of Gpoly to which we add a set of at most k vertices with arbitrary adjacencies, called modulator. We prove that the generic optimization problem is fixed parameter tractable on Gpoly+kv, with parameter k, if the modulator is also part of the input. 


Address 
[Liedloff, Mathieu; Todinca, Ioan] Univ Orleans, INSA Ctr Val Loire, LIFO, EA 4022, Orleans, France, Email: mathieu.liedloff@univorleans.fr; 


Corporate Author 

Thesis 



Publisher 
Springer 
Place of Publication 

Editor 



Language 
English 
Summary Language 

Original Title 



Series Editor 

Series Title 

Abbreviated Series Title 



Series Volume 

Series Issue 

Edition 



ISSN 
01784617 
ISBN 

Medium 



Area 

Expedition 

Conference 



Notes 
WOS:000460105700003 
Approved 



Call Number 
UAI @ eduardo.moreno @ 
Serial 
989 

Permanent link to this record 




Author 
Becker, F.; Kosowski, A.; Matamala, M.; Nisse, N.; Rapaport, I.; Suchan, K.; Todinca, I. 


Title 
Allowing each node to communicate only once in a distributed system: shared whiteboard models 
Type 


Year 
2015 
Publication 
Distributed Computing 
Abbreviated Journal 
Distrib. Comput. 


Volume 
28 
Issue 
3 
Pages 
189200 


Keywords 
Distributed computing; Local computation; Graph properties; Bounded communication 


Abstract 
In this paper we study distributed algorithms on massive graphs where links represent a particular relationship between nodes (for instance, nodes may represent phone numbers and links may indicate telephone calls). Since such graphs are massive they need to be processed in a distributed way. When computing graphtheoretic properties, nodes become natural units for distributed computation. Links do not necessarily represent communication channels between the computing units and therefore do not restrict the communication flow. Our goal is to model and analyze the computational power of such distributed systems where one computing unit is assigned to each node. Communication takes place on a whiteboard where each node is allowed to write at most one message. Every node can read the contents of the whiteboard and, when activated, can write one small message based on its local knowledge. When the protocol terminates its output is computed from the final contents of the whiteboard. We describe four synchronization models for accessing the whiteboard. We show that message size and synchronization power constitute two orthogonal hierarchies for these systems. We exhibit problems that separate these models, i.e., that can be solved in one model but not in a weaker one, even with increased message size. These problems are related to maximal independent set and connectivity. We also exhibit problems that require a given message size independently of the synchronization model. 


Address 
[Becker, Florent; Todinca, Ioan] Univ Orleans, LIFO, Orleans, France, Email: florent.becker@univorleans.fr; 


Corporate Author 

Thesis 



Publisher 
Springer 
Place of Publication 

Editor 



Language 
English 
Summary Language 

Original Title 



Series Editor 

Series Title 

Abbreviated Series Title 



Series Volume 

Series Issue 

Edition 



ISSN 
01782770 
ISBN 

Medium 



Area 

Expedition 

Conference 



Notes 
WOS:000354708400003 
Approved 



Call Number 
UAI @ eduardo.moreno @ 
Serial 
492 

Permanent link to this record 




Author 
Goles, E.; MontealegreBarba, P.; Todinca, I. 


Title 
The complexity of the bootstraping percolation and other problems 
Type 


Year 
2013 
Publication 
Theoretical Computer Science 
Abbreviated Journal 
Theor. Comput. Sci. 


Volume 
504 
Issue 

Pages 
7382 


Keywords 



Abstract 
We study the problem of predicting the state of a vertex in automata networks, where the state at each site is given by the majority function over its neighborhood. We show that for networks with maximum degree greater than 5 the problem is PComplete, simulating a monotone Boolean circuit. Then, we show that the problem for networks with no vertex with degree greater than 4 is in NC, giving a fast parallel algorithm. Finally, we apply the result to the study of related problems. (C) 2012 Elsevier B.V. All rights reserved. 


Address 



Corporate Author 

Thesis 



Publisher 

Place of Publication 

Editor 



Language 

Summary Language 

Original Title 



Series Editor 

Series Title 

Abbreviated Series Title 



Series Volume 

Series Issue 

Edition 



ISSN 
03043975 
ISBN 

Medium 



Area 

Expedition 

Conference 



Notes 
WOS:000325905100008 
Approved 



Call Number 
UAI @ eduardo.moreno @ 
Serial 
320 

Permanent link to this record 




Author 
Rapaport, I.; Suchan, K.; Todinca, I.; Verstraete, J. 


Title 
On Dissemination Thresholds in Regular and Irregular Graph Classes 
Type 


Year 
2011 
Publication 
Algorithmica 
Abbreviated Journal 
Algorithmica 


Volume 
59 
Issue 
1 
Pages 
1634 


Keywords 
Bootstrap percolation; Cubic graphs; Information dissemination 


Abstract 
We investigate the natural situation of the dissemination of information on various graph classes starting with a random set of informed vertices called active. Initially active vertices are chosen independently with probability p, and at any stage in the process, a vertex becomes active if the majority of its neighbours are active, and thereafter never changes its state. This process is a particular case of bootstrap percolation. We show that in any cubic graph, with high probability, the information will not spread to all vertices in the graph if p < 1/2. We give families of graphs in which information spreads to all vertices with high probability for relatively small values of p. 


Address 
[Todinca, I.] Univ Orleans, LIFO, Orleans, France, Email: rapaport@dim.uchile.cl 


Corporate Author 

Thesis 



Publisher 
Springer 
Place of Publication 

Editor 



Language 
English 
Summary Language 

Original Title 



Series Editor 

Series Title 

Abbreviated Series Title 



Series Volume 

Series Issue 

Edition 



ISSN 
01784617 
ISBN 

Medium 



Area 

Expedition 

Conference 



Notes 
WOS:000286525300003 
Approved 



Call Number 
UAI @ eduardo.moreno @ 
Serial 
119 

Permanent link to this record 