First, we present a new algorithm for the single-source shortest paths problem (SSSP) in edge-weighted directed graphs, with n vertices, m edges, and both positive and negative real edge weights. For a positive integer parameter t , in O ( tm ) time the algorithm finds for each vertex v a path distance from the source to v not exceeding that given by the shortest path from the source to v among the so called t + light paths . A directed path between two vertices is t + light if it contains at most t more edges than the minimum edge-cardinality directed path between these vertices. For t = O ( n ) , our algorithm yields an O ( nm )-time solution to SSSP in directed graphs with real edge weights matching the time complexity of the Bellman-Ford algorithm. Our next contribution is a new algorithm for the all-pairs shortest paths problem (APSP) in directed acyclic graphs (DAGs) with positive and negative real edge weights. The running time of the algorithm depends on such parameters as the number of leaves in (lexicographically first) shortest-paths trees, and the in-degrees in the input DAG. If the number of leaves is sufficiently small on the average, the algorithm is substantially faster than the best known algorithm in case of non-sparse DAGs. We also discuss an extension of hypothetical improved upper time-bounds for APSP in non-negatively edge-weighted DAGs to include directed graphs with a polynomial number of large directed cycles.

Abstract We study applications of clustering (in particular, the Hamming k -center clustering problem) in the design of efficient and practical algorithms for computing an approximate and the exact arithmetic matrix product of two 0-1 rectangular matrices with clustered rows or columns, respectively. Our results in part can be regarded as an extension of the clustering-based approach to Boolean square matrix multiplication due to Arslan and Chidri (CSC 2011). We provide a simple and efficient deterministic algorithm for approximate matrix product of 0-1 matrices, where the additive error is proportional to the minimum maximum radius in an $${\ell }$$ ℓ -center clustering of the rows of the first matrix or an k -center clustering of the columns of the second matrix. We use the approximation algorithm as a preprocessing after which a query asking for the exact value of an arbitrary entry in the product matrix can be answered in time proportional to the additive error. As a consequence, we obtain a simple deterministic algorithm for the exact matrix product of 0-1 matrices. We also present an alternative simple deterministic algorithm for the exact product and in addition, faster analogous randomized algorithms for an approximate and the exact matrix products of 0-1 matrices based on randomized $${\ell }$$ ℓ - and k -center clustering.

We study the time complexity of computing the ( min ⁡ , + ) matrix product of two n × n integer matrices in terms of n and the number of monotone subsequences the rows of the first matrix and the columns of the second matrix can be decomposed into. In particular, we show that if each row of the first matrix can be decomposed into at most m 1 monotone subsequences and each column of the second matrix can be decomposed into at most m 2 monotone subsequences such that all the subsequences are non-decreasing or all of them are non-increasing then the ( min ⁡ , + ) product of the matrices can be computed in O ( m 1 m 2 n 2.569 ) time. On the other hand, we observe that if all the rows of the first matrix are non-decreasing and all columns of the second matrix are non-increasing or vice versa then this case is as hard as the general one. We also present six cases of the restrictions on the input integer matrices under which the problem of computing the ( min ⁡ , + ) matrix product is equally hard as that of computing the minimum and maximum witnesses of Boolean matrix product. Similarly, we also study the time complexity of computing the ( min ⁡ , + ) convolution of two n -dimensional integer vectors in terms of n and the number of monotone subsequences the two vectors can be decomposed into. We show that if the first vector can be decomposed into at most m 1 monotone subsequences and the second vector can be decomposed into at most m 2 subsequences such that all the subsequences of the first vector are non-decreasing and all the subsequences of the second vector are non-increasing or vice versa then their ( min ⁡ , + ) convolution can be computed in O ˜ ( m 1 m 2 n 1.5 ) time. On the other, the case when both vectors are non-decreasing or both of them are non-increasing is as hard as the general case. Finally, we present six cases of the restrictions on the input integer vectors under which the problem of computing the ( min ⁡ , + ) vector convolution is equally hard as that of computing the minimum and maximum witnesses of the Boolean vector convolution.

We study the problem of computing the so called minimum and maximum witnesses for Boolean vector convolution. We also consider a generalization of the problem which is to determine for each positive value at a coordinate of the convolution vector, q smallest (largest) witnesses, where q is the minimum of a parameter k and the number of witnesses for this coordinate. We term this problem the smallest k-witness problem or the largest k-witness problem, respectively. We also study the corresponding smallest and largest k-witness problems for Boolean matrix product. First, we present an $$\tilde{O}(n^{1.5}k^{0.5})$$ -time algorithm for the smallest or largest k-witness problem for the Boolean convolution of two n-dimensional vectors, where the notation $$\tilde{O}(\ )$$ suppresses polylogarithmic in n factors. In consequence, we obtain new upper time bounds on reporting positions of mismatches in potential string alignments and on computing restricted cases of the $$(\min , +)$$ vector convolution. Next, we present a fast (substantially subcubic in n and linear in k) algorithm for the smallest or largest k-witness problem for the Boolean matrix product of two $$n\times n$$ Boolean matrices. It yields fast algorithms for reporting k lightest (heaviest) triangles in a vertex-weighted graph.