Smallest k-point enclosing rectangle and square of arbitrary orientation

Given a set of n points in 2D, the problem of identifying the smallest rectangle of arbitrary orientation, and containing exactly k(?n) points is studied in this paper. The worst case time and space complexities of the proposed algorithm are O(n²logn+nk(n−k)(n−k+logk)) and O(n), respectively. The algorithm is then used to identify the smallest square of arbitrary orientation, and containing exactly k points in O(n²logn+kn²(n−k)logn) time.     

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.     

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.     

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.     

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.     

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.     

Primal-dual approximation algorithms for the Prize-Collecting Steiner Tree Problem

The primal-dual scheme has been used to provide approximation algorithms for many problems. Goemans and Williamson gave a (2−1/(n−1))-approximation for the Prize-Collecting Steiner Tree Problem that runs in O(n³logn) time—it applies the primal-dual scheme once for each of the n vertices of the graph. We present a primal-dual algorithm that runs in O(n²logn), as it applies this scheme only once, and achieves the slightly better ratio of (2−2/n). We also show a tight example for the analysis of the algorithm and discuss briefly a couple of other algorithms described in the literature.     

Jebelean-Weber's algorithm without spurious factors

Tudor Jebelean and Ken Weber introduced an algorithm for finding (a,b)-pairs satisfying au+bv≡0 (mod k), with . It is based on Sorenson's “k-ary reduction”. This algorithm does not preserve the GCD and its related GCD algorithm has an O(n²) time bit complexity in the worst case. We present a modified version which avoids this problem. We show that a slightly modified GCD algorithm has an O(n²/logn) running time in the worst case, where n is the number of bits of the larger input.     

A 2-approximation NC algorithm for connected vertex cover and tree cover

The connected vertex cover problem is a variant of the vertex cover problem, in which a vertex cover is additional required to induce a connected subgraph in a given connected graph. The problem is known to be NP-hard and to be at least as hard to approximate as the vertex cover problem is. While several 2-approximation NC algorithms are known for vertex cover, whether unweighted or weighted, no parallel algorithm with guaranteed approximation is known for connected vertex cover. Moreover, converting the existing sequential 2-approximation algorithms for connected vertex cover to parallel ones results in RNC algorithms of rather high complexity at best.In this paper we present a 2-approximation NC (and RNC) algorithm for connected vertex cover (and tree cover). The NC algorithm runs in O(log²n) time using O(Δ²(m+n)/logn) processors on an EREW-PRAM, while the RNC algorithm runs in O(logn) expected time using O(m+n) processors on a CRCW-PRAM, when a given graph has n vertices and m edges with maximum vertex degree of Δ.     

Parallel Algorithms for the Edge-Coloring and Edge-Coloring Update Problems

LetG(V,E) be a simple undirected graph with a maximum vertex degree Δ(G) (or Δ for short), |V| =nand |E| =m. An edge-coloring ofGis an assignment to each edge inGa color such that all edges sharing a common vertex have different colors. The minimum number of colors needed is denoted by χ′(G) (called thechromatic index). For a simple graphG, it is known that Δ ≤ χ′(G) ≤ Δ + 1. This paper studies two edge-coloring problems. The first problem is to perform edge-coloring for an existing edge-colored graphGwith Δ + 1 colors stemming from the addition of a new vertex intoG. The proposed parallel algorithm for this problem runs inO(Δ^3/2log³Δ + Δ logn) time usingO(max{nΔ, Δ³}) processors. The second problem is to color the edges of a given uncolored graphGwith Δ + 1 colors. For this problem, our first parallel algorithm requiresO(Δ^5.5log³Δ logn+ Δ⁵log⁴n) time andO(max{n²Δ,nΔ³}) processors, which is a slight improvement on the algorithm by H. J. Karloff and D. B. Shmoys [J. Algorithms8 (1987), 39–52]. Their algorithm costsO(Δ⁶log⁴n) time andO(n²Δ) processors if we use the fastest known algorithm for finding maximal independent sets by M. Goldberg and T. Spencer [SIAM J. Discrete Math.2 (1989), 322–328]. Our second algorithm requiresO(Δ^4.5log³Δ logn+ Δ⁴log⁴n) time andO(max{n²,nΔ³}) processors. Finally, we present our third algorithm by incorporating the second algorithm as a subroutine. This algorithm requiresO(Δ^3.5log³Δ logn+ Δ³log⁴n) time andO(max{n²log Δ,nΔ³}) processors, which improves, by anO(Δ^2.5) factor in time, on Karloff and Shmoys' algorithm. All of these algorithms run in the COMMON CRCW PRAM model.     

Labeling points with given rectangles

In this paper, we consider the following problem: Given n pairs of a point and an axis-parallel rectangle in the plane, place each rectangle at each point in order that the point lies on the corner of the rectangle and the rectangles do not intersect. If the size of the rectangles may be enlarged or reduced at the same factor, maximize the factor. This paper generalizes the results of Formann and Wagner [Proc. 7th Annual ACM Symp. on Comput. Geometry (SoCG'91), 1991, pp. 281-288]. They considered the uniform squares case and showed that there is no polynomial time algorithm less than 2-approximation. We present a 2-approximation algorithm of the non-uniform rectangle case which runs in O(n²logn) time and takes O(n²) space. We also show that the decision problem can be solved in O(nlogn) time and space in the RAM model by transforming the problem to a simpler geometric problem.     

Computing shortest transversals

We present anO(nlog² n) time andO(n) space algorithm for computing the shortest line segment that intersects a set ofn given line segments or lines in the plane. If the line segments do not intersect the algorithm may be trimmed to run inO(nlogn) time. Furthermore, in combination with linear programming the algorithm will also find the shortest line segment that intersects a set ofn isothetic rectangles in the plane inO(nlogk) time, wherek is the combinatorial complexity of the space of transversals andk≤4n. These results find application in: (1) line-fitting between a set ofn data ranges where it is desired to obtain the shortestline-of-fit, (2) finding the shortest line segment from which a convexn-vertex polygon is weakly externally visible, and (3) determing the shortestline-of-sight between two edges of a simplen-vertex polygon, for whichO(n) time algorithms are also given. All the algorithms are based on the solution to a new fundamental geometric optimization problem that is of independent interest and should find application in different contexts as well.     

Randomized parallel list ranking for distributed memory multiprocessors

We present a randomized parallel list ranking algorithm for distributed memory multiprocessors, using a BSP type model. We first describe a simple version which requires, with high probability, log(3p)+log ln(n)=Õ(logp+log logn) communication rounds (h-relations withh=Õ(n/p)) andÕ(n/p)) local computation. We then outline an improved version that requires high probability, onlyr?(4k+6) log(2/3p)+8=Õ(k logp) communication rounds wherek=min{i?0 |ln(i+1)n?(2/3p)²ⁱ⁺¹}. Notekn) is an extremely small number. Forn andp?4, the value ofk is at most 2. Hence, for a given number of processors,p, the number of communication rounds required is, for all practical purposes, independent ofn. Forn?1, 500,000 and 4?p?2048, the number of communication rounds in our algorithm is bounded, with high probability, by 78, but the actual number of communication rounds observed so far is 25 in the worst case. Forn?10010100 and 4?p?2048, the number of communication rounds in our algorithm is bounded, with high probability, by 118; and we conjecture that the actual number of communication rounds required will not exceed 50. Our algorithm has a considerably smaller member of communication rounds than the list ranking algorithm used in Reid-Miller’s empirical study of parallel list ranking on the Cray C-90.⁽¹⁾ To our knowledge, Reid-Miller’s algorithm⁽¹⁾ was the fastest list ranking implementation so far. Therefore, we expect that our result will have considerable practical relevance.     

A note on point location in arrangements of hyperplanes

We give an algorithm for point location in an arrangement of n hyperplanes in E^d with running time poly(d,logn) and space O(n^d). The space improves on the O(n^d+ε) bound of Meiser's algorithm [Inform. and Control 106 (1993) 286] that has a similar running time.     

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.     

Sieve algorithms for perfect power testing

A positive integern is a perfect power if there exist integersx andk, both at least 2, such thatn=x ^k . The usual algorithm to recognize perfect powers computes approximatekth roots forklog ₂ n, and runs in time O(log³ n log log logn).First we improve this worst-case running time toO(log³ n) by using a modified Newton's method to compute approximatekth roots. Parallelizing this gives anNC ² algorithm.Second, we present a sieve algorithm that avoidskth-root computations by seeing if the inputn is a perfectkth power modulo small primes. Ifn is chosen uniformly from a large enough interval, the average running time isO(log² n).Third, we incorporate trial division to give a sieve algorithm with an average running time ofO(log² n/log² logn) and a median running time ofO(logn).The two sieve algorithms use a precomputed table of small primes. We give a heuristic argument and computational evidence that the largest prime needed in this table is (logn)^1+O(1); assuming the Extended Riemann Hypothesis, primes up to (logn)^2+O(1) suffice. The table can be computed in time roughly proportional to the largest prime it contains.We also present computational results indicating that our sieve algorithms perform extremely well in practice.This work forms part of the second author's Ph.D. thesis at the University of Wisconsin-Madison, 1991. This research was sponsored by NSF Grants CCR-8552596 and CCR-8504485.     

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.     

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.