185 research outputs found
Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
No full textMotivated by routing issues in ad hoc networks, we present polylogarithmic-time distributed algorithms for two problems. Given a network, we first show how to compute connected and weakly connected dominating sets whose size is at most O (log A) times the optimum, A being the maximum degree of the input network. This is best-possible if NP not subset of DTIME[n(O(log log n))] and if the processors are required to run in polynomial-time. We then show how to construct dominating sets that have the above properties, as well as the "low stretch" property that any two adjacent nodes in the network have their dominators at a distance of at most O (log n) in the output network. (Given a dominating set S, a dominator of a vertex u is any nu epsilon S such. that the distance between u and v is at most one.) We also show our time bounds to be essentially optimal. (c) 2005 Elsevier Inc. All rights reserved
AI futures
No full textThree books offer varied perspectives on the ascendancy of artificial intelligence
Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
No full text
Finding most vital edges in a graph
No full textIn many applications such as design of transportation networks, we often need to identify a set of regions/sections whose damage will cause the greatest increase in transportation cost within the network so that we can set extra protection to prevent them from being damaged.Modeling a transportation network with a weighted graph, a set of regions with a set of edges in the graph, transportation cost within the network with a particular property of the graph, we can convert this real-application problem to the following graph-theoretic problem: finding a set of edges in the graph, namely most vital edges or MVE for short, whose removal will cause the greatest damage to a particular property of the graph. The problems are traditionally referred to as prior analysis problems in sensitivity analysis (see Chapter 30).http://www.amazon.com/Handbook-Approximation-Algorithms-Metaheuristics-Information/dp/158488550
Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
No full textAnalysis and Experimental Evaluation of a Simple Algorithm for Collaborative Filtering in Planted Partition Models
No full textAnalysis and Experimental Evaluation of a Simple Algorithm for Collaborative Filtering in Planted Partition Models
No full textSingularities and Cognitive Computing
No full textAdvances in Artificial Intelligence (AI)/Machine Learning (ML) have led to discussions about singularities: the economic singularity when AI displaces human jobs and the technological singularity when AI surpasses human capabilities in general intelligence. We seek to clarify some issues in the discussion
- …
