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

A self-stabilizing algorithm for a Maximal 2-Packing in a Cactus Graph Under Any Scheduler

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2017年第8期28卷 1021-1045页

作者： Antonio Trejo-Sanchez, Joel Alberto Fernandez-Zepeda, Jose Cesar Ramirez-Pacheco, Julio Ctr Invest Matemat AC CONACYT CIMAT Merida Merida 97032 Yucatan Mexico CICESE Dept Comp Sci Carretera Ensenada Tijuana 3918 Ensenada 22860 Baja California Mexico Univ Caribe Dept Basic Sci SM 78Mza 1Lote 1 Cancun 77528 QR Mexico

In this paper, we present a self-stabilizing algorithm that computes a maximal 2-packing set in a cactus under the adversarial scheduler. The cactus is a network topology such that any edge belongs to at most one cycle. The cactus has important applications in telecommunication networks, location problems, and biotechnology, among others. We assume that the value of each vertex identifier can take any value of length O(logn) bits. The execution time of this algorithm is O(n) rounds or O(n(2)) time steps. Our algorithm matches the state of the art results for this problem, following an entirely different approach. Our approach allows the computation of the maximum 2-packing when the cactus is a ring.

关键词： self-stabilizing algorithm cactus graph adversarial scheduler 2-packing set

来源：评论

学校读者我要写书评

暂无评论

A self-stabilizing algorithm for finding a minimal positive influence dominating set in social networks 13

A self-stabilizing algorithm for finding a minimal positive ...

引用

Proceedings of the Twenty-Fourth Australasian Database Conference - Volume 137

作者： Guangyuan Wang Hua Wang Xiaohui Tao Ji Zhang University of Southern Queensland QLD Australia

ISBN: (纸本)9781921770227

Online social network has developed significantly in recent years. Most of current research has utilized the property of online social network to spread information and ideas. Motivated by applications in social networks (such as alcohol intervention strategies), a variation of the dominating set called a positive influence dominating set (PIDS) has been studied in the literature. However, the existing work all focused on greedy algorithms for the PIDS problem with different approximation ratios, which are limited to find approximate solutions to PIDS in large networks. In order to select a minimal PIDS (MPIDS) in large social networks, we first present a self-stabilizing algorithm for the MPIDS problem in this paper, which can find a MPIDS in an arbitrary network graph without any isolated node. It is assumed that the nodes in the proposed algorithm have globally unique identifiers, and the algorithm works under a central daemon. We further prove that the worst case convergence time of the algorithm from any arbitrary initial state is O(n2) steps where n is the number of nodes in the network.

关键词： minimal positive influence dominating set self-stabilizing algorithm graph algorithm

来源：评论

学校读者我要写书评

暂无评论

A self-stabilizing graph algorithm: Finding the cutting center of a tree

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2004年第2期81卷 183-190页

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

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 article 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

来源：评论

学校读者我要写书评

暂无评论

A self-stabilizing DISTRIBUTED algorithm TO CONSTRUCT AN ARBITRARY SPANNING TREE OF A CONNECTED GRAPH

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 1995年第9期30卷 1-7页

作者： ANTONOIU, G SRIMANI, PK COLORADO STATE UNIV DEPT COMP SCIFT COLLINSCO 80523

We propose a simple self-stabilizing distributed algorithm that maintains an arbitrary spanning tree in a connected graph. In proving the correctness of the algorithm, we develop a new technique without using a bounded function (which is customary for proving correctness of self-stabilizing algorithms);the new approach is simple and can be potentially applied to proving correctness of other self-stabilizing algorithms.

关键词： self-stabilizing algorithm DISTRIBUTED DEMON SPANNING TREE CORRECTNESS PROOF ANALYSIS

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A self-stabilizing distributed algorithm for the Steiner tree problem

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2004年第2期E87D卷 299-307页

作者： Kamei, S Kakugawa, H Hiroshima Univ Dept Informat Engn Higashihiroshima 7398527 Japan

self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. In this paper, we investigate the Steiner tree problem in distributed systems, and propose a self-stabilizing heuristic solution to the problem. Our algorithm is constructed by four layered modules (sub-algorithms): construction of a shortest path forest, transformation of the network, construction of a minimum spanning tree, and pruning unnecessary links and processes. Competitiveness is 2(1 - 1/l), where l is the number of leaves of optimal solution.

关键词： distributed algorithm fault-tolerant self-stabilizing algorithm fair composition Steiner tree problem

来源：评论

学校读者我要写书评

暂无评论

self-stabilizing algorithms for minimal dominating sets and maximal independent sets

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 2003年第5-6期46卷 805-811页

作者： Hedetniemi, SM Hedetniemi, ST Jacobs, DP Srimani, PK Clemson Univ Dept Comp Sci Clemson SC 29634 USA

In the self-stabilizing algorithmic paradigm for distributed computation, each node has only a local view of the system, yet in a finite amount of time, the system converges to a global state satisfying some desired property. In this paper, we present polynomial time self-stabilizing algorithms for finding a dominating bipartition, a maximal independent set, and a minimal dominating set in any graph. (C) 2003 Elsevier Ltd. All rights reserved.

关键词： graph self-stabilizing algorithm dominating set independent set

来源：评论

学校读者我要写书评

暂无评论

self-stabilizing algorithmS FOR UNFRIENDLY PARTITIONS INTO TWO DISJOINT DOMINATING SETS

引用

PARALLEL PROCESSING LETTERS 2013年第1期23卷

作者： Hedetniemi, Sandra M. Hedetniemi, Stephen T. Kennedy, K. E. McRae, Alice A. Clemson Univ Sch Comp Clemson SC 29634 USA Southern Wesleyan Univ Dept Comp Sci Central SC 29630 USA Appalachian State Univ Dept Comp Sci Boone NC 28608 USA

An unfriendly partition is a partition of the vertices of a graph G = (V,E) into two sets, say Red R(V) and Blue B(V), such that every Red vertex has at least as many Blue neighbors as Red neighbors, and every Blue vertex has at least as many Red neighbors as Blue neighbors. We present three polynomial time, self-stabilizing algorithms for finding unfriendly partitions in arbitrary graphs G, or equivalently into two disjoint dominating sets.

关键词： self-stabilizing algorithm unfriendly partitions disjoint dominating sets

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：