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 induced subgraph isomorphism problem and the general subgraph isomorphism problem for small pattern graphs. We present a new general method for detecting induced subgraphs of a host graph isomorphic to a fixed pattern graph by reduction to polynomial testing for nonidentity with zero over a field of finite characteristic. It yields new upper time bounds for several pattern graphs on five vertices and provides an alternative combinatorial method for the majority of pattern graphs on four and three vertices. Since our method avoids the large overhead of fast matrix multiplication, it can be of practical interest even for larger pattern graphs. Next, we derive new upper time bounds on counting the number of isomorphisms between a fixed pattern graph with an independent set of size $s$ and a subgraph of the host graph. We also consider a weighted version of the counting problem, when one counts the number of isomorphisms between the pattern graph and lightest subgraphs, providing a slightly slower combinatorial algorithm.

We present a general technique for detecting and counting small subgraphs. It consists of forming special linear combinations of the numbers of occurrences of different induced subgraphs of fixed size in a graph. These combinations can be efficiently computed by rectangular matrix multiplication. Our two main results utilizing the technique are as follows. Let $H$ be a fixed graph with $k$ vertices and an independent set of size $s.$ 1. Detecting if an $n$-vertex graph contains a (not necessarily induced) subgraph isomorphic to $H$ can be done in time $O(n^{\omega(\lceil (k-s)/2 \rceil, 1, \lfloor (k-s)/2 \rfloor )})$, where $\omega (p,q,r)$ is the exponent of fast arithmetic matrix multiplication of an $n^p\times n^q$ matrix by an $n^q\times n^r$ matrix. 2. When $s=2,$ counting the number of (not necessarily induced) subgraphs isomorphic to $H$ can be done in the same time, i.e., in time $O(n^{\omega(\lceil (k-2)/2 \rceil, 1, \lfloor (k-2)/2 \rfloor )}).$ It follows in particular that we can count the number of subgraphs isomorphic to any $H$ on four vertices that is not $K_4$ in time $O(n^{\omega})$, where $\omega =\omega (1,1,1)$ is known to be smaller than 2.373. Similarly, we can count the number of subgraphs isomorphic to any $H$ on five vertices that is not $K_5$ in time $O(n^{\omega(2,1,1)}),$ where $\omega(2,1,1)$ is known to be smaller than 3.257. Finally, we derive input-sensitive variants of our time upper bounds. They are partially expressed in terms of the number $m$ of edges of the input graph and do not rely on fast matrix multiplication.

We present a general technique for detecting and counting small subgraphs.It consists in forming special linear combinations of the numbers of occurrences of different induced subgraphs of fixed size in a graph.The combinations can be efficiently computed by rectangular matrix multiplication.Our two main results utilizing the technique are as follows.Let H be a fixed graph with k vertices and an independent set of size s.1. Detecting if an n-vertex graph contains a (nonnecessarily induced) subgraph isomorphic to H can be done in timewhere ω(p, q, r) is the exponent of fast arithmetic matrix multiplication of an n p × n q matrix by an n q × n r matrix.2. When s = 2, counting the number of (nonnecessarily induced) subgraphs isomorphic to H can be done in the same time, i.e., in time O(n k-2 + n ω( (k-2)/2 ,1, (k-2)/2 ) ). (This improves for s = 2 on a counting algorithm of Vassilevska and Williams, running in time O(n k-s+3 ).)It follows in particular that we can count the number of subgraphs isomorphic to any H on four vertices that is not K 4 in time O(n ω ), where ω = ω(1, 1, 1) is known to be smaller than 2.376.Similarly, we can count the number of subgraphs isomorphic to any H on five vertices that is not K 5 in time O(n ω(2,1,1) ), where ω(2, 1, 1) is known to be smaller than 3.334.

We present a new algorithm for the two-center problem: “Given a set S of n points in the real plane, find two closed discs whose union contains all of the points and the radius of the larger disc is minimized.” An almost quadratic O(n2logn) solution is given. The previously best known algorithms for the two-center problem have time complexity O(n2log3n). The solution is based on a new geometric characterization of the optimal discs and on a searching scheme with so-called lazy evaluation. The algorithm is simple and does not assume general position of the input points. The importance of the problem is known in various practical applications including transportation, station placement, and facility location.

A new geometrical transform, skewed-projection, is introduced. This transform is applied to design a new algorithm for a common transversal problem for families of polyhedra in R3. The time and space analysis, using Davenport-Schinzel sequences, is given.

Two new algorithms finding relative neighborhood graph RNG(V) for a set V of n points are presented. The first algorithm solves this problem for input points in (R2,Lp) metric space in time O(n a(n,n)) if the Delaunay triangulation DT(V) is given. This time performance is achieved due to attractive and natural application of FIND-UNION data structure to represent so-called elimination forest of edges in DT(V). The second algorithm solves the relative neighborhood graph problem in (Rd,Lp), 1