9 papers
Fast approximate -center clustering in high dimensional spaces
Mirosław Kowaluk, Andrzej Lingas, Mia Persson
We study the design of efficient approximation algorithms for the -center clustering and minimum-diameter -clustering problems in high dimensional Euclidean and Hamming…
Approximate all-pairs Hamming distances and 0-1 matrix multiplication
Miroslaw Kowaluk, Andrzej Lingas, Mia Persson
Arslan showed that computing all-pairs Hamming distances is easily reducible to arithmetic 0-1 matrix multiplication (IPL 2018). We provide a reverse, linear-time reduction of arit…
Multiplication of 0-1 matrices via clustering
Jesper Jansson, Miroslaw Kowaluk, Andrzej Lingas +1
We study applications of clustering (in particular, the -center clustering problem) in the design of efficient and practical algorithms for computing an approximate and the exac…
Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences
Andrzej Lingas, Mia Persson
We study the time complexity of computing the matrix product of two integer matrices in terms of and the number of monotone subsequences the rows of the…
Improved Lower Bounds for Monotone q-Multilinear Boolean Circuits
Andrzej Lingas, Mia Persson
A monotone Boolean circuit is composed of OR gates, AND gates and input gates corresponding to the input variables and the Boolean constants. It is -multilinear if for each its…
An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs
Andrzej Lingas, Mia Persson, Dzmitry Sledneu
A straightforward dynamic programming method for the single-source shortest paths problem (SSSP) in an edge-weighted directed acyclic graph (DAG) processes the vertices in a topolo…
Computing the Boolean product of two n\times n Boolean matrices using O(n^2) mechanical operation
Andrzej Lingas, Mia Persson
We study the problem of determining the Boolean product of two n\times n Boolean matrices in an unconventional computational model allowing for mechanical operations. We show that…
The Snow Team Problem (Clearing Directed Subgraphs by Mobile Agents)
Dariusz Dereniowski, Andrzej Lingas, Dorota Osula +2
We study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initia…
A fast parallel algorithm for minimum-cost small integral flows
Andrzej Lingas, Mia Persson
We present a new approach to the minimum-cost integral flow problem for small values of the flow. It reduces the problem to the tests of simple multi-variate polynomials over a fin…