3 papers
cs.DS2021
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…
cs.DS2020
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…
cs.DC2012
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…