The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
A Semi-Separated Pair Decomposition (SSPD), with parameter s > 1, of a set is a set {(Ai,Bi)} of pairs of subsets of S such that for each i, there are balls and containing Ai and Bi respectively such...
Let S be a set of n points in general position in the plane. Together with S we are given a set of parity constraints, that is, every point of S is labeled either even or odd. A graph G on S satisfies the parity constraint of a point p ∈ S, if the parity of the degree of p in G matches its label. In this paper we study how well various classes of planar graphs can satisfy arbitrary parity constraints...
We show that every c-planar clustered graph admits a straight-line c-planar drawing in which each cluster is represented by an axis-parallel rectangle, thus solving a problem posed by Eades, Feng, Lin, and Nagamochi [Algorithmica, 2006].
A central issue in the design of modern communication networks is the provision of Quality-of-Service (QoS) guarantees at the presence of heterogeneous users. For instance, in QoS multicasting, a source needs to efficiently transmit a message to a set of receivers, each requiring support at a different QoS level (e.g., bandwidth). This can be formulated as the Priority Steiner tree problem: Here,...
A feed-link is an artificial connection from a given location p to a real-world network. It is most commonly added to an incomplete network to improve the results of network analysis, by making p part of the network. The feed-link has to be “reasonable”, hence we use the concept of dilation to determine the quality of a connection. We consider the following abstract problem: Given a simple...
Locked tree linkages have been known to exist in the plane since 1998, but it is still open whether they have a polynomial-time characterization. This paper examines the properties needed for planar trees to lock, with a focus on finding the smallest locked trees according to different measures of complexity, and suggests some new avenues of research for the problem of algorithmic characterization...
We consider minimum equivalent digraph problem, its maximum optimization variant and some non-trivial extensions of these two types of problems motivated by biological and social network applications. We provide -approximation algorithms for all the minimization problems and 2-approximation algorithms for all the maximization problems using appropriate primal-dual polytopes. We also...
Given a connected graph G = (V,E) with nonnegative costs on edges, $c:E\rightarrow {\mathcal R}^+$ , and a subset of terminal nodes R ⊂ V, the Steiner tree problem asks for the minimum cost subgraph of G spanning R. The Steiner Tree Problem with distances 1 and 2 (i.e., when the cost of any edge is either 1 or 2) has been investigated for long time since it is MAX SNP-hard and admits better approximations...
We present a succinct representation of a set of n points on an n×n grid using $n\lg n + o(n\lg n)$ bits to support orthogonal range counting in $O(\lg n /\lg\lg n)$ time, and range reporting in $O(k\lg n/\lg\lg n)$ time, where k is the size of the output. This achieves an improvement on query time by a factor of upon the previous result of Mäkinen and Navarro [1], while...
The time required for a sequence of operations on a data structure is usually measured in terms of the worst possible such sequence. This, however, is often an overestimate of the actual time required. Distribution-sensitive data structures attempt to take advantage of underlying patterns in a sequence of operations in order to reduce time complexity, since access patterns are non-random in many applications...
This paper provides a systematic study of several proposed measures for online algorithms in the context of a specific problem, namely, the two server problem on three colinear points. Even though the problem is simple, it encapsulates a core challenge in online algorithms which is to balance greediness and adaptability. We examine Competitive Analysis, the Max/Max Ratio, the Random Order Ratio, Bijective...
Suppose we want to compute the Delaunay triangulation of a set P whose points are restricted to a collection of input regions known in advance. Building on recent work by Löffler and Snoeyink[21], we show how to leverage our knowledge of for faster Delaunay computation. Our approach needs no fancy machinery and optimally handles a wide variety of inputs, eg, overlapping...
We present an improved algorithm for the general satisfiability problem. We introduce a new measure, the l-value, for a Boolean formula , which is defined based on weighted variable frequencies in the formula . We then develop a branch-and-search algorithm for the satisfiability problem that tries to maximize the decreasing rates in terms of the l-value during the branch-and-search...
We develop algorithms to compute edge sequences, Voronoi diagrams, shortest path maps, the Fréchet distance, and the diameter of a polyhedral surface. Distances on the surface are measured by the length of a Euclidean shortest path. Our main result is a linear factor speedup for the computation of all shortest path edge sequences and the diameter of a convex polyhedral surface. This speedup is achieved...
The buy-at-bulk network design problem has been extensively studied in the general graph model. In this paper we consider the geometric version of the problem, where all points in a Euclidean space are candidates for network nodes. We present the first general approach for geometric versions of basic variants of the buy-at-bulk network design problem. It enables us to obtain quasi-polynomial-time...
We introduce the rank-sensitive priority queue — a data structure that always knows the minimum element it contains, for which insertion and deletion take O(log(n/r)) time, with n being the number of elements in the structure, and r being the rank of the element being inserted or deleted (r = 1 for the minimum, r = n for the maximum). We show how several elegant implementations of rank-sensitive priority...
Two years before WADS began, my father Martin Demaine and my six-year-old self designed and made puzzles as the Erik and Dad Puzzle Company, which distributed to toy stores across Canada. So began our journey into the interactions between algorithms and the arts. More and more, we find that our mathematical research and artistic projects converge, with the artistic side inspiring the mathematical...
We present skip-splay, the first binary search tree algorithm known to have a running time that nearly achieves the unified bound. Skip-splay trees require only O(m lg lg n + UB(σ)) time to execute a query sequence σ = σ1 ... σm. The skip-splay algorithm is simple and similar to the splay algorithm.
Cognitive experiments show that humans can read graph drawings in which all edge crossings are at right angles equally well as they can read planar drawings; they also show that the readability of a drawing is heavily affected by the number of bends along the edges. A graph visualization whose edges can only cross perpendicularly is called a RAC (Right Angle Crossing) drawing. This paper initiates...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.