Search Constraints
Filtering by:
Publisher
Springer Berlin Heidelberg
Remove constraint Publisher: Springer Berlin Heidelberg
Number of results to display per page
Search Results

 Resource Type:
 Conference Proceeding
 Creator:
 Dillabaugh, Craig, He, Meng, and Maheshwari, Anil
 Abstract:
 We present two results for path traversal in trees, where the traversal is performed in an asymptotically optimal number of I/Os and the tree structure is represented succinctly. Our first result is for bottomup traversal that starts with a node in the tree T and traverses a path to the root. For blocks of size B, a tree on N nodes, and for a path of length K, we design data structures that permit traversal of the bottomup path in O(K/B) I/Os using only bits, for an arbitrarily selected constant, ε, where 0∈<∈ε<∈1. Our second result is for topdown traversal in binary trees. We store T using (3∈+∈q)N∈+∈o(N) bits, where q is the number of bits required to store a key, while topdown traversal can still be performed in an asymptotically optimal number of I/Os.
 Date Created:
 20081201

 Resource Type:
 Conference Proceeding
 Creator:
 Kranakis, Evangelos and Wiese, Andreas
 Abstract:
 We investigate the problem of locally coloring and constructing special spanners of location aware Unit Disk Graphs (UDGs). First we present a local approximation algorithm for the vertex coloring problem in UDGs which uses at most four times as many colors as required by an optimal solution. Then we look at the colorability of spanners of UDGs. In particular we present a local algorithm for constructing a 4colorable spanner of a unit disk graph. The output consists of the spanner and the 4coloring. 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 π/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 3coloring UDGs or spanners of UDGs, even if the 3colorability of the graph (or the spanner respectively) is guaranteed in advance.
 Date Created:
 20081201

 Resource Type:
 Conference Proceeding
 Creator:
 Petriu, Dorina C. and Tawhid, Rasha
 Abstract:
 The paper proposes to integrate performance analysis in the early phases of the modeldriven development process for Software Product Lines (SPL). We start by adding generic performance annotations to the UML model representing the set of core reusable SPL assets. The annotations are generic and use the MARTE Profile recently adopted by OMG. A first model transformation realized in the Atlas Transformation Language (ATL), which is the focus of this paper, derives the UML model of a specific product with concrete MARTE performance annotations from the SPL model. A second transformation generates a Layered Queueing Network performance model for the given product by applying an existing transformation approach named PUMA, developed in previous work. The proposed technique is illustrated with an ecommerce case study that models the commonality and variability in both structural and behavioural SPL views. A product is derived and the performance of two design alternatives is compared.
 Date Created:
 20081128

 Resource Type:
 Conference Proceeding
 Creator:
 Bose, Prosenjit, Maheshwari, Anil, Carmi, Paz, Smid, Michiel, and Farshi, Mohammad
 Abstract:
 It is wellknown that the greedy algorithm produces high quality spanners and therefore is used in several applications. However, for points in ddimensional Euclidean space, the greedy algorithm has cubic running time. In this paper we present an algorithm that computes the greedy spanner (spanner computed by the greedy algorithm) for a set of n points from a metric space with bounded doubling dimension in time using space. Since the lower bound for computing such spanners is Ω(n 2), the time complexity of our algorithm is optimal to within a logarithmic factor.
 Date Created:
 20081027

 Resource Type:
 Conference Proceeding
 Creator:
 Kranakis, Evangelos, Shi, Q., Bhattacharya, B., Wiese, A., Burmester, B., and Hu, Y.
 Abstract:
 Intrusion detection, area coverage and border surveillance are important applications of wireless sensor networks today. They can be (and are being) used to monitor large unprotected areas so as to detect intruders as they cross a border or as they penetrate a protected area. We consider the problem of how to optimally move mobile sensors to the fence (perimeter) of a region delimited by a simple polygon in order to detect intruders from either entering its interior or exiting from it. We discuss several related issues and problems, propose two models, provide algorithms and analyze their optimal mobility behavior.
 Date Created:
 20080922

 Resource Type:
 Conference Proceeding
 Creator:
 Couture, Mathieu, Smid, Michiel, Maheshwari, Anil, Bose, Prosenjit, Carmi, Paz, and Zeh, Norbert
 Abstract:
 Given an integer k ≥ 2, we consider the problem of computing the smallest real number t(k) such that for each set P of points in the plane, there exists a t(k)spanner for P that has chromatic number at most k. We prove that t(2)∈=∈3, t(3)∈=∈2, , and give upper and lower bounds on t(k) for k∈>∈4. We also show that for any ε>∈0, there exists a (1∈+∈ε)t(k)spanner for P that has O(P) edges and chromatic number at most k. Finally, we consider an online variant of the problem where the points of P are given one after another, and the color of a point must be assigned at the moment the point is given. In this setting, we prove that t(2)∈=∈3, , , and give upper and lower bounds on t(k) for k∈>∈4.
 Date Created:
 20080827

 Resource Type:
 Conference Proceeding
 Creator:
 Kranakis, Evangelos and Wiese, Andreas
 Abstract:
 We present the first local approximation schemes for maximum independent set and minimum vertex cover in unit disk graphs. In the graph model we assume that each node knows its geographic coordinates in the plane (location aware nodes). Our algorithms are local in the sense that the status of each node v (whether or not v is in the computed set) depends only on the vertices which are a constant number of hops away from v. This constant is independent of the size of the network. We give upper bounds for the constant depending on the desired approximation ratio. We show that the processing time which is necessary in order to compute the status of a single vertex is bounded by a polynomial in the number of vertices which are at most a constant number of vertices away from it. Our algorithms give the best possible approximation ratios for this setting. The technique which we use to obtain the algorithm for vertex cover can also be employed for constructing the first global PTAS for this problem in unit disk graph which does not need the embedding of the graph as part of the input.
 Date Created:
 20080701

 Resource Type:
 Conference Proceeding
 Creator:
 Biddle, Robert, Noble, James, Barr, Pippin, Fischer, Ronald, and Khaled, Rilla
 Abstract:
 Persuasive technologies are increasingly ubiquitous, but the strategies they utilise largely originate in America. Consumer behaviour research shows us that certain persuasion strategies will be more effective on some cultures than others. We claim that the existing strategies will be less effective on nonAmerican audiences than they are on American audiences, and we use information from interviews to show that there exists much scope to develop persuasive technologies from a collectivismfocused perspective. To illustrate the development of such a tool, we describe the design of a collectivismfocused financial planning tool.
 Date Created:
 20060717

 Resource Type:
 Conference Proceeding
 Creator:
 Smid, Michiel and Gudmundsson, Joachim
 Abstract:
 Given a connected geometric graph G, we consider the problem of constructing a tspanner of G having the minimum number of edges. We prove that for every t with 1 1+1/t) edges. This bound almost matches the known upper bound, which states that every connected weighted graph with n vertices contains a tspanner with O(tn1+2/(t+1)) edges. We also prove that the problem of deciding whether a given geometric graph contains a tspanner with at most K edges is NPhard. Previously, this NPhardness result was only known for nongeometric graphs.
 Date Created:
 20060101

 Resource Type:
 Conference Proceeding
 Creator:
 Mirandola, Raffaela, Grassi, Vincenzo, Sabetta, Antonino, and Petriu, Dorina C.
 Abstract:
 The verification of nonfunctional requirements of software models (such as performance, reliability, scalability, security, etc.) requires the transformation of UML models into different analysis models such as Petri nets, queueing networks, formal logic, etc., which represent the system at a higher level of abstraction. The paper proposes a new "abstractionraising" transformation approach for generating analysis models from UML models. In general, such transformations must bridge a large semantic gap between the source and the target model. The proposed approach is illustrated by a transformation from UML to Klaper (Kernel LAnguage for PErformance and Reliability analysis of componentbased systems).
 Date Created:
 20060706