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.
We prove that for all 0 ≤ t ≤ k and d ≥ 2k, every graph G with treewidth at most k has a 'large' induced subgraph H, where H has treewidth at most t and every vertex in H has degree at most d in G, The order of H depends on t, k, d, and the order of G. With t = k, we obtain large sets of bounded degree vertices. With t = 0, we obtain large independent sets of bounded degree. In both these cases, our bounds on the order of H are tight. For bounded degree independent sets in trees, we characterise the extremal graphs. Finally, we prove that an interval graph with maximum clique size k has a maximum independent set in which every vertex has degree at most 2k.
We present external memory algorithms for outerplanarity testing, embedding outerplanar graphs, breadth-first search (BFS) and depth-first search (DFS) in outerplanar graphs, and finding a2-separator of size 2 for a given outerplanar graph. Our algorithms take O(sort(N)) I/Os and can easily be improved to take O (perm (N)) I/Os, as all these problems have linear time solutions in internal memory. For BFS, DFS, and outerplanar embedding we show matching lower bounds.
We present tight upper and lower bounds on the spanning ratio of a large family of constrained θ-graphs. We show that constrained θ-graphs with 4k2 (k≥ 1 and integer) cones have a tight spanning ratio of 1+2 sin(θ/2), where θ is 2 π/ (4k+2). We also present improved upper bounds on the spanning ratio of the other families of constrained θ-graphs.
Given a set S of s points in the plane, where do we place a new point, p, in order to maximize the area of its region in the Voronoi diagram of S and p? We study the case where the Voronoi neighbors of p are in convex position, and prove that there is at most one local maximum.
Fuel cells with nominal outputs of approximately 1kW AC are emerging as a prime-mover of a micro-cogeneration system potentially well-suited to compete, on an energy basis, with conventional methods for satisfying occupant electrical and thermal demands in a residential application. As the energy benefits of these systems can be incremental when compared to efficient conventional methods, it is especially important to consider the uncertainties of the models on which simulation results are based. However, researchers have yet to take this aspect into account.This article makes a contribution by demonstrating how these model uncertainties may be propagated to the simulation results of a micro-cogeneration system for comparison to a reference scenario using a case study. This case study compares the energy performance of a fuel-cell based micro-cogeneration system serving only domestic hot water demands to an efficient reference scenario where the conventional methods for providing electrical and thermal demands are considered to be a central gas-fired combined-cycle plant and a condensing tankless water heater respectively. The simulation results demonstrated that if model uncertainties were ignored, it would have been possible to demonstrate that the considered micro-cogeneration system was more efficient than the reference scenario for average consumption levels of domestic hot water. However, when model uncertainties were considered, the efficiency of the considered micro-cogeneration system could not reliably exceed that of the reference scenario by serving the domestic hot water needs of a single-family home.
We describe a novel Distributed Storage protocol in Disruption (Delay) Tolerant Networks (DTN). Since DTNs can not guarantee the connectivity of the network all the time, distributed data storage and look up has to be performed in a store-and-forward way. In this work, we define local distributed location regions which are called cells to facilitate the data storage and look up process. Nodes in a cell have high probability of moving within their cells. Our protocol resorts to storing data items in cells which have hierarchical structure to reduce routing information storage at nodes. Multiple copies of a data item may be stored at nodes to counter the adverse impact of the nature of DTNs. The cells are relatively stable regions and as a result, data exchange overheads among nodes are reduced. Through experimentation, we show that the proposed distributed storage protocol achieves higher successful data storage ratios with lower delays and limited data item exchange requirements than other protocols in the literature.
This article interrogates the question of what it means to be a scholar-commentator in the digital age. Deploying an autoethnographic style, the essay asks about the role of power and responsibility in teaching, research, and public commentary, particularly in the context of studying and engaging in Jewish politics. The article addresses questions about the proper role of the scholar in the academy and the role of subjectivity and political commitments in structuring scholarship, pedagogy, and public engagement. It also examines how one’s view of the profession can seem to shift through the emergence of new writing outlets and new forums for public engagement. Finally, the author investigates how a scholar’s own political commitments can shift over time, how one seeks to shore up identification on social media while trying to change hearts and minds through the op-ed pages, and how community identification can serve as a buffer and motivator for particular forms of research and political action.
There is a paradoxical relationship between the density of solar housing and net household energy use. The amount of solar energy available per person decreases as density increases. At the same time, transportation energy, and to some extent, household operating energy decreases. Thus, an interesting question is posed: how does net energy use vary with housing density? This study attempts to provide insight into this question by examining three housing forms: low-density detached homes, medium-density townhouses, and high-density high-rise apartments in Toronto. The three major quantities of energy that are summed for each are building operational energy use, solar energy availability, and personal transportation energy use. Solar energy availability is determined on the basis of an effective annual collector efficiency. The results show that under the base case in which solar panels are applied to conventional homes, the high-density development uses one-third less energy than the low-density one. Improving the efficiency of the homes results in a similar trend. Only when the personal vehicle fleet or solar collectors are made to be extremely efficient does the trend reverse-the low-density development results in lower net energy.