A fast algorithm for a class of bottleneck problems

We show that if a bottleneck problem of sizem with an ordered list of element costs can be solved in O(ξ(m)) time, then the problem with an unordered list of element costs can be solved in O(ξ(m)) log^* m) time.     

Construction of Aho Corasick automaton in linear time for integer alphabets

We present a new simple algorithm that constructs an Aho Corasick automaton for a set of patterns, P, of total length n, in O(n) time and space for integer alphabets. Processing a text of size m over an alphabet Σ with the automaton costs O(mlog|Σ|+k), where there are k occurrences of patterns in the text.A new, efficient implementation of nodes in the Aho Corasick automaton is introduced, which works for suffix trees as well.     

Listing all the minimum spanning trees in an undirected graph

Efficient polynomial time algorithms are well known for the minimum spanning tree problem. However, given an undirected graph with integer edge weights, minimum spanning trees may not be unique. In this article, we present an algorithm that lists all the minimum spanning trees included in the graph. The computational complexity of the algorithm is O(N(mn+n ² log n)) in time and O(m) in space, where n, m and N stand for the number of nodes, edges and minimum spanning trees, respectively. Next, we explore some properties of cut-sets, and based on these we construct an improved algorithm, which runs in O(N m log n) time and O(m) space. These algorithms are implemented in C language, and some numerical experiments are conducted for planar as well as complete graphs with random edge weights.     

Counting edge crossings in a 2-layered drawing

Given a bipartite graph G=(V,W,E) with a bipartition {V,W} of a vertex set and an edge set E, a 2-layered drawing of G in the plane means that the vertices of V and W are respectively drawn as distinct points on two parallel lines and the edges as straight line segments. We consider the problem of counting the number of edge crossings. In this paper, we design two algorithms to this problem based on the dynamic programming and divide-and-conquer approaches. These algorithms run in O(n₁n₂) time and O(m) space and in O(min{n₁n₂,|E|log(min{|V|,|W|})}) time and O(m) space, respectively. Our algorithms outperform the previously fastest Θ(|E|log(min{|V|,|W|})) time algorithm for dense graphs.     

All-pairs shortest-paths computation in the presence of negative cycles

We present an algorithm that solves the all-pairs shortest-paths problem on a directed graph with n vertices and m arcs in time O(nm+n²logn), where the arcs are assigned real, possibly negative costs. Our algorithm is new in the following respect. It computes the distance μ(v,w) between each pair v,w of vertices even in the presence of negative cycles, where μ(v,w) is defined as the infimum of the costs of all directed paths from v to w.     

Fully dynamic biconnectivity in graphs

We present an algorithm for maintaining the biconnected components of a graph during a sequence of edge insertions and deletions. It requires linear storage and preprocessing time. The amortized running time for insertions and for deletions isO(m ^2/3 ), wherem is the number of edges in the graph. Any query of the form ‘Are the verticesu andv biconnected?’ can be answered in timeO(1). This is the first sublinear algorithm for this problem. We can also output all articulation points separating any two vertices efficiently. If the input is a plane graph, the amortized running time for insertions and deletions drops toO(√n logn) and the query time isO(log² n), wheren is the number of vertices in the graph. The best previously known solution takes timeO(n ^2/3 ) per update or query.     

Approximation algorithms for general parallel task scheduling

A general parallel task scheduling problem is considered. A task can be processed in parallel on one of several alternative subsets of processors. The processing time of the task depends on the subset of processors assigned to the task. We first show the hardness of approximating the problem for both preemptive and nonpreemptive cases in the general setting. Next we focus on linear array network of m processors. We give an approximation algorithm of ratio O(logm) for nonpreemptive scheduling, and another algorithm of ratio 2 for preemptive scheduling. Finally, we give a nonpreemptive scheduling algorithm of ratio O(log²m) for m×m two-dimensional meshes.     

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 Δ.     

Edit distance for a run-length-encoded string and an uncompressed string

We propose a new algorithm for computing the edit distance of an uncompressed string against a run-length-encoded string. For an uncompressed string of length n and a compressed string with M runs, the algorithm computes their edit distance in time O(Mn). This result directly implies an O(min{mN,Mn}) time algorithm for strings of lengths m and n with M and N runs, respectively. It improves the previous best known time bound O(mN+Mn).     

An optimization algorithm for free-form surface partitioning based on weighted gaussian image

Partitioning free-form surfaces into sub-patches and finding optimal representative normal for each patch to maximize a global objective function is an important two-level operation in diverse industrial applications. In this paper, by solving a maximum hemispherical partitioning problem raised from a weighted Gaussian image, an optimization algorithm is proposed to partition a free-form surface into two sub-patches and simultaneously report the optimal representative normals. By discretizing the free-form surface with W sample points and clustering normals on the surface with m distinct sample normals, the proposed algorithm is designed, in general, with O(m²W²) time complexity and O(W²) space complexity, and in particular, if the surface is convex, in O(m² log m) time complexity. Case studies with four representative examples are presented and a real world application is exploited to demonstrate the effectiveness and usefulness of the proposed algorithm.     

An efficient retrieval selection algorithm for video servers with random duplicated assignment storage technique

Random Duplicated Assignment (RDA) is an approach in which video data is stored by assigning a number of copies of each data block to different, randomly chosen disks. It has been shown that this approach results in smaller response times and lower disk and RAM costs compared to the well-known disk stripping techniques. Based on this storage approach, one has to determine, for each given batch of data blocks, from which disk each of the data blocks is to be retrieved. This is to be done in such a way that the maximum load of the disks is minimized. The problem is called the Retrieval Selection Problem (RSP). In this paper, we propose a new efficient algorithm for RSP. This algorithm is based on the breadth-first search approach and is able to guarantee optimal solutions for RSP in O(n²+mn), where m and n correspond to the number of data blocks and the number of disks, respectively. We will show that our proposed algorithm has a lower time complexity than an existing algorithm, called the MFS algorithm.     

An improved FPTAS for Restricted Shortest Path

Given a graph with a cost and a delay on each edge, Restricted Shortest Path (RSP) aims to find a min-cost s-t path subject to an end-to-end delay constraint. The problem is NP-hard. In this note we present an FPTAS with an improved running time of O(mn/ε) for acyclic graphs, where m and n denote the number of edges and nodes in the graph. Our algorithm uses a scaling and rounding technique similar to that of Hassin [Math. Oper. Res. 17 (1) (1992) 36-42]. The novelty of our algorithm lies in its “adaptivity”. During each iteration of our algorithm the approximation parameters are fine-tuned according to the quality of the current solution so that the running time is kept low while progress is guaranteed at each iteration. Our result improves those of Hassin [Math. Oper. Res. 17 (1) (1992) 36-42], Phillips [Proc. 25th Annual ACM Symposium on the Theory of Computing, 1993, pp. 776-785], and Raz and Lorenz [Technical Report, 1999].     

Improved algorithms for optimal length resolution refutation in difference constraint systems

This paper is concerned with the design and analysis of improved algorithms for determining the optimal length resolution refutation (OLRR) of a system of difference constraints over an integral domain. The problem of finding short explanations for unsatisfiable Difference Constraint Systems (DCS) finds applications in a number of design domains including program verification, proof theory, real-time scheduling, and operations research. These explanations have also been called “certificates” and “refutations” in the literature. This problem was first studied in Subramani (J Autom Reason 43(2):121–137, 2009), wherein the first polynomial time algorithm was proposed. In this paper, we propose two new strongly polynomial algorithms which improve on the existing time bound. Our first algorithm, which we call the edge progression approach, runs in O(n ² · k + m · n · k) time, while our second algorithm, which we call the edge relaxation approach, runs in O(m · n · k) time, where m is the number of constraints in the DCS, n is the number of program variables, and k denotes the length of the shortest refutation. We conducted an extensive empirical analysis of the three OLRR algorithms discussed in this paper. Our experiments indicate that in the case of sparse graphs, the new algorithms discussed in this paper are superior to the algorithm in Subramani (J Autom Reason 43(2):121–137, 2009). Likewise, in the case of dense graphs, the approach in Subramani (J Autom Reason 43(2):121–137, 2009) is superior to the algorithms described in this paper. One surprising observation is the superiority of the edge relaxation algorithm over the edge progression algorithm in all cases, although both algorithms have the same asymptotic time complexity.     

An optimal visibility graph algorithm for triangulated simple polygons

LetP be a triangulated simple polygon withn sides. The visibility graph ofP has an edge between every pair of polygon vertices that can be connected by an open segment in the interior ofP. We describe an algorithm that finds the visibility graph ofP inO(m) time, wherem is the number of edges in the visibility graph. Becausem can be as small asO(n), the algorithm improves on the more general visibility algorithms of Asanoet al. [AAGHI] and Welzl [W], which take Θ(n ²) time, and on Suri'sO(m logn) visibility graph algorithm for simple polygons [S].     

A Dijkstra-like method computing all extreme supported non-dominated solutions of the biobjective shortest path problem

We address the problem of determining all extreme supported solutions of the biobjective shortest path problem. A novel Dijkstra-like method generalizing Dijkstra׳s algorithm to this biobjective case is proposed. The algorithm runs in O(N(m+n log n)) time to solve one-to-one and one-to-all biobjective shortest path problems determining all extreme supported non-dominated points in the outcome space and one supported efficient path associated with each one of them. Here n is the number of nodes, m is the number of arcs and N is the number of extreme supported points in outcome space for the one-to-all biobjective shortest path problem. The memory space required by the algorithm is O(n+m) for the one-to-one problem and O(N+m) for the one-to-all problem. A computational experiment comparing the performance of the proposed methods and state-of-the-art methods is included.     

Parallel comparison of run-length-encoded strings on a linear systolic array

The length of the longest common subsequence (LCS) between two strings of M and N characters can be computed by an O(M × N) dynamic programming algorithm, that can be executed in O(M + N) steps by a linear systolic array. It has been recently shown that the LCS between run-length-encoded (RLE) strings of m and n runs can be computed by an O(nM + Nm − nm) algorithm that could be executed in O(m + n) steps by a parallel hardware. However, the algorithm cannot be directly mapped on a linear systolic array because of its irregular structure.In this paper, we propose a modified algorithm that exhibits a more regular structure at the cost of a marginal reduction of the efficiency of RLE. We outline the algorithm and we discuss its mapping on a linear systolic array.     

Maintaining bridge-connected and biconnected components on-line

We consider the twin problems of maintaining the bridge-connected components and the biconnected components of a dynamic undirected graph. The allowed changes to the graph are vertex and edge insertions. We give an algorithm for each problem. With simple data structures, each algorithm runs inO(n logn +m) time, wheren is the number of vertices andm is the number of operations. We develop a modified version of the dynamic trees of Sleator and Tarjan that is suitable for efficient recursive algorithms, and use it to reduce the running time of the algorithms for both problems toO(mα(m,n)), where α is a functional inverse of Ackermann's function. This time bound is optimal. All of the algorithms useO(n) space.     

Stackelberg Network Pricing Games

We study a multi-player one-round game termed Stackelberg Network Pricing Game, in which a leader can set prices for a subset of m priceable edges in a graph. The other edges have a fixed cost. Based on the leader’s decision one or more followers optimize a polynomial-time solvable combinatorial minimization problem and choose a minimum cost solution satisfying their requirements based on the fixed costs and the leader’s prices. The leader receives as revenue the total amount of prices paid by the followers for priceable edges in their solutions. Our model extends several known pricing problems, including single-minded and unit-demand pricing, as well as Stackelberg pricing for certain follower problems like shortest path or minimum spanning tree. Our first main result is a tight analysis of a single-price algorithm for the single follower game, which provides a (1+ε)log?m-approximation. This can be extended to provide a (1+ε)(log?k+log?m)-approximation for the general problem and k followers. The problem is also shown to be hard to approximate within $\mathcal{O}(\log^{\varepsilon}k + \log^{\varepsilon}m)$ for some ε>0. If followers have demands, the single-price algorithm provides an $\mathcal{O}(m^{2})$ -approximation, and the problem is hard to approximate within $\mathcal{O}(m^{\epsilon})$ for some ε>0. Our second main result is a polynomial time algorithm for revenue maximization in the special case of Stackelberg bipartite vertex-cover, which is based on non-trivial max-flow and LP-duality techniques. This approach can be extended to provide constant-factor approximations for any constant number of followers.     

A remark on the subsequence problem for arc-annotated sequences with pairwise nested arcs

The Arc-Preserving Subsequence (APS) problem appears in the comparison of RNA structures in computational biology. Given two arc-annotated sequences of length n and m<n, APS asks if the shorter sequence can be obtained from the longer one by deleting certain elements along with their incident arcs. It is known that APS with pairwise nested arcs can be solved in O(mn) time. We give an algorithm running in O(m²+n) time in the worst case, actually it is even faster in particular if the shorter sequence has many arcs. The result may serve as a building block for improved APS algorithms in the general case.