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

International Conference and Workshops on Networked Systems (NetSys)

作者： Markus Benter Mohammad Divband Sebastian Kniesburges Andreas Koutsopoulos Kalman Graffi Algorithms and Complexity Group University of Paderborn Germany Universitat Paderborn Paderborn Nordrhein-Westfalen DE Theory of Distributed Systems Group University of Paderborn Germany Technology of Social Networks Group University of Düsseldorf Germany

Self-stabilization is the property of a system to transfer itself regardless of the initial state into a legitimate state. Chord as a simple, decentralized and scalable distributed hash table is an ideal showcase to introduce self-stabilization for p2p overlays. In this paper, we present Re-Chord, a self-stabilizing version of Chord. We show, that the stabilization process is functional, but prone to strong churn. For that, we present Ca-Re-Chord, a churn resistant version of Re-Chord, that allows the creation of a useful DHT in any kind of graph regardless of the initial state. Simulation results attest the churn resistance and good performance of Ca-Re-Chord.

关键词： Peer-to-peer computing Resistance Routing Robustness Overlay networks Social network services Educational institutions

来源：评论

学校读者我要写书评

暂无评论

A spiking neural P system simulator based on CUDA

A spiking neural P system simulator based on CUDA

引用

12th International Conference on Membrane Computing, CMC 2011

作者： Cabarle, Francis George C. Adorna, Henry Martínez, Miguel A. Algorithms and Complexity Lab. Department of Computer Science University of the Philippines Diliman Diliman 1101 Quezon City Philippines Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Seville Avda. Reina Mercedes s/n 41012 Sevilla Spain

ISBN: (纸本)9783642280238

In this paper we present a Spiking Neural P system (SNP system) simulator based on graphics processing units (GPUs). In particular we implement the simulator using NVIDIA CUDA enabled GPUs. The massively parallel architecture of current GPUs is very suitable for the maximally parallel computations of SNP systems. We simulate a wider variety of SNP systems, after presenting a previous work on SNP system matrix representation which led to their simulation in GPUs, and the simulation algorithm included here. Finally, we compare and present the performance speedups of the CPU-GPU based simulator over the CPU only simulator. © 2012 Springer-Verlag.

关键词： Graphics processing unit

来源：评论

学校读者我要写书评

暂无评论

Coloring random graphs online without creating monochromatic subgraphs 11

Coloring random graphs online without creating monochromatic...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Torsten Mutze Thomas Rast Reto Spohel Institute of Theoretical Computer Science Algorithms and Complexity Group

ISBN: (纸本)9780898719932

Consider the following generalized notion of graph coloring: a coloring of the vertices of a graph G is valid w.r.t. some given graph F if there is no copy of F in G whose vertices all receive the same color. We study the problem of computing valid colorings of the binomial random graph G_(n,p) on n vertices with edge probability p = p(n) in the following online setting: the vertices of an initially hidden instance of G_(n,p) are revealed one by one (together with all edges leading to previously revealed vertices) and have to be colored immediately and irrevocably with one of r available colors. It is known that for any fixed graph F and any fixed integer r≥2 this problem has a threshold p0(F, r, n) in the following sense: For any function p(n) = o(p0) there is a strategy that a.a.s. (asymptotically almost surely, i.e., with probability tending to 1 as n tends to infinity) finds an r-coloring of G_(n,p) that is valid w.r.t. F online, and for any function p(n)=ω(p0) any online strategy will a.a.s. fail to do so. In this work we establish a general correspondence between this probabilistic problem and a deterministic twoplayer game in which the random process is replaced by an adversary that is subject to certain restrictions inherited from the random setting. This characterization allows us to compute, for any F and r, a valueγ=γ(F,r) such that the threshold of the probabilistic problem is given by p0(F, r, n) = n~(-γ). Our approach yields polynomial-time coloring algorithms that a.a.s. find valid colorings of G_(n,p) online in the entire regime below the respective thresholds, i.e., for any p(n) = o(n~(-γ)).

关键词： Color Fluorine (F) vertex head Valid AASS gene colored graph Line graph Probability Stochastic Processes

来源：评论

学校读者我要写书评

暂无评论

On Balanced Coloring Games in Random Graphs

引用

Electronic Notes in Discrete Mathematics 2011年 38卷 425-430页

作者： Gugelmann, Luca Spöhel, Reto Institute of Theoretical Computer Science ETH Zürich 8092 Zürich Switzerland Algorithms and Complexity Group Max-Planck-Institut für Informatik 66123 Saarbrücken Germany

Consider the balanced Ramsey game, in which a player has r colors and where in each round r random edges of an initially empty graph on n vertices are presented. The player has to immediately assign a different color to each edge and her goal is to avoid creating a monochromatic copy of some fixed graph F for as long as possible. The Achlioptas game is similar, but the player only loses when she creates a copy of F in one distinguished color. We show that there is an infinite family of nonforests F for which the balanced Ramsey game has a different threshold than the Achlioptas game, settling an open question by Krivelevich et al. We also consider the natural vertex analogues of both games and show that their thresholds coincide for all graphs F, in contrast to our results for the edge case. © 2011 Elsevier B.V.

关键词： Coloring games Ramsey theory Random graphs

来源：评论

学校读者我要写书评

暂无评论

On the path-avoidance vertex-coloring game

引用

Electronic Notes in Discrete Mathematics 2011年 38卷 657-662页

作者： Mütze, Torsten Spöhel, Reto Institute of Theoretical Computer Science ETH Zürich 8092 Zürich Switzerland Algorithms and Complexity Group Max-Planck-Institut für Informatik 66123 Saarbrücken Germany

For any graph F and any integer r≥2, the online vertex-Ramsey density of F and r, denoted m*(F, r), is a parameter defined via a deterministic two-player Ramsey-type game (Painter vs. Builder). This parameter was int... 详细信息

For any graph F and any integer r≥2, the online vertex-Ramsey density of F and r, denoted m^*(F, r), is a parameter defined via a deterministic two-player Ramsey-type game (Painter vs. Builder). This parameter was introduced in a recent paper [Mütze, T., T. Rast and R. Spöhel, Coloring random graphs online without creating monochromatic subgraphs, in: Proceedings of the 22nd annual ACM-SIAM Symposium on Discrete algorithms (SODA '11), 2011, pp. 145-158], where it was shown that the online vertex-Ramsey density determines the threshold of a similar probabilistic one-player game (Painter vs. the binomial random graph G_n,p). For a large class of graphs F, including cliques, cycles, complete bipartite graphs, hypercubes, wheels, and stars of arbitrary size, a simple greedy strategy is optimal for Painter and closed formulas for m^*(F, r) are *** this work we show that in the innocent-looking case where F=P_ℓ is a (long) path, the picture is very different. As it turns out, for this family of graphs the greedy strategy fails quite badly, and the parameter m^*(F, r) exhibits a much more complex behavior than one might expect in view of the other examples mentioned. © 2011 Elsevier B.V.

关键词： Online process Ramsey property Random graph

来源：评论

学校读者我要写书评

暂无评论

An improved GPU simulator for Spiking Neural P systems

An improved GPU simulator for Spiking Neural P systems

引用

6th International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA 2011

作者： Cabarle, Francis George C. Adorna, Henry Martínez-Del-Amor, Miguel A. Algorithms and Complexity Lab. Dept. of Computer Science University of the Philippines Diliman Philippines Research Group on Natural Computing Dept. of Computer Science and AI University of Seville Spain

ISBN: (纸本)9780769545141

Spiking Neural P (SNP) systems, variants of P systems (under Membrane and Natural computing), are computing models that acquire abstraction and inspiration from the way neurons 'compute' or process information. Similar to other P system variants, SNP systems are Turing complete models that by nature compute non-deterministically and in a maximally parallel manner. P systems usually trade (often exponential) space for (polynomial to constant) time. Due to this nature, P system variants are currently limited to parallel simulations, and several variants have already been simulated in parallel devices. In this paper we present an improved SNP system simulator based on graphics processing units (GPUs). Among other reasons, current GPUs are architectured for massively parallel computations, thus making GPUs very suitable for SNP system simulation. The computing model, hardware/software considerations, and simulation algorithm are presented, as well as the comparisons of the CPU only and CPU-GPU based simulators. © 2011 IEEE.

关键词： Graphics processing unit

来源：评论

学校读者我要写书评

暂无评论

Coloring random graphs online without creating monochromatic subgraphs

Coloring random graphs online without creating monochromatic...

引用

作者： Mütze, Torsten Rast, Thomas Spöhel, Reto Institute of Theoretical Computer Science ETH Zürich 8092 Zürich Switzerland Algorithms and Complexity Group Max-Planck-Institut für Informatik 66123 Saarbrücken Germany

ISBN: (纸本)9780898719932

Consider the following generalized notion of graph coloring: a coloring of the vertices of a graph G is valid w.r.t. some given graph F if there is no copy of F in G whose vertices all receive the same color. We study the problem of computing valid colorings of the binomial random graph Gn,p on n vertices with edge probability p = p(n) in the following online setting: the vertices of an initially hidden instance of Gn,p are revealed one by one (together with all edges leading to previously revealed vertices) and have to be colored immediately and irrevocably with one of r available colors. It is known that for any fixed graph F and any fixed integer r ≥ 2 this problem has a threshold p0(F,r,n) in the following sense: For any function p(n) = o(p0) there is a strategy that a.a.s. (asymptotically almost surely, i.e., with probability tending to 1 as n tends to infinity) finds an r-coloring of Gn,p that is valid w.r.t. F online, and for any function p(n) = ω(p0) any online strategy will a.a.s. fail to do so. In this work we establish a general correspondence between this probabilistic problem and a deterministic two-player game in which the random process is replaced by an adversary that is subject to certain restrictions inherited from the random setting. This characterization allows us to compute, for any F and r, a value γ = γ(F,r) such that the threshold of the probabilistic problem is given by p0(F,r,n) = nγ. Our approach yields polynomial-time coloring algorithms that a.a.s. find valid colorings of Gn,p online in the entire regime below the respective thresholds, i.e., for any p(n) = o(n-γ).

关键词： Coloring

来源：评论

学校读者我要写书评

暂无评论

Spiking neural P system simulations on a high performance GPU platform

Spiking neural P system simulations on a high performance GP...

引用

11th International Conference on algorithms and Architectures for Parallel Processing, ICA3PP 2011

作者： Cabarle, Francis George Adorna, Henry Martínez-Del-Amor, Miguel A. Pérez-Jiménez, Mario J. Algorithms and Complexity Lab. Department of Computer Science University of the Philippines Diliman Quezon City Diliman 1101 Philippines Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Seville Avda. Reina Mercedes s/n Sevilla 41012 Spain

ISBN: (纸本)9783642246685

In this paper we present our results in adapting a Spiking Neural P system (SNP system) simulator to a high performance graphics processing unit (GPU) platform. In particular, we extend our simulations to larger and more complex SNP systems using an NVIDIA Tesla C1060 GPU. The C1060 is manufactured for high performance computing and massively parallel computations, matching the maximally parallel nature of SNP systems. Using our GPU accelerated simulations we present speedups of around 200x for some SNP systems, compared to CPU only simulations. © 2011 Springer-Verlag.

关键词： Graphics processing unit

来源：评论

学校读者我要写书评

暂无评论

Upper and lower bounds for finding connected motifs in vertex-colored graphs

Upper and lower bounds for finding connected motifs in verte...

引用

作者： Fellows, Michael R. Fertin, Guillaume Hermelin, Danny Vialette, Stéphane University of Newcastle Callaghan NSW 2308 Australia UMR CNRS 6241 Université de Nantes 2 rue de la Houssinière 44322 Nantes Cedex 3 France Algorithms and Complexity Group Max Planck Institute for Informatics Campus E1 4 66123 Saarbrücken Germany LIGM CNRS Université Paris-Est 5 Bd Descartes 77454 Marne-la-Vallée France

We study the problem of finding occurrences of motifs in vertex-colored graphs, where a motif is a multiset of colors, and an occurrence of a motif is a subset of connected vertices whose multiset of colors equals the motif. This problem is a natural graph-theoretic pattern matching variant where we are not interested in the actual structure of the occurrence of the pattern, we only require it to preserve the very basic topological requirement of connectedness. We give two positive results and three negative results that together give an extensive picture of tractable and intractable instances of the problem. © 2010 Elsevier Inc. All rights reserved.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

Fixed-parameter evolutionary algorithms and the vertex cover problem

Fixed-parameter evolutionary algorithms and the vertex cover...

引用

11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009

作者： Kratsch, Stefan Neumann, Frank Algorithms and Complexity Group Max-Planck-Institut für Informatik Saarbrücken Germany

ISBN: (纸本)9781605583259

In this paper, we consider multi-objective evolutionary algorithms for the Vertex Cover problem in the context of parameterized complexity. We relate the runtime of our algorithms to the input size and the cost of a minimum solution and point out that the search process of evolutionary algorithms creates partial solutions that are similar to the effect of a kernelization (i.e. a special type of preprocessing from parameterized complexity). Based on this, we show that evolutionary algorithms solve the vertex cover problem efficiently if the size of a minimum vertex cover is not too large, i.e. the expected runtime is bounded by O(f(OPT)nc), where c is a constant and f a function that only depends on OPT. This shows that evolutionary algorithms are randomized fixed-parameter tractable algorithms for the vertex cover problem. Copyright 2009 ACM.

关键词： Multiobjective optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：