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

local CONSTRUCTION AND COLORING OF SPANNERS OF LOCATION AWARE UNIT DISK GRAPHS

DISCRETE MATHEMATICS algorithms AND APPLICATIONS 2009年第4期1卷 555-588页

作者： Wiese, Andreas Kranakis, Evangelos Tech Univ Berlin Inst Math Str 17 Juni 136 D-10623 Berlin Germany Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada

We look at the problem of coloring locally specially constructed spanners of unit disk graphs. First we present a local approximation algorithm for the vertex coloring problem in Unit Disk Graphs (UDGs) which uses at most four times as many colors as an optimal solution requires. Next we look at the colorability of spanners of UDGs. In particular we present a local algorithm for constructing a 4-colorable spanner of a unit disk graph. The output consists of the spanner and the 4-coloring. The computed spanner also has the properties that it is planar, the degree of a vertex in the spanner is at most 5 and the angles between two edges are at least p/ 3. By enlarging the locality distance (i. e. the size of the neighborhood which a vertex has to explore in order to compute its color) we can ensure the total weight of the spanner to be arbitrarily close to the weight of a minimum spanning tree. We prove that a local algorithm cannot compute a bipartite spanner of a unit disk graph and therefore our algorithm needs at most one color more than any local algorithm for the task requires. Moreover, we prove that there is no local algorithm for 3-coloring UDGs or spanners of UDGs, even if the 3-colorability of the graph (or the spanner respectively) is guaranteed in advance.

关键词： local algorithms unit disk graphs approximation algorithms spanner coloring

来源：评论

学校读者我要写书评

暂无评论

Coloring Unstructured Wireless Multi-Hop Networks

Coloring Unstructured Wireless Multi-Hop Networks

引用

28th Annual ACM Symposium on Principles of Distributed Computing

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

ISBN: (纸本)9781605583969

We present a randomized coloring algorithm for the unstructured radio network model, a model comprising autonomous nodes, asynchronous wake-up, no collision detection and an unknown but geometric network topology. The current state-of-the-art coloring algorithm needs with high probability O(Delta . log n) time and uses O(Delta) colors, where n and Delta are the number of nodes in the network and the maximum degree, respectively;this algorithm requires knowledge of a linear bound on n and Delta. We improve this result in three ways: Firstly, we improve the time complexity, instead of the logarithmic factor we just need a polylogarithmic additive term, more specifically, our time complexity is O(Delta + log Delta . log n) given an estimate of n and Delta, and O(Delta + log(2) n) without knowledge of Delta. Secondly, our vertex coloring algorithm needs Delta + 1 colors only. Thirdly, our algorithm manages to do a distance-d coloring with asymptotically optimal O(Delta) colors for a constant d.

关键词： Ad Hoc Networks Sensor Networks Unstructured Radio Networks Unit Disk Graphs Growth Bounded Graphs Bounded Independence Graphs local algorithms Parallel algorithms Distributed algorithms Coloring

来源：评论

学校读者我要写书评

暂无评论

A local Algorithm for Finding Dense Subgraphs

A Local Algorithm for Finding Dense Subgraphs

引用

19th ACM-SIAM Symposium on Discrete algorithms

作者： Andersen, Reid Microsoft Redmond WA 98052 One Microsoft Way United States

ISBN: (纸本)9780898716474

A local graph algorithm is one that searches for an approximation of the best solution near a specified starting vertex, and has a running time independent of the size of the graph. Recently, local algorithms have been developed for graph partitioning and clustering. In this paper, we present a local algorithm for finding dense subgraphs of bipartite graphs, according to the measure of density proposed by Karman and Vinay. The algorithm takes as input a bipartite graph with a. specified starting vertex, and attempts to find a dense subgraph near that vertex. We prove the following local approximation guarantee for the algorithm. For any subgraph S with k vertices and density theta, there is a large set of starting vertices within S for which the algorithm produces a subgraph with density Omega(theta/log Delta), where Delta is the maximum degree. The running time of the algorithm is O(Delta k(2)), independent of the number of vertices in the graph.

关键词： Dense subgraphs local algorithms Spectral graph theory

来源：评论

学校读者我要写书评

暂无评论

What Can Be Approximated locally? Case Study: Dominating Sets in Planar Graphs 08

What Can Be Approximated Locally? Case Study: Dominating Set...

引用

20th ACM Symposium on Parallelism in algorithms and Architectures

作者： Lenzen, Christoph Oswald, Yvonne Anne Wattenhofer, Roger ETH Comp Engn & Networks Lab Zurich Switzerland

ISBN: (纸本)9781595939739

Whether local algorithms can compute constant approximations of NP-hard problems is of both practical and theoretical interest. So far, no algorithms achieving this goal are known, as either the approximation ratio or the running time exceed O(1), or the nodes are provided with non-trivial additional information. In this paper, we present the first distributed algorithm approximating a minimum dominating set on a planar graph within a constant factor in constant time. Moreover, the nodes do not need any additional information.

关键词： approximation distributed algorithms local algorithms dominating sets planar graphs

来源：评论

学校读者我要写书评

暂无评论

A Log-Star Distributed Maximal Independent Set Algorithm for Growth-Bounded Graphs

A Log-Star Distributed Maximal Independent Set Algorithm for...

引用

27th Annual ACM Symposium on Principles of Distributed Computing

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

ISBN: (纸本)9781595939890

We present a novel distributed algorithm for the maximal independent set (MIS) problem. On growth-bonded graphs (GBG) our deterministic algorithm finishes in O(log*n) time, n being the, number of nodes. In light of Linial's Omega(log* n) lower bound our algorithm is asymptotically, v optimal. Our algorithm answers prominent open problems, in the ad hoc/sensor network domain. For instance, it solves the connected dominating set problem for unit. disk graphs in O(log* n) time, exponentially faster than the state-of-the-art algorithm. With a new extension our algorithm also computes a delta + 1 coloring in O(log'n) time, where delta is the maximum degree of the graph.

关键词： Ad Hoc Networks Sensor Networks Radio Networks Unit Disk Graphs Growth Bounded Graphs local algorithms Parallel algorithms Maximal Independent Sets Dominating Sets Connected Dominating Sets Coloring Symmetry Breaking

来源：评论

学校读者我要写书评

暂无评论

local solutions for global problems in wireless networks

引用

JOURNAL OF DISCRETE algorithms 2007年第3期5卷 395-407页

作者： Urrutia, J. Univ Nacl Autonoma Mexico Inst Matematicas Mexico City DF Mexico

In this paper, we review a recently developed class of algorithms that solve global problems in unit distance wireless networks by means of local algorithms. A local algorithm is one in which any node of a network only has information on nodes at distance at most k from itself, for a constant k. For example, given a unit distance wireless network N, we want to obtain a planar subnetwork of N by means of an algorithm in which all nodes can communicate only with their neighbors in N, perform some operations, and then halt. We review algorithms for obtaining planar subnetworks, approximations to minimum weight spanning trees, Delaunay triangulations, and relative neighbor graphs. Given a unit distance wireless network N, we present new local algorithms to solve the following problems: 1. Calculate small dominating sets ( not necessarily connected) of N. 2. Extract a bounded degree planar subgraph H of N and obtain a proper edge coloring of H with at most 12 colors. The second of these algorithms can be used in the channel assignment problem. (C) 2007 Elsevier B.V. All rights reserved.

关键词： local algorithms Routing Ad hoc and wireless networks Dominating sets local vertex coloring

来源：评论

学校读者我要写书评

暂无评论

Compositional systems over reducible networks

引用

FUNDAMENTA INFORMATICAE 2007年第3-4期79卷 265-282页

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

In the paper two notions related to local (distributed) computations are identified and discussed. The first one is the notion of reducible graphs. A graph is reducible if it can be reduced to a singleton by successive removing its removable nodes;the removing procedure should be local in the sense that to decide whether a node is removable or not it is sufficient to inspect its neighbor-hood. The second is the notion of compositional systems, consisting of a set of objects together with a composition operation which to each pair of local objects (like local votes, partial trees, partial orderings, local consensus, local processes etc.) assigns their possible compositions;a sequence of such composition operations leads to a global object (like a global vote, a full spanning tree, a total ordering, a global consensus, a synchronized process, etc). Combining these two notions gives rise to a generic distributed algorithm for composing different local objects assigned to nodes of a reducible graph into one global object assigned to all nodes. Correctness of the composing algorithm, i.e its proper termination and its impartiality is proved.

关键词： local algorithms distributed data computation networks distributed computing

来源：评论

学校读者我要写书评

暂无评论

Association rule mining in peer-to-peer systems

引用

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS 2004年第6期34卷 2426-2438页

作者： Wolff, R Schuster, A Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

We extend the problem of association rule mining-a key data mining problem-to systems in which the database is partitioned among a very large number of computers that are dispersed over a wide area. Such computing systems include grid computing platforms, federated database systems, and peer-to-peer computing environments. The scale of these systems poses several difficulties, such as the impracticality of global communications and global synchronization, dynamic topology changes of the network, on-the-fly data updates, the need to share resources with other applications, and the frequent failure and recovery of resources. We present an algorithm by which every node in the system can reach the exact solution, as if it were given the combined database. The algorithm is entirely asynchronous, imposes very little communication overhead, transparently tolerates network topology changes and node failures, and quickly, adjusts to changes in the data as they occur. Simulation of up to 10000 nodes show that the algorithm is local: all rules, except for those whose confidence is about equal to the confidence threshold, are discovered using information gathered from a very small vicinity, whose size is independent of the size of the system.

关键词： anytime algorithms association rule-mining data mining local algorithms peer-to-peer

来源：评论

学校读者我要写书评

暂无评论

On complexity of minimization and compression problems for models of sequential choice

引用

DISCRETE APPLIED MATHEMATICS 2004年第1-3期135卷 281-300页

作者： Sholomov, LA Russian Acad Sci Inst Syst Anal Moscow 117312 Russia

A model of sequential choice of depth k for binary relations r(1),r(2),...,r(k) on a set A of alternatives relates each X subset of or equal to A to its subset C, (...C-r2(C-r1(X))...), where C-r(Y)={y is an element of Y \(For Allz is an element of Y)z (r) over bary}, Y subset of or equal to A. The minimization problem is of building an equivalent model of minimal depth;the compression problem is posed similarly, but the model built must satisfy some "insertion" condition. We prove that for k greater than or equal to 3, the minimization and compression problems for models of depth k are NP-hard (for k = 2, they are polynomial). Parameters of local algorithms solving these problems are investigated, and it is shown that the compression problem is decidable by algorithms working with neighbourhoods of size 3, whereas the minimization problem is not decidable for any finite neighbourhood size. For an arbitrary k, a model of depth k is built such that its minimization problem is not decidable with the use of neighbourhoods smaller than the whole model. (C) 2002 Elsevier B.V. All rights reserved.

关键词： choice models sequential choice binary relations complexity minimization problem compression problem local algorithms

来源：评论

学校读者我要写书评

暂无评论

A Graphical μ—Calculus and local Model Checking

引用

Journal of Computer Science & Technology 2002年第6期17卷 665-671页

作者：林惠民 LaboratoryforComputerScience InstituteofSoftwareTheChineseAcademyofSciencesP.O.Box8718Beijing100080

A graphical notation for the propositionalμ-calculus, called modal graphs, ispresented. It is shown that both the textual and equational presentations of theμ-calculus canbe translated into modal graphs. A model checking algorithm based on such graphs is *** algorithm is truly local in the sense that it only generates the parts of the underlyingsearch space which are necessary for the computation of the final result. The correctness of thealgorithm is proven and its complexity analysed.

关键词： model checking μ-calculus modal graphs local algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：