A note on maximum independent sets in rectangle intersection graphs

Finding the maximum independent set in the intersection graph of n axis-parallel rectangles is NP-hard. We re-examine two known approximation results for this problem. For the case of rectangles of unit height, Agarwal, van Kreveld and Suri [Comput. Geom. Theory Appl. 11 (1998) 209-218] gave a (1+1/k)-factor algorithm with an O(nlogn+n^2k−1) time bound for any integer constant k?1; we describe a similar algorithm running in only O(nlogn+nΔ^k−1) time, where Δ?n denotes the maximum number of rectangles a point can be in. For the general case, Berman, DasGupta, Muthukrishnan and Ramaswami [J. Algorithms 41 (2001) 443-470] gave a ⌈log_kn⌉-factor algorithm with an O(n^k+1) time bound for any integer constant k?2; we describe similar algorithms running in O(nlogn+nΔ^k−2) and n^O(k/logk) time.     

Speedup of Vidyasankar's algorithm for the group k-exclusion problem

Vidyasankar introduced a combined problem of k-exclusion and group mutual exclusion, called the group k-exclusion problem, which occurs in a situation where philosophers with the same interest can attend a forum in a meeting room, and up to k meeting rooms are available. We propose an improvement to Vidyasankar's algorithm. Waiting times in the trying region in the original algorithm and in our algorithm are bounded by n(n−k)c+O(n³(n−k))l and (n−k)c+O(n(n−k)²)l, respectively, where n is the number of processes, l is an upper bound on the time between successive two atomic steps, and c is an upper bound on the time that any philosopher spends in a forum.     

An improved algorithm for the maximum agreement subtree problem

In this paper, we solve the maximum agreement subtree problem for a set T of k rooted leaf-labeled evolutionary trees on n leaves where T contains a binary tree. We show that the O(kn³)-time dynamic-programming algorithm proposed by Bryant [Building trees, hunting for trees, and comparing trees: theory and methods in phylogenetic analysis, Ph.D. thesis, Dept. Math., University of Canterbury, 1997, pp. 174-182] can be implemented in O(kn²+n²logk−2nloglogn) and O(kn3−1/(k−1)) time by using multidimensional range search related data structures proposed by Gabow et al. [Scaling and related techniques for geometry problems, in: Proc. 16th Annual ACM Symp. on Theory of Computing, 1984, pp. 135-143] and Bentley [Multidimensional binary search trees in database applications, IEEE Trans. Softw. Eng. SE-5 (4) (1979) 333-340], respectively. When k<2+(logn−logloglogn)/(loglogn), the first implementation will be significantly faster than Bryant's algorithm. For k=3, it yields the best known algorithm which runs in O(n²lognloglogn)-time.     

On constructing the relative neighborhood graphs in EuclideanK-dimensional spaces

In this paper, a new algorithm for constructing the relative neighborhood graph(RNG) of ann points set in Euclideank-dimensional space is presented, for fixedk≥3. The worst case running time of the algorithm isO(n ^2?a(k) (logn)^1?a(k) ), fora(k)=2^?(k+1), which is under the assumption that no three input points form an isosceles triangle. Previous algorithms needO(n ²) time. Our algorithm proceeds in two phases. First, a supergraph ofRNG withO(n) edges is constructed and then those edges which do not belong toRNG are eliminated.     

Computing the subset partial order for dense families of sets

We give an algorithm to compute the subset partial order (called the subset graph) for a family F of sets containing k sets with N elements in total and domain size n. Our algorithm requires O(nk²/logk) time and space on a Pointer Machine. When F is dense, i.e. N=Θ(nk), the algorithm requires O(N²/log²N) time and space. We give a construction for a dense family whose subset graph is of size Θ(N²/log²N), indicating the optimality of our algorithm for dense families. The subset graph can be dynamically maintained when F undergoes set insertions and deletions in O(nk/logk) time per update (that is sub-linear in N for the case of dense families). If we assume words of b?k bits, allow bits to be packed in words, and use bitwise operations, the above running time and space requirements can be reduced by a factor of blog(k/b+1)/logk and b²log(k/b+1)/logk respectively.     

Dynamic normal forms and dynamic characteristic polynomial

We present the first fully dynamic algorithm for computing the characteristic polynomial of a matrix. In the generic symmetric case, our algorithm supports rank-one updates in O(n²logn) randomized time and queries in constant time, whereas in the general case the algorithm works in O(n²klogn) randomized time, where k is the number of invariant factors of the matrix. The algorithm is based on the first dynamic algorithm for computing normal forms of a matrix such as the Frobenius normal form or the tridiagonal symmetric form. The algorithm can be extended to solve the matrix eigenproblem with relative error 2^−b in additional O(nlog²nlogb) time. Furthermore, it can be used to dynamically maintain the singular value decomposition (SVD) of a generic matrix. Together with the algorithm, the hardness of the problem is studied. For the symmetric case, we present an Ω(n²) lower bound for rank-one updates and an Ω(n) lower bound for element updates.     

Conflict-Free Chromatic Art Gallery Coverage

We consider a chromatic variant of the art gallery problem, where each guard is assigned one of k distinct colors. A placement of such colored guards is conflict-free if each point of the polygon is seen by some guard whose color appears exactly once among the guards visible to that point. What is the smallest number k(n) of colors that ensure a conflict-free covering of all n-vertex polygons? We call this the conflict-free chromatic art gallery problem. Our main result shows that k(n) is O(logn) for orthogonal and for monotone polygons, and O(log² n) for arbitrary simple polygons. By contrast, if all guards visible from each point must have distinct colors, then k(n) is Ω(n) for arbitrary simple polygons, as shown by Erickson and LaValle (Robotics: Science and Systems, vol. VII, pp. 81–88, 2012). The problem is motivated by applications in distributed robotics and wireless sensor networks but is also of interest from a theoretical point of view.     

Range mode and range median queries in constant time and sub-quadratic space

Given a list of n items and a function defined over sub-lists, we study the space required for computing the function for arbitrary sub-lists in constant time.For the function mode we improve the previously known space bound O(n²/logn) to O(n²loglogn/log²n) words.For median the space bound is improved to O(n²loglog²n/log²n) words from O(n²⋅log(k)n/logn), where k is an arbitrary constant and log(k) is the iterated logarithm.     

Finding an Euclidean anti--centrum location of a set of points

An obnoxious facility is to be located inside a polygonal region of the plane, maximizing the sum of the k smallest weighted Euclidean distances to n given points, each protected by some polygonal forbidden region. For the unweighted case and k fixed an O(n²logn) time algorithm is presented. For the weighted case a thorough study of the relevant structure of the multiplicatively weighted order-k-Voronoi diagram leads to the design of an O(kn³+n³logn) time algorithm for finding an optimal solution to the anti-t-centrum problem for every t=1,…,k, simultaneously.     

Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax k vertex-disjoint paths in a directed acyclic graph

This paper is composed of two parts. In the first part, an improved algorithm is presented for the problem of finding length-bounded two vertex-disjoint paths in an undirected planar graph. The presented algorithm requires O(n³bmin) time and O(n²bmin) space, where bmin is the smaller of the two given length bounds. In the second part of this paper, we consider the minmax k vertex-disjoint paths problem on a directed acyclic graph, where k?2 is a constant. An improved algorithm and a faster approximation scheme are presented. The presented algorithm requires O(nk+1Mk−1) time and O(nkMk−1) space, and the presented approximation scheme requires O((1/?)^k−1n2klogk−1M) time and O((1/?)^k−1n2k−1logk−1M) space, where ? is the given approximation parameter and M is the length of the longest path in an optimal solution.     

Towards optimal range medians

We consider the following problem: Given an unsorted array of n elements, and a sequence of intervals in the array, compute the median in each of the subarrays defined by the intervals. We describe a simple algorithm which needs O(nlogk+klogn) time to answer k such median queries. This improves previous algorithms by a logarithmic factor and matches a comparison lower bound for k=O(n). The space complexity of our simple algorithm is O(nlogn) in the pointer machine model, and O(n) in the RAM model. In the latter model, a more involved O(n) space data structure can be constructed in O(nlogn) time where the time per query is reduced to O(logn/loglogn). We also give efficient dynamic variants of both data structures, achieving O(log²n) query time using O(nlogn) space in the comparison model and O((logn/loglogn)²) query time using O(nlogn/loglogn) space in the RAM model, and show that in the cell-probe model, any data structure which supports updates in O(log^O(1)n) time must have Ω(logn/loglogn) query time.Our approach naturally generalizes to higher-dimensional range median problems, where element positions and query ranges are multidimensional—it reduces a range median query to a logarithmic number of range counting queries.     

Improved deterministic algorithms for weighted matching and packing problems

Based on the method of (n,k)-universal sets, we present a deterministic parameterized algorithm for the weighted rd-matching problem with time complexity O^∗(4^{(r−1)k+o(k)}), improving the previous best upper bound O^∗(4^rk+o(k)). In particular, the algorithm applied to the unweighted 3d-matching problem results in a deterministic algorithm with time O^∗(16^k+o(k)), improving the previous best result O^∗(21.26^k). For the weighted r-set packing problem, we present a deterministic parameterized algorithm with time complexity O^∗(2^{(2r−1)k+o(k)}), improving the previous best result O^∗(2^2rk+o(k)). The algorithm, when applied to the unweighted 3-set packing problem, has running time O^∗(32^k+o(k)), improving the previous best result O^∗(43.62^k+o(k)). Moreover, for the weighted r-set packing and weighted rd-matching problems, we give a kernel of size O(k^r), which is the first kernelization algorithm for the problems on weighted versions.     

A Nonoblivious Bus Access Scheme Yields an Optimal Partial Sorting Algorithm

This paper focuses on a linear array ofnnodes withmultiple shared busesas a practically feasible model for parallel processing. Letkbe the number of shared buses. A nonoblivious scheme for mutually exclusive access tokshared buses is proposed. The effectiveness of the scheme is demonstrated by proposing an algorithm for solving a partial sort problem, which can be efficiently executed on the array according to the scheme. Thepartial sort problemwith parametermis the problem of sorting a subsetS′ of a given setS, whereS′ is the set of elements less than or equal to themth smallest element inS. Ifm= 1, then it is solved by an algorithm for finding the smallest element inS, and ifm=n, then it is solved by adapting normal sorting algorithm. The time complexity (9m/k) log₂log₂n+ 3.467[formula]+O(m/k+ (n/k)^1/4) of the proposed algorithm matches a lower bound Ω ([formula]+m/k) with respect tonandk, ifmis small enough to satisfym=O([formula]/log logn).     

Bandwidth on AT-free graphs

We study the classical Bandwidth problem from the viewpoint of parametrised algorithms. Given a graph G=(V,E) and a positive integer k, the Bandwidth problem asks whether there exists a bijective function β:{1,…,∣V∣}→V such that for every edge uv∈E, ∣β⁻¹(u)−β⁻¹(v)∣≤k. It is known that under standard complexity assumptions, no algorithm for Bandwidth with running time of the form f(k)n^O(1) exists, even when the input is restricted to trees. We initiate the search for classes of graphs where such algorithms do exist. We present an algorithm with running time n⋅2^O(klogk) for Bandwidth on AT-free graphs, a well-studied graph class that contains interval, permutation, and cocomparability graphs. Our result is the first non-trivial algorithm that shows fixed-parameter tractability of Bandwidth on a graph class on which the problem remains NP-complete.     

Computing largest empty circles with location constraints

LetQ = {q₁, q₂,..., q_n} be a set ofn points on the plane. The largest empty circle (LEG) problem consists in finding the largest circleC with center in the convex hull ofQ such that no pointq _i εQ lies in the interior ofC. Shamos recently outlined anO(n logn) algorithm for solving this problem.⁽⁹⁾ In this paper it is shown that this algorithm does not always work correctly. A different approach is proposed here and shown to also result in anO(n logn) algorithm. The new approach has the advantage that it can also solve more general problems. In particular, it is shown that if the center ofC is constrained to lie in an arbitrary convexn-gon, an0(n logn) algorithm can still be obtained. Finally, an0(n logn +k logn) algorithm is given for solving this problem when the center ofC is constrained to lie in an arbitrary simplen-gonP. wherek denotes the number of intersections occurring between edges ofP and edges of the Voronoi diagram ofQ andk ?O(n ²).     

An optimal speed-up parallel algorithm for triangulating simplicial point sets in space

Previous research on developing parallel triangulation algorithms concentrated on triangulating planar point sets.O(log³ n) running time algorithms usingO(n) processors have been developed in Refs. 1 and 2. Atallah and Goodrich⁽³⁾ presented a data structure that can be viewed as a parallel analogue of the sequential plane-sweeping paradigm, which can be used to triangulate a planar point set inO(logn loglogn) time usingO(n) processors. Recently Merks⁽⁴⁾ described an algorithm for triangulating point sets which runs inO(logn) time usingO(n) processors, and is thus optimal. In this paper we develop a parallel algorithm for triangulating simplicial point sets in arbitrary dimensions based on the idea of the sequential algorithm presented in Ref. 5. The algorithm runs inO(log² n) time usingO(n/logn) processors. The algorithm hasO(n logn) as the product of the running time and the number of processors; i.e., an optimal speed-up.     

Fast computation of smallest enclosing circle with center on a query line segment

Here we propose an efficient algorithm for computing the smallest enclosing circle whose center is constrained to lie on a query line segment. Our algorithm preprocesses a given set of n points P={p₁,p₂,…,pn} such that for any query line or line segment L, it efficiently locates a point c on L that minimizes the maximum distance among the points in P from c. Roy et al. [S. Roy, A. Karmakar, S. Das, S.C. Nandy, Constrained minimum enclosing circle with center on a query line segment, in: Proc. of the 31st Mathematical Foundation of Computer Science, 2006, pp. 765-776] have proposed an algorithm that solves the query problem in O(log²n) time using O(nlogn) preprocessing time and O(n) space. Our algorithm improves the query time to O(logn); but the preprocessing time and space complexities are both O(n²).     

Computing sparse permanents faster

Bax and Franklin (2002) gave a randomized algorithm for exactly computing the permanent of any n×n zero-one matrix in expected time exp[−Ω(n1/3/(2lnn))]n². Building on their work, we show that for any constant C>0 there is a constant ?>0 such that the permanent of any n×n (real or complex) matrix with at most Cn nonzero entries can be computed in deterministic time n(2−?) and space O(n). This improves on the Ω(n²) runtime of Ryser's algorithm for computing the permanent of an arbitrary real or complex matrix.     

Improved algorithms for the k simple shortest paths and the replacement paths problems

Given a directed, non-negatively weighted graph G=(V,E) and s,t∈V, we consider two problems. In the k simple shortest paths problem, we want to find the k simple paths from s to t with the k smallest weights. In the replacement paths problem, we want the shortest path from s to t that avoids e, for every edge e in the original shortest path from s to t. The best known algorithm for the k simple shortest paths problem has a running of O(k(mn+n²logn)). For the replacement paths problem the best known result is the trivial one running in time O(mn+n²logn).In this paper we present two simple algorithms for the replacement paths problem and the k simple shortest paths problem in weighted directed graphs (using a solution of the All Pairs Shortest Paths problem). The running time of our algorithm for the replacement paths problem is O(mn+n²loglogn). For the k simple shortest paths we will perform O(k) iterations of the second simple shortest path (each in O(mn+n²loglogn) running time) using a useful property of Roditty and Zwick [L. Roditty, U. Zwick, Replacement paths and k simple shortest paths in unweighted directed graphs, in: Proc. of International Conference on Automata, Languages and Programming (ICALP), 2005, pp. 249-260]. These running times immediately improve the best known results for both problems over sparse graphs.Moreover, we prove that both the replacement paths and the k simple shortest paths (for constant k) problems are not harder than APSP (All Pairs Shortest Paths) in weighted directed graphs.     

On finding a widest empty 1-corner corridor

A 1-corner corridor through a set S of points is an open subset of CH(S) containing no points from S and bounded by a pair of parallel polygonal lines each of which contains two segments. Given a set of n points in the plane, we consider the problem of computing a widest empty 1-corner corridor. We describe an algorithm that solves the problem in O(n⁴logn) time and O(n) space. We also present an approximation algorithm that computes in time a solution with width at least a fraction (1−ε) of the optimal, for any small enough ε>0.