188 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
Towards a critique of Maharashtra's political economy: Conceptual cobwebs and policy puzzles
No full textBased on P.R. Dubhashi Public Lecture delivered at Gokhale Institute of Politics and Economics, Pune on Friday, December 18, 2009. Jayant Lele, Professor Emeritus, Departments of Political Studies, Sociology and Global Development Studies, Queen's University at Kingston, Canada, email: [email protected]. Author is grateful to Dr. Dubhashi, Dr. Parchure, Dr. Deepak Shah, Dr. Nagarajan, Dr. Rath and Dr. Tripathy for making this possible
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 text- …
