Algorithms for shortest paths and d-cycle problems

Let G be a weighted graph with n vertices and m edges. We address the d-cycle problem, i.e., the problem of finding a subgraph of minimum weight with given cyclomatic number d. Hartvigsen [Minimum path bases, J. Algorithms 15 (1993) 125–142] presented an algorithm with running time O(n²m) and O(n^2d−1m²) for the cyclomatic numbers d=1 and d2, respectively. Using a (d+1)-shortest-paths algorithm, we develop a new more efficient algorithm for the d-cycle problem with running time O(n^2d−1+n²m+n³logn).     

Efficient algorithms to compute all articulation points of a permutation graph

Based on the geometric representation, an efficient algorithm is designed to find all articulation points of a permutation graph. The proposed algorithm takes onlyO(n logn) time andO(n) space, wheren represents the number of vertices. The proposed sequential algorithm can easily be implemented in parallel which takesO(logn) time andO(n) processors on an EREW PRAM. These are the first known algorithms for the problem on this class of graph.     

An efficient algorithm to solve connectivity problem on trapezoid graphs

The connectivity problem is a fundamental problem in graph theory. The best known algorithm to solve the connectivity problem on general graphs withn vertices andm edges takesO(K(G)mn ^1.5) time, whereK(G) is the vertex connectivity ofG. In this paper, an efficient algorithm is designed to solve vertex connectivity problem, which takesO(n ²) time andO(n) space for a trapezoid graph.     

A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem

In this paper, we focus on the directed minimum degree spanning tree problem and the minimum time broadcast problem. Firstly, we propose a polynomial time algorithm for the minimum degree spanning tree problem in directed acyclic graphs. The algorithm starts with an arbitrary spanning tree, and iteratively reduces the number of vertices of maximum degree. We can prove that the algorithm must reduce a vertex of the maximum degree for each phase, and finally result in an optimal tree. The algorithm terminates in O(mnlogn) time, where m and n are the numbers of edges and vertices of the graph, respectively. Moreover, we apply the new algorithm to the minimum time broadcast problem. Two consequences for directed acyclic graphs are: (1) the problem under the vertex-disjoint paths mode can be approximated within a factor of of the optimum in O(mnlogn)-time; (2) the problem under the edge-disjoint paths mode can be approximated within a factor of O(Δ^*/logΔ^*) of the optimum in O(mnlogn)-time, where Δ^* is the minimum k such that there is a spanning tree of the graph with maximum degree k.     

An optimal parallel connectivity algorithm

A synchronized parallel algorithm of depth O(n²/p) for p (≤n²/log²n) processors is given for the problem of computing connected components of an undirected graph. The speed-up of this algorithm is optimal in the sense that the depth of the algorithm is of the order of the running time of the fastest known sequential algorithm over the number of processors used.     

An Efficient Algorithm for the Complex Roots Problem

Given a univariate polynomialf(z) of degreenwith complex coefficients, whose norms are less than 2^min magnitude, the root problem is to find all the roots off(z) up to specified precision 2^−μ. Assuming the arithmetic model for computation, we provide an algorithm which has complexityO(nlog⁵nlogB), whereb= χ + μ, and χ = max{n,m}. This improves on the previous best known algorithm of Pan for the problem, which has complexityO(n²log²nlog(m+ μ)). A remarkable property of our algorithm is that it does not require any assumptions about the root separation off, which were either explicitly, or implicitly, required by previous algorithms. Moreover it also has a work-efficient parallel implementation. We also show that both the sequential and parallel implementations of the algorithm work without modification in the Boolean model of arithmetic. In this case, it follows from root perturbation estimates that we need only specify θ = ⌈n(B+ logn+ 3)⌉ bits of the binary representations of the real and imaginary parts of each of the coefficients off. We also show that by appropriate rounding of intermediate values, we can bound the number of bits required to represent all complex numbers occurring as intermediate quantities in the computation. The result is that we can restrict the numbers we use in every basic arithmetic operation to those having real and imaginary parts with at most φ bits, where[formula]and[formula]Thus, in the Boolean model, the overall work complexity of the algorithm is only increased by a multiplicative factor ofM(φ) (whereM(ψ) =O(ψ(log ψ) log log ψ) is the bit complexity for multiplication of integers of length ψ). The key result on which the algorithm is based, is a new theorem of Coppersmith and Neff relating the geometric distribution of the zeros of a polynomial to the distribution of the zeros of its high order derivatives. We also introduce several new techniques (splitting sets and “centered” points) which hinge on it. We also observe that our root finding algorithm can be efficiently parallelized to run in parallel timeO(log⁶nlogB) usingnprocessors.     

Paired domination on interval and circular-arc graphs

We study the paired-domination problem on interval graphs and circular-arc graphs. Given an interval model with endpoints sorted, we give an O(m+n) time algorithm to solve the paired-domination problem on interval graphs. The result is extended to solve the paired-domination problem on circular-arc graphs in O(m(m+n)) time.     

A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm

Recently, É. Tardos gave a strongly polynomial algorithm for the minimum-cost circulation problem and solved the open problem posed in 1972 by J. Edmonds and R.M. Karp. Her algorithm runs in O(m ² T(m, n) logm) time, wherem is the number of arcs,n is the number of vertices, andT(m, n) is the time required for solving a maximum flow problem in a network withm arcs andn vertices. In the present paper, taking an approach that is a dual of Tardos's, we also give a strongly polynomial algorithm for the minimum-cost circulation problem. Our algorithm runs in O(m ² S(m, n) logm) time and reduces the computational complexity, whereS(m, n) is the time required for solving a shortest path problem with a fixed origin in a network withm arcs,n vertices, and a nonnegative arc length function. The complexity is the same as that of Orlin's algorithm, recently developed by efficiently implementing the Edmonds-Karp scaling algorithm.     

New lower bounds for Hopcroft's problem

We establish new lower bounds on the complexity of the following basic geometric problem, attributed to John Hopcroft: Given a set ofn points andm hyperplanes in $\mathbb{R}^d $ , is any point contained in any hyperplane? We define a general class ofpartitioning algorithms, and show that in the worst case, for allm andn, any such algorithm requires time Ω(n logm + n ^2/3m^2/3 + m logn) in two dimensions, or Ω(n logm + n ^5/6m^1/2 + n^1/2m^5/6 + m logn) in three or more dimensions. We obtain slightly higher bounds for the counting version of Hopcroft's problem in four or more dimensions. Our planar lower bound is within a factor of 2O(log^*(n+m)) of the best known upper bound, due to Matou?ek. Previously, the best known lower bound, in any dimension, was Ω(n logm + m logn). We develop our lower bounds in two stages. First we define a combinatorial representation of the relative order type of a set of points and hyperplanes, called amonochromatic cover, and derive lower bounds on its size in the worst case. We then show that the running time of any partitioning algorithm is bounded below by the size of some monochromatic cover. As a related result, using a straightforward adversary argument, we derive aquadratic lower bound on the complexity of Hopcroft's problem in a surprisingly powerful decision tree model of computation.     

On the dimension of trees

It is proved that for trees (and forests) G one has dimG?3 log⁺₂∣G∣(where dim G, the dimension of G, is the minimum k such that G is embeddable into a product of k complete graphs; ∣G∣ is the size of G). Moreover, if m(G) is the quotient of G obtained by identifying the points with coinciding neighbour sets, one has, for forests G, log⁺₂ ∣m(G)∣ ? 1 ? dimG ? 3 log⁺₂m(G>) + 1. Also, for the bipartite dimension bid G (arising from embeddings into P^k₃) one has bid G ? 8 log⁺₂ ∣G ∣.     

An optimal pram algorithm for a spanning tree on trapezoid graphs

LetG be a graph withn vertices andm edges. The problem of constructing a spanning tree is to find a connected subgraph ofG withn vertices andn?1 edges. In this paper, we propose anO(logn) time parallel algorithm withO(n/logn), processors on an EREW PRAM for constructing a spanning tree on trapezoid graphs.     

Fast algorithms for identifying maximal common connected sets of interval graphs

Given a family of interval graphs F={G₁=(V,E₁),…,G_k=(V,E_k)} on the same vertices V, a set S⊂V is a maximal common connected set of F if the subgraphs of G_i,1?i?k, induced by S are connected in all G_i and S is maximal for the inclusion order. The maximal general common connected set for interval graphs problem (gen-CCPI) consists in efficiently computing the partition of V in maximal common connected sets of F. This problem has many practical applications, notably in computational biology. Let n=|V| and . For k?2, an algorithm in O((kn+m)logn) time is presented in Habib et al. [Maximal common connected sets of interval graphs, in: Combinatorial Pattern Matching (CPM), Lecture Notes in Computer Science, vol. 3109, Springer, Berlin, 2004, pp. 359-372]. In this paper, we improve this bound to O(knlogn+m). Moreover, if the interval graphs are given as k sets of n intervals, which is often the case in bioinformatics, we present a simple time algorithm.     

Multiplicative infinite loop space theory

Let G be a finitely presented group given by its pre-abelian presentation <X1,…,Xm; Xe11ζ1,…,Xemmζ,ζm+1,…>, where ei≥0 for i = 1,…, m and ζj?G′ for j≥1. Let N be the subgroup of G generated by the normal subgroups [xeii, G] for i = 1,…, m. Then Dn+2(G)≡γn+2(G) (modNG′) for all n≥0, where G” is the second commutator subgroup of G,γn+2(G) is the (n+2)th term of the lower central series of G and Dn+2(G) = G∩(1+△n+2(G)) is the (n+2)th dimension subgroup of G.     

On finding a large number of 3D points with a small diameter

Given a set S of n points in R³, we wish to decide whether S has a subset of size at least k with Euclidean diameter at most r. It is unknown whether this decision problem is NP-hard. The two closely related optimization problems, (i) finding a largest subset of diameter at most r, and (ii) finding a subset of the smallest diameter of size at least k, were recently considered by Afshani and Chan. For maximizing the size, they presented several polynomial-time algorithms with constant approximation factors, the best of which has a factor of . For maximizing the diameter, they presented a polynomial-time approximation scheme. In this paper, we present improved approximation algorithms for both optimization problems. For maximizing the size, we present two algorithms: the first one improves the approximation factor to 2.5 and the running time by an O(n) factor; the second one improves the approximation factor to 2 and the running time by an O(n²) factor. For minimizing the diameter, we improve the running time of the PTAS from O(nlogn+2^O(1/ε3)n) to O(nlogn+2^{O(1/(ε1.5logε))}n).     

A trust region method for solving the decentralized static output feedback design problem

The shortest-paths problem is a fundamental problem in graph theory and finds diverse applications in various fields. This is why shortest path algorithms have been designed more thoroughly than any other algorithm in graph theory. A large number of optimization problems are mathematically equivalent to the problem of finding shortest paths in a graph. The shortest-path between a pair of vertices is defined as the path with shortest length between the pair of vertices. The shortest path from one vertex to another often gives the best way to route a message between the vertices. This paper presents anO(n ²) time sequential algorithm and anO(n ²/p+logn) time parallel algorithm on EREW PRAM model for solving all pairs shortest paths problem on circular-arc graphs, wherep andn represent respectively the number of processors and the number of vertices of the circular-arc graph.     

An algebraic approach to approximate evaluation of a polynomial on a set of real points

The previous best algorithm for approximate evaluation of a polynomial on a real set was due to Rokhlin and required of the order ofmu+nu ³ infinite precision arithmetic operations to approximate [on a fixed bounded setX(m) ofm+1 real points] a degreen polynomial $p\left( z \right) = \sum\nolimits_{i = 0}^n {p_i x^i } $ within the error bound $2^{ - u} \sum\nolimits_{i = 0}^n {\left| {p_i } \right|} $ . We develop an approximation algorithm which exploits algebraic computational techniques and decreases Rokhlin's record estimate toO(mlog² u+nmin-u, logn}). For logu=o(logn), this result may also be favorably compared with the record boundO(m+n)log² n) on the complexity of the exact multipoint polynomial evaluation. The new algorithm can be performed in the fields (or rings) generated by the input values, which enables us to decrease the precision of the computations [by using modular (residue) arithmetic] and to simplify our computations further in the case whereu=O(logn). Our algorithm allows NC and simultaneously processor efficient parallel implementation. Because of the fundamental nature of the multipoint polynomial evaluation, our results have further applications to numerical and algebraic computational problems. In passing, we also show a substantial improvement in the Chinese remainder algorithm for integers based on incorporating Kaminski's fast residue computation.     

Ray Shooting Amidst Convex Polygons in 2D

We consider the problem of ray shooting in a two-dimensional scene consisting ofmconvex polygons with a total ofnedges. We present a data structure that requiresO(mn log m) space and preprocessing time and that answers a ray shooting query inO(log² m log² n) time. If the polygons are pairwise disjoint, the space and preprocessing time can be improved toO((m²+n)log m) andO((m²+n log n)log m), respectively. Our algorithm also works for a collection of disjoint simple polygons. We also show that if we allow onlyO(n) space, a ray shooting query among a collection of disjoint simple polygons can be answered in timeO(m/[formula]¹⁺ log² n) time, for any >0.     

On the parallel computation of the biconnected and strongly connected co-components of graphs

In this paper, we consider the problems of co-biconnectivity and strong co-connectivity, i.e., computing the biconnected components and the strongly connected components of the complement of a given graph. We describe simple sequential algorithms for these problems, which work on the input graph and not on its complement, and which for a graph on n vertices and m edges both run in optimal O(n+m) time. Our algorithms are not data structure-based and they employ neither breadth-first-search nor depth-first-search.Unlike previous linear co-biconnectivity and strong co-connectivity sequential algorithms, both algorithms admit efficient parallelization. The co-biconnectivity algorithm can be parallelized resulting in an optimal parallel algorithm that runs in time using processors. The strong co-connectivity algorithm can also be parallelized to yield an -time and O(m^1.188/logn)-processor solution. As a byproduct, we obtain a simple optimal O(logn)-time parallel co-connectivity algorithm.Our results show that, in a parallel process environment, the problems of computing the biconnected components and the strongly connected components can be solved with better time-processor complexity on the complement of a graph rather than on the graph itself.     

A polynomial time algorithm for a chance-constrained single machine scheduling problem

This paper gives an O(n√nlog³n) time algorithm for the chance-constrained sequencing problem on a single machine, where n is the number of jobs and the objective is to minimize the number of jobs which are early with probability not smaller than α (a given constant) against the common due time d.