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

local Computations on Triangular Graphs

FUNDAMENTA INFORMATICAE 2010年第1-4期100卷 117-140页

作者： Mazurkiewicz, Antoni Polish Acad Sci Inst Comp Sci PL-01237 Warsaw Poland

The paper deals with the class of finite triangular graphs. It turns out that this class enjoys regular properties similar to those of trees and complete graphs. The main objective of the paper is to lift algorithms for some typical local computations, known for other classes of graphs, to the class of triangular graphs. local algorithms on graphs, according to [8, 9], are defined as local rules for relabeling graph nodes. Rules are local, if they are defined only for a class of subgraphs of processed graph (as neighborhoods of nodes or edges) and neither their results nor their applicability do not depend upon the knowledge of the whole graph labeling. While designing local algorithm for triangular graphs one needs to use some intrinsic properties of such graphs;it puts some additional light on their inherent structure. To illustrate essential features of local computations on triangular graphs, local algorithms for three typical issues of local computations are discussed: leader election, spanning tree construction, and nodes ordering. Correctness of these algorithms, as deadlock freeness, proper termination, and impartiality, are proved.

关键词： local algorithms triangular graphs leader elections spanning trees nodes orderings

来源：评论

学校读者我要写书评

暂无评论

A local O(n²) Gathering Algorithm 10

A Local O(n<SUP>2</SUP>) Gathering Algorithm

引用

22nd ACM Symposium on Parallelism in algorithms and Architectures

作者： Degener, Bastian Kempkes, Barbara auf der Heide, Friedhelm Meyer Univ Gesamthsch Paderborn Dept Comp Sci Heinz Nixdorf Inst D-4790 Paderborn Germany

ISBN: (纸本)9781450300797

The gathering problem, where n autonomous robots with restricted capabilities are required to meet in a single point of the plane, is widely studied We consider the case that robots are limited to see only robots within a bounded vicinity and present an algorithm achieving gathering in O(n(2)) rounds in expectation A round consists of a movement of all robots, in random order. All previous algorithms with a proven time bound assume global view on the configuration of all robots

关键词： swarm robotics local algorithms distributed algorithms gathering geometric networks

来源：评论

学校读者我要写书评

暂无评论

Almost Stable Matchings by Truncating the Gale-Shapley Algorithm

引用

ALGORITHMICA 2010年第1期58卷 102-118页

作者： Floreen, Patrik Kaski, Petteri Polishchuk, Valentin Suomela, Jukka Univ Helsinki HIIT FIN-00014 Helsinki Finland

We show that the ratio of matched individuals to blocking pairs grows linearly with the number of propose-accept rounds executed by the Gale-Shapley algorithm for the stable marriage problem. Consequently, the participants can arrive at an almost stable matching even without full information about the problem instance;for each participant, knowing only its local neighbourhood is enough. In distributed-systems parlance, this means that if each person has only a constant number of acceptable partners, an almost stable matching emerges after a constant number of synchronous communication rounds. We apply our results to give a distributed (2+epsilon)-approximation algorithm for maximum-weight matching in bicoloured graphs and a centralised randomised constant-time approximation scheme for estimating the size of a stable matching.

关键词： Distributed stable matching Almost stable matching local algorithms Constant-time randomised algorithms

来源：评论

学校读者我要写书评

暂无评论

A New Technique For Distributed Symmetry Breaking

A New Technique For Distributed Symmetry Breaking

引用

29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing

作者： Schneider, Johannes Wattenhofer, Roger ETH Comp Engn & Networks Lab CH-8092 Zurich Switzerland

ISBN: (纸本)9781605588889

We introduce MULTI-TRIALS, a new technique for symmetry breaking for distributed algorithms and apply it to various problems in general graphs. For instance, we present three randomized algorithms for distributed (vertex or edge) coloring improving on previous algorithms and showing a time/color trade-off. To get a Delta + 1 coloring takes time O(log Delta + root log n). To obtain an O(Delta + log(1+1/log)*(n) n) coloring takes time O(log* n). This is more than an exponential improvement in time for graphs of polylogarithmic degree. Our fastest algorithm works in constant time using O(Delta log((c)) n + log(1+1/c) n) colors, where c denotes an arbitrary constant and log((c)) n denotes the c times (recursively) applied logarithm to n. We also use the MULTI-TRIALS technique to compute network decompositions and to compute maximal independent set (MIS), obtaining new results for several graph classes.

关键词： local algorithms Parallel algorithms Coloring Symmetry Breaking Network Decomposition

来源：评论

学校读者我要写书评

暂无评论

Study on the unweighted least-squares phase unwrapping algorithm

Study on the unweighted least-squares phase unwrapping algor...

引用

Conference on Holography, Diffractive Optics, and Applications IV

作者： Wang, Xuhui Zhang, Zhihui Guo, Zhongjia Wang, Huaying Handan Coll Sch Informat Engn Handan 056005 Hebei Peoples R China Hebei Univ Engn Sch Informat & Elect Engn Handan 056038 Peoples R China Hebei Univ Engn Coll Sci Handan 056038 Peoples R China

ISBN: (纸本)9780819483782

Two-dimensional phase unwrapping algorithm is the important step and key technology of three-dimensional shape measurement. In order to obtain the appearance characteristics of the object more accurately, a new phase unwrapping algorithm based on unweighted least-squares is presented in this paper, which is an improvement of discrete cosine transform (DCT) phase unwrapping algorithm. The advantage of this method is not only because of the global algorithms, processing the image as a whole, each pixel's value in the image is uniquely determined by solving the Discrete Poisson's equation with Newman boundary conditions which makes the least-squares solution of the wrapped and unwrapped phase difference minimum, but also can reduce the residues effectively. Through computer simulation, this new method and the original DCT algorithm were compared. Theoretical analysis and the results prove the validity of this method. The improved algorithm can eliminate the residues in the wrapped phase pictures more effectively. The phase information of the object can be reconstructed more accurately.

关键词： two-dimensional phase unwrapping algorithm three-dimensional shape measurement the least-squares phase unwrapping algorithm Discrete Poison equation Neumann boundary conditions discrete cosine transform global algorithms computer simulation local algorithms

来源：评论

学校读者我要写书评

暂无评论

A local Algorithm for Finding Dense Subgraphs

引用

ACM TRANSACTIONS ON algorithms 2010年第4期6卷 1–12页

作者： Andersen, Reid Microsoft Corp 1 Microsoft Way Redmond WA 98052 USA

We describe a local algorithm for finding subgraphs with high density, according to a measure of density introduced by Kannan and Vinay [1999]. The algorithm takes as input a bipartite graph G, a starting vertex v , and a parameter k, and outputs an induced subgraph of G. It is local in the sense that it does not examine the entire input graph;instead, it adaptively explores a region of the graph near the starting vertex. The running time of the algorithm is bounded by O(Delta k(2)), which depends on the maximum degree Delta, but is otherwise independent of the graph. We prove the following approximation guarantee: for any subgraph S with k' vertices and density theta, there exists a set S' subset of S for which the algorithm outputs a subgraph with density Omega(theta/log Delta) whenever v is an element of S' and k >= k'. We prove that S' contains at least half of the edges in S.

关键词： Dense subgraphs local algorithms spectral graph theory

来源：评论

学校读者我要写书评

暂无评论

A simple local 3-approximation algorithm for vertex cover

引用

INFORMATION PROCESSING LETTERS 2009年第12期109卷 642-645页

作者： Polishchuk, Valentin Suomela, Jukka Aalto Univ HIIT FI-00014 Helsinki Finland Univ Helsinki FI-00014 Helsinki Finland

We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering... 详细信息

关键词： Approximation algorithms Distributed computing Graph algorithms local algorithms

来源：评论

学校读者我要写书评

暂无评论

A Generic local Algorithm for Mining Data Streams in Large Distributed Systems

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2009年第4期21卷 465-478页

作者： Wolff, Ran Bhaduri, Kanishka Kargupta, Hillol Univ Haifa Dept Management Informat Syst IL-31905 Haifa Israel NASA Ames Res Ctr Mission Crit Technol Inc IDU Grp Moffett Field CA 94035 USA Univ Maryland Dept Comp Sci & Elect Engn Baltimore MD 21250 USA AGNIK LLC Columbia MD 21045 USA

In a large network of computers or wireless sensors, each of the components (henceforth, peers) has some data about the global state of the system. Much of the system's functionality such as message routing, information retrieval, and load sharing relies on modeling the global state. We refer to the outcome of the function (e. g., the load experienced by each peer) as the model of the system. Since the state of the system is constantly changing, it is necessary to keep the models up to date. Computing global data mining models, e. g., decision trees, k-means clustering in large distributed systems may be very costly due to the scale of the system and due to communication cost, which may be high. The cost further increases in a dynamic scenario when the data changes rapidly. In this paper, we describe a two-step approach for dealing with these costs. First, we describe a highly efficient local algorithm that can be used to monitor a wide class of data mining models. Then, we use this algorithm as a feedback loop for the monitoring of complex functions of the data such as its k-means clustering. The theoretical claims are corroborated with a thorough experimental analysis.

关键词： Distributed data mining peer-to-peer local algorithms

来源：评论

学校读者我要写书评

暂无评论

An Optimal local Approximation Algorithm for Max-Min Linear Programs 09

An Optimal Local Approximation Algorithm for Max-Min Linear ...

引用

21st ACM Symposium on Parallelism in algorithms and Architectures

作者： Floreen, Patrik Kaasinen, Joel Kaski, Petteri Suomela, Jukka Univ Helsinki HIIT FI-00014 Helsinki Finland

In a max-min LP, the objective is to maximise omega subject to Ax = omega 1, and x >= 0 for nonnegative matrices A and C. We present a local algorithm (constant-time distributed algorithm) for approximating max-min... 详细信息

ISBN: (纸本)9781605586069

In a max-min LP, the objective is to maximise omega subject to Ax <= 1, Cx >= omega 1, and x >= 0 for nonnegative matrices A and C. We present a local algorithm (constant-time distributed algorithm) for approximating max-min Us. The approximation ratio Of Our algorithm is the best possible for any local algorithm;there is a matching unconditional lower bound.

关键词： local algorithms approximation algorithms linear programs

来源：评论

学校读者我要写书评

暂无评论

A local Scalable Distributed Expectation Maximization Algorithm for Large Peer-to-Peer Networks

A Local Scalable Distributed Expectation Maximization Algori...

引用

9th IEEE International Conference on Data Mining

作者： Bhaduri, Kanishka Srivastava, Ashok N. NASA Ames Res Ctr MCT Inc MS 269-2 Moffett Field CA 94035 USA NASA Ames Res Ctr Moffett Field CA 94035 USA

ISBN: (纸本)9781424452422

This paper describes a local and distributed expectation maximization algorithm for learning parameters of Gaussian mixture models (GMM) in large peer-to-peer (P2P) environments. The algorithm can be used for a variety of well-known data mining tasks in distributed environments such as clustering, anomaly detection, target tracking, and density estimation to name a few, necessary for many emerging P2P applications in bioinformatics, webmining and sensor networks. Centralizing all or some of the data to build global models is impractical in such P2P environments because of the large number of data sources, the asynchronous nature of the P2P networks, and dynamic nature of the data/network. The proposed algorithm takes a two-step approach. In the monitoring phase, the algorithm checks if the model 'quality' is acceptable by using an efficient local algorithm. This is then used as a feedback loop to sample data from the network and rebuild the GMM when it is outdated. We present thorough experimental results to verify our theoretical claims.

关键词： peer-to-peer local algorithms expectation maximization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：