Records 
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 
Kosowski, A.; Li, B.; Nisse, N.; Suchan, K. 
Title 
kChordal Graphs: From Cops and Robber to Compact Routing via Treewidth 
Type 

Year 
2015 
Publication 
Algorithmica 
Abbreviated Journal 
Algorithmica 
Volume 
72 
Issue 
3 
Pages 
758777 
Keywords 
Treewidth; Chordality; Compact routing; Cops and robber games 
Abstract 
Cops and robber games, introduced by Winkler and Nowakowski (in Discrete Math. 43(23), 235239, 1983) and independently defined by Quilliot (in J. Comb. Theory, Ser. B 38(1), 8992, 1985), concern a team of cops that must capture a robber moving in a graph. We consider the class of kchordal graphs, i.e., graphs with no induced (chordless) cycle of length greater than k, ka parts per thousand yen3. We prove that k1 cops are always sufficient to capture a robber in kchordal graphs. This leads us to our main result, a new structural decomposition for a graph class including kchordal graphs. We present a polynomialtime algorithm that, given a graph G and ka parts per thousand yen3, either returns an induced cycle larger than k in G, or computes a treedecomposition of G, each bag of which contains a dominating path with at most k1 vertices. This allows us to prove that any kchordal graph with maximum degree Delta has treewidth at most (k1)(Delta1)+2, improving the O(Delta(Delta1) (k3)) bound of Bodlaender and Thilikos (Discrete Appl. Math. 79(13), 4561, 1997. Moreover, any graph admitting such a treedecomposition has small hyperbolicity). As an application, for any nvertex graph admitting such a treedecomposition, we propose a compact routing scheme using routing tables, addresses and headers of size O(klog Delta+logn) bits and achieving an additive stretch of O(klog Delta). As far as we know, this is the first routing scheme with O(klog Delta+logn)routing tables and small additive stretch for kchordal graphs. 
Address 
[Kosowski, A.] INRIA, LaBRI, CEPAGE, Talence, France, Email: bi.li@inria.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:000355939800004 
Approved 

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