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

A self-stabilizing algorithm for the shortest path problem in a distributed system

COMPUTERS & MATHEMATICS WITH APPLICATIONS 2002年第1-2期43卷 103-109页

作者： Huang, TC Lin, JC Yuan Ze Univ Dept Comp Engn & Sci Chung Li Taoyuan 32026 Taiwan

In this paper, we propose a self-stabilizing algorithm for finding shortest paths in a distributed system in which a central daemon is assumed. The correctness of the proposed algorithm is proved by using the bounded ... 详细信息

关键词： central daemon self-stabilizing algorithm shortest paths distance turn nodes bounded function predecessors

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A 4n-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon

引用

INFORMATION PROCESSING LETTERS 2014年第10期114卷 515-518页

作者： Chiu, Well Y. Chen, Chiuyuan Tsai, Shih-Yu Natl Chiao Tung Univ Dept Appl Math Hsinchu 30010 Taiwan

A distributed system is self-stabilizing if, regardless of its initial state, the system is guaranteed to reach a legitimate (i.e., correct) state in finite time. In 2007, Turau proposed the first linear-time self-stabilizing algorithm for the minimal dominating set (MDS) problem under an unfair distributed daemon [9];this algorithm stabilizes in at most 9n moves, where n is the number of nodes in the system. In 2008, Goddard et al. [4] proposed a 5n-move algorithm. In this paper, we present a 4n-move algorithm. (C) 2014 Elsevier B.V. All rights reserved.

关键词： self-stabilizing algorithm Fault tolerance Distributed computing Graph algorithm Domination

来源：评论

学校读者我要写书评

暂无评论

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 algorithm for the shortest path problem assuming the distributed demon

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 2005年第5-6期50卷 671-681页

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

Shortest path finding has a variety of applications in transportation and communication. In this paper, we study a well-known self-stabilizing algorithm for the shortest path problem for the distributed systems. The previous works on this topic had two assumptions that can be relaxed in this paper. First, in the previous works, the systems were assumed to be integral-weighted, whereas in this paper, the systems are real-weighted. Second, and more importantly, the previous works have shown that the algorithm is self-stabilizing under the more restricted central demon model, whereas in this paper, we give a rigorous proof showing that the algorithm is actually self-stabilizing under the more general distributed demon model. The work in this paper is of significance because in the existing literature on self-stabilizing systems, most of the papers regarding the distributed demon are for the ring networks only;there are very few papers that discuss the self-stabilizing algorithms for the general distributed systems assuming the distributed demon model. (c) 2005 Elsevier Ltd. All rights reserved.

关键词： real-weighted system distributed demon shortest path problem bounded function technique self-stabilizing algorithm

来源：评论

学校读者我要写书评

暂无评论

A self-stabilizing algorithm for the Median Problem in Partial Rectangular Grids and Their Relatives

引用

algorithmICA 2012年第1-2期62卷 146-168页

作者： Chepoi, Victor Fevat, Tristan Godard, Emmanuel Vaxes, Yann Aix Marseille Univ LIF Lab Informat Fondamentale Marseille CNRS UMR 6166 Marseille France

Given a graph G=(V,E), a vertex v of G is a median vertex if it minimizes the sum of the distances to all other vertices of G. The median problem consists of finding the set of all median vertices of G. In this note, we present self-stabilizing algorithms for the median problem in partial rectangular grids and relatives. Our algorithms are based on the fact that partial rectangular grids can be isometrically embedded into the Cartesian product of two trees, to which we apply the algorithm proposed by Antonoiu and Srimani (J. Comput. Syst. Sci. 58:215-221, 1999) and Bruell et al. (SIAM J. Comput. 29:600-614, 1999) for computing the medians in trees. Then we extend our approach from partial rectangular grids to a more general class of plane quadrangulations. We also show that the characterization of medians of trees given by Gerstel and Zaks (Networks 24:23-29, 1994) extends to cube-free median graphs, a class of graphs which includes these quadrangulations.

关键词： self-stabilizing algorithm Median problem Isometric embedding Rectangular grid

来源：评论

学校读者我要写书评

暂无评论

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 algorithm for Maximal p-Star Decomposition of General Graphs

A Self-stabilizing Algorithm for Maximal p-Star Decompositio...

引用

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

作者： Neggazi, Brahim Turau, Volker Haddad, Mohammed Kheddouci, Hamamache Univ Lyon 1 CNRS UMR5205 LIRIS 43 Bd 11 Novembre 1918 F-69622 Villeurbanne France Hamburg Univ Technol Inst Telemat D-21073 Hamburg Germany

ISBN: (纸本)9783319030890;9783319030883

A p-star is a complete bipartite graph K-1, (p) with one center node and p leaf nodes. In this paper we propose the first distributed self-stabilizing algorithm for graph decomposition into p-stars. For a graph G and an integer p >= 1, this decomposition provides disjoint components of G where each component forms a p-star. We prove convergence and correctness of the algorithm under an unfair distributed daemon. The stabilization time is 2 [n/p+1] + 2 rounds.

关键词： Graph decomposition stars generalized matching master-slave model self-stabilizing algorithm

来源：评论

学校读者我要写书评

暂无评论

A self-stabilizing algorithm for finding the cutting center of a tree

A self-stabilizing algorithm for finding the cutting center ...

引用

International Conference on Parallel and Distributed Processing Techniques and Applications

作者： Chaudhuri, P Thompson, H Univ W Indies Dept Comp Sci Math & Phys Bridgetown Barbados

ISBN: (纸本)1892512459

The cutting number of a node i in a connected graph G is the number of pairs of nodes in different components of G - {i}. The cutting center consists of the set of nodes of G with maximal cutting number. This paper presents a self-stabilizing algorithm for finding the cutting numbers for all nodes of a tree T = < V-T;E-T> and hence the cutting center of T It is shown that the proposed self-stabilizing algorithm requires O(n(2)) moves. The algorithm complexity can also be expressed as O(n) rounds.

关键词： distributed system self-stabilizing algorithm tree cutting center complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：