Search Constraints
Filtering by:
Date Created
2008
Remove constraint Date Created: 2008
Publisher
Springer Berlin Heidelberg
Remove constraint Publisher: Springer Berlin Heidelberg
1 - 10 of 10
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 bottom-up 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 bottom-up path in O(K/B) I/Os using only bits, for an arbitrarily selected constant, ε, where 0∈<∈ε<∈1. Our second result is for top-down 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 top-down traversal can still be performed in an asymptotically optimal number of I/Os.
- Date Created:
- 2008-12-01
-
- 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 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 π/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.
- Date Created:
- 2008-12-01
-
- 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 model-driven 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 e-commerce 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:
- 2008-11-28
-
- Resource Type:
- Conference Proceeding
- Creator:
- Bose, Prosenjit, Maheshwari, Anil, Carmi, Paz, Smid, Michiel, and Farshi, Mohammad
- Abstract:
- It is well-known that the greedy algorithm produces high quality spanners and therefore is used in several applications. However, for points in d-dimensional 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:
- 2008-10-27
-
- 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:
- 2008-09-22
-
- 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 on-line 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:
- 2008-08-27
-
- 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:
- 2008-07-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Kranakis, Evangelos, Morin, Pat, and Krizanc, Danny
- Abstract:
- We present a tradeoff between the expected time for two identical agents to rendez-vous on a synchronous, anonymous, oriented ring and the memory requirements of the agents. In particular, we show that there exists a 2t state agent, which can achieve rendez-vous on an n node ring in expected time O( n 2/2 t ∈+∈2 t ) and that any t/2 state agent requires expected time Ω( n 2/2 t ). As a corollary we observe that Θ(loglogn) bits of memory are necessary and sufficient to achieve rendez-vous in linear time.
- Date Created:
- 2008-05-12
-
- Resource Type:
- Conference Proceeding
- Creator:
- Wiese, Andreas and Kranakis, Evangelos
- Date Created:
- 2008-11-26
-
- Resource Type:
- Conference Proceeding
- Creator:
- Kranakis, Evangelos, Pelc, Andrzej, and Paquette, Michel
- Abstract:
- We study the feasibility and time of communication in random geometric radio networks, where nodes fail randomly with positive correlation. We consider a set of radio stations with the same communication range, distributed in a random uniform way on a unit square region. In order to capture fault dependencies, we introduce the ranged spot model in which damaging events, called spots, occur randomly and independently on the region, causing faults in all nodes located within distance s from them. Node faults within distance 2s become dependent in this model and are positively correlated. We investigate the impact of the spot arrival rate on the feasibility and the time of communication in the fault-free part of the network. We provide an algorithm which broadcasts correctly with probability 1 - ε in faulty random geometric radio networks of diameter D in time O(D + log1/ε).
- Date Created:
- 2008-11-26