检索结果-内蒙古大学图书馆

A self-stabilizing algorithm for Finding a Minimal Distance-2 Dominating Set in Distributed Systems

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2008年第6期24卷 1709-1718页

作者： Lin, Ji-Cherng Huang, Tetz C. Wang, Cheng-Pin Chen, Chih-Yuan Yuan Ze Univ Dept Comp Sci & Engn Chungli 320 Taiwan Nanya Inst Technol Dept Comp Sci & Informat Engn Chungli 320 Taiwan

The study of various dominating set problems is an important area within graph theory. In applications, a dominating set in a system can be considered as an ideal place for allocating resources. And, a minimal dominating set allows allocating a smaller number of resources. Distance-versions of the concept of minimal dominating sets are more applicable to modeling real-world problems, such as placing a smaller number of objects within acceptable distances of a given population. However, due to the main restriction that any processor in a distributed system can only access the data of its direct neighbors, a self-stabilizing algorithm for finding a minimal distance-k (with k >= 2) dominating set is hard to get, and its correctness is hard to verify. In this paper, a self-stabilizing algorithm for finding a minimal distance-2 dominating set is proposed. The algorithm can be applied to any distributed system that operates under the central demon model. The correctness of the algorithm is verified.

关键词： minimal distance-2 dominating set self-stabilizing algorithm Dijkstra's central demon model distributed system legitimate configuration

来源：评论

学校读者我要写书评

暂无评论

A linear-time self-stabilizing algorithm for the minimal 2-dominating set problem in general networks

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2008年第1期24卷 175-187页

作者： Huang, Tetz C. Chen, Chin-Yuan Wang, Cheng-Pin Yuan Ze Univ Dept Comp Engn & Sci Chungli 320 Taiwan

Kamei and Kakugawa have recently proposed a self-stabilizing algorithm for the minimal k-dominating set problem. Their algorithm is a general form of the maximal-independent-set algorithm proposed by Shukla et al. The results in their paper are for any tree network that assumes Dijkstra's central demon model. In particular, the worst-case stabilization time is claimed to be O(n(2)), where n is the number of nodes in the system. In this paper, we generalize their results for the case k = 2. We show that their algorithm with k = 2, when operating in any general network, is self-stabilizing under the central demon model, and solves the minimal 2-dominating set problem. We also derive that the worst-case stabilization time is linear, i.e., O(n). A bounded function technique is employed in obtaining these results.

关键词： self-stabilizing algorithm central demon model maximal independent set minimal k-dominating set tree network general network bounded function cut point

来源：评论

学校读者我要写书评

暂无评论

Distance-2 self-stabilizing algorithm for a b-Coloring of Graphs

Distance-2 Self-stabilizing Algorithm for a b-Coloring of Gr...

引用

10th International Symposium on Stabilization, Safety and Security of Distributed Systems (SSS 2008)

作者： Dekar, Lyes Kheddouci, Hamamache Univ Lyon 1 Lab LIESP IUTA Dept Informat 71 Rue Peter Fink F-01000 Bourg En Bresse France Univ Lyon 1 Univ Lyon Lab LIESP F-69622 Villeurbanne France

ISBN: (纸本)9783540893349

A b-coloring of a graph G is a proper k-coloring of G such that for each color i, <= i <= k at least one vertex colored with i is adjacent to every color j, with 1 <= j not equal i <= k. This kind of coloring is useful to decompose any system into communities, where each community contains a vertex adjacent to all the other communities. This kind of organization can provide improving in many fields, especially in the data clustering. In this paper we propose a new self-stabilizing algorithm for finding a b-coloring of arbitrary undirected connected graphs. Because the characteristics of the b-coloring problem, the proposed self-stabilizing algorithm use a distance-2 knowledge.

关键词： b-coloring self-stabilizing algorithm clustering data mining graphs

来源：评论

学校读者我要写书评

暂无评论

A self-stabilizing 2/3-approximation algorithm for the maximum matching problem

引用

THEORETICAL COMPUTER SCIENCE 2011年第40期412卷 5515-5526页

作者： Manne, Fredrik Mjelde, Morten Pilard, Laurence Tixeuil, Sebastien Univ Bergen N-5020 Bergen Norway Univ Franche Comte F-25030 Besancon France Univ Paris 06 LIP6 F-75252 Paris 05 France Univ Paris 06 INRIA Grand Large F-75252 Paris 05 France

The matching problem asks for a large set of disjoint edges in a graph. It is a problem that has received considerable attention in both the sequential and the self-stabilizing literature. Previous work has resulted in self-stabilizing algorithms for computing a maximal (1/2-approximation) matching in a general graph, as well as computing a 2/3-approximation on more specific graph types. In this paper, we present the first self-stabilizing algorithm for finding a 2/3-approximation to the maximum matching problem in a general graph. We show that our new algorithm, when run under a distributed adversarial daemon, stabilizes after at most 0(n(2)) rounds. However, it might still use an exponential number of time steps. (C) 2011 Elsevier B.V. All rights reserved.

关键词： self-stabilizing algorithm 2/3-approximation Maximum matching

来源：评论

学校读者我要写书评

暂无评论

Improved self-stabilizing algorithms for L(2, 1)-Labeling Tree Networks

引用

MATHEMATICS IN COMPUTER SCIENCE 2011年第1期5卷 27-39页

作者： Chaudhuri, Pranay Thompson, Hussein Jaypee Univ Informat Technol Dept Comp Sci & Engn Waknaghat 173215 Solan India Univ West Indies Dept Comp Sci Math & Phys Bridgetown Barbados

The L(2, 1)-labeling problem for a graph G is a variation of the standard graph coloring problem. Here, we seek to assign a label (color) to each node of G such that nodes a distance of two apart are assigned unique labels and adjacent nodes receive labels which are at least two apart. In a previous paper-presented at the 23rd IASTED International Multi-Conference: Parallel and Distributed Computing and Networks, Innsbruck, Austria-we presented, to the best of our knowledge, the first self-stabilizing algorithm which {Delta + 2}-L(2, 1)-labels rooted trees. That algorithm was shown to require an exponential number of moves to stabilize on a global solution (which is not uncommon in self-stabilizing systems). In this paper, we present two self-stabilizing algorithms which {Delta + 2}-L(2, 1)-label a given rooted tree T in only O(nh) moves (where h is the height and n is the number of nodes in the tree T) under a central scheduler. We also show how the algorithms may be adapted to unrooted trees, dynamic topology changes, and consider the correctness of the protocols under the distributed scheduler model.

关键词： Distributed system self-stabilizing algorithm L(2, 1)-labeling Graph coloring Complexity Tree

来源：评论

学校读者我要写书评

暂无评论

A self-stabilizing Marching algorithm for a Group of Oblivious Robots

A Self-stabilizing Marching Algorithm for a Group of Oblivio...

引用

12th International Conference on Principles of Distributed Systems

作者： Asahiro, Yuichi Fujita, Satoshi Suzuki, Ichiro Yamashita, Masafumi Kyushu Sangyo Univ Fac Informat Sci Dept Social Informat Syst Higashi Ku 2-3-1 Matsukadai Fukuoka 8138503 Japan Hiroshima Univ Dept Elect Engn Fac Engn Hiroshima 7398527 Japan Univ Wisconsin Dept Elect Engn & Comp Sci Milwaukee WI 53201 USA Kyushu Univ Dept Comp Sci & Commun Engn Nishi Ku Fukuoka 8190395 Japan

ISBN: (纸本)9783540922209

We propose a self-stabilizing marching algorithm for a group of oblivious robots in an obstacle-free workplace. To this end, we develop a distributed algorithm for a group of robots to transport a polygonal object, where each robot holds the object at a corner, and observe that each robot can simulate the algorithm, even after we replace the object by an imaginary one;we thus can use the algorithm as a marching algorithm. Each robot independently computes a velocity vector using the algorithm, moves to a new position with the velocity for a unit of time, and repeats this cycle until it reaches the goal position. The algorithm is oblivious, i.e., the computation depends only on the current robot configuration, and is constructed from a naive algorithm that generates only a selfish move, by adding two simple ingredients. For the case of two robots, we theoretically show that the algorithm is self-stabilizing, and demonstrate by simulations that the algorithm produces a motion that is fairly close to the time-optimal motion. For cases of more than two robots, we show that a natural extension of the algorithm for two robots also produces smooth and elegant motions by simulations as well.

关键词： motion coordination marching flocking self-stabilizing algorithm oblivious algorithm

来源：评论

学校读者我要写书评

暂无评论

An improved self-stabilizing algorithm for biconnectivity and bridge-connectivity

引用

INFORMATION PROCESSING LETTERS 2007年第1期102卷 27-34页

作者： Tsin, Yung H. Univ Windsor Sch Comp Sci Windsor ON N9B 3P4 Canada

The functionality of a self-stabilizing algorithm for determining cut-vertices and biconnected components of distributed computer networks, are discussed. A self-stabilizing algorithm is a distributed algorithm that determines all the bridges and determines all bridge-connected components. It is a modification of the self-stabilizing depth-first search algorithm of Collin and Dolev and it is a adaptation of Tarjan's sequential algorithm for biconnectivity to the self-stabilizing model. The time complexity and memory requirement of the algorithm is similar to that of the depth-first spanning tree algorithm. The algorithm require O(m log n) bits per processor and it efficiently determines bridge-connected components in comparison of Chaudhari's composite algorithm for bridge-connected components. It determines biconnected components of distributed computer networks using spanning subtrees.

关键词： self-stabilizing algorithm fault tolerance distributed computing distributed algorithm cut-vertex biconnected component bridge bridge-connected component

来源：评论

学校读者我要写书评

暂无评论

A self-stabilizing algorithm for finding a minimal 2-dominating set assuming the distributed demon model

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 2007年第3期54卷 350-356页

作者： Huang, Tetz C. Lin, Ji-Cherng Chen, Chih-Yuan Wang, Cheng-Pin Yuan Ze Univ Dept Comp Sci & Engn Chungli 320 Taiwan

A 2-dominating set in a distributed system is a set of processors such that each processor outside the set has at least two neighbors in the set. In applications, a 2-dominating set can be considered as an ideal place in the system for allocating resources, and a minimal 2-dominating set allows for the minimum of resources to be allocated. Since a maximal independent set can be viewed as a minimal 1-dominating set, the problem of finding a minimal 2-dominating set extends the problem of finding a maximal independent set in some sense. The distributed demon model for self-stabilizing systems is a natural generalization of the central demon model introduced by Dijkstra. In the past, only a few self-stabilizing algorithms under the distributed demon model have been obtained without using any transformer, and most of these algorithms are for ring networks only. In this paper, we propose a self-stabilizing algorithm that can find a minimal 2-dominating set in any general network in which the distributed demon model is assumed. This proposed algorithm is not obtained via any transformer. We also verify the correctness of the proposed algorithm. (c) 2007 Elsevier Ltd. All rights reserved.

关键词： self-stabilizing algorithm minimal 2-dominating set central demon model distributed demon model cut point

来源：评论

学校读者我要写书评

暂无评论

A self-stabilizing DISTRIBUTED APPROXIMATION algorithm FOR THE MINIMUM CONNECTED DOMINATING SET

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2010年第3期21卷 459-476页

作者： Kamei, Sayaka Kakugawa, Hirotsugu Hiroshima Univ Dept Informat Engn Hiroshima 7398527 Japan Osaka Univ Dept Comp Sci Osaka 5608531 Japan

self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. A self-stabilizing system tolerates any kind and any finite number of transient faults, such as message loss, memory corruption, and topology change. Because such transient faults occur so frequently in mobile ad hoc networks, distributed algorithms on them should tolerate such events. In this paper, we propose a self-stabilizing distributed approximation algorithm for the minimum connected dominating set, which can be used, for example, as a virtual backbone or routing in mobile ad hoc networks. The size of the solution by our algorithm is at most 7.6 vertical bar D-opt vertical bar + 1.4, where D-opt is the minimum connected dominating set. The time complexity is O(k) rounds, where k is the depth of input BFS tree.

关键词： self-stabilizing algorithm approximation algorithm ad hoc network minimum connected dominating set fault-tolerant

来源：评论

学校读者我要写书评

暂无评论

An efficient fault-containing self-stabilizing algorithm for the shortest path problem

引用

DISTRIBUTED COMPUTING 2006年第2期19卷 149-161页

作者： Huang, Tetz C. Yuan Ze Univ Dept Comp Sci & Engn Taoyuan 320 Taiwan

Shortest path finding has a variety of applications in transportation and communication. In this paper, we propose a fault-containing self-stabilizing algorithm for the shortest path problem in a distributed system. The improvement made by the proposed algorithm in stabilization times for single-fault situations can demonstrate the desirability of an efficient fault-containing self-stabilizing algorithm. For single-fault situations, the worst-case stabilization time of the proposed algorithm is O(Delta), where Delta is the maximum node degree in the system, and the contamination number of the proposed algorithm is 1.

关键词： self-stabilizing algorithm fault-containment single-fault situation stabilization time shortest path problem

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：