Optimal irreversible dynamos in chordal rings

被引:33
作者
Flocchini, P
Geurts, F
Santoro, N
机构
[1] Univ Ottawa, Sch Informat Technol & Engn, Stn A, Ottawa, ON K1N 6N5, Canada
[2] Free Univ Brussels, Dept Informat, B-1050 Brussels, Belgium
[3] Carleton Univ, Sch Comp Sci, Ottawa, ON K1S 5B6, Canada
关键词
majority rule; dynamic monopolies; chordal rings;
D O I
10.1016/S0166-218X(00)00388-7
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
In this paper, we study the effect of a simple majority rule on two classes of chordal rings: weakly and strongly chorded rings. In the case of weakly chorded rings, we establish a lower bound on the weight of optimal dynamos and we prove that the bound is tight with a constructive upper bound; we also provide a complete characterization of the optimal dynamos for the well-known class of double- and triple-loop networks. Also in the case of strongly chorded rings, we establish tight bounds and show how to construct optimal dynamos. (C) 2001 Elsevier Science BN. All rights reserved.
引用
收藏
页码:23 / 42
页数:20
相关论文
共 22 条
[1]   THE NUMBER OF FIXED-POINTS OF THE MAJORITY-RULE [J].
AGUR, Z ;
FRAENKEL, AS ;
KLEIN, ST .
DISCRETE MATHEMATICS, 1988, 70 (03) :295-302
[2]   EFFICIENT ELECTIONS IN CHORDAL RING NETWORKS [J].
ATTIYA, H ;
VANLEEUWEN, J ;
SANTORO, N ;
ZAKS, S .
ALGORITHMICA, 1989, 4 (03) :437-446
[3]   DISTRIBUTED LOOP COMPUTER-NETWORKS - A SURVEY [J].
BERMOND, JC ;
COMELLAS, F ;
HSU, DF .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1995, 24 (01) :2-10
[4]  
BERMOND JC, 1996, P 3 C STRUCT INF COM, P170
[5]  
De Prisco R, 1998, THEOR COMPUT SCI, V197, P171, DOI 10.1016/S0304-3975(97)00238-7
[6]  
FLOCCHINI F, 2000, P EUROPAR 98
[7]  
FLOCCHINI P, 1999, P 6 COLL STRUCT INF, P152
[8]   PERIODIC BEHAVIOR OF GENERALIZED THRESHOLD FUNCTIONS [J].
GOLES, E ;
OLIVOS, J .
DISCRETE MATHEMATICS, 1980, 30 (02) :187-189
[9]  
Goles E., 1990, Neural and Automata Networks, DOI 10.1007/978-94-009-0529-0
[10]  
KRIZANC D, 1995, P 2 COLL STRUCT INF