A. Lingas

activity

20092024

most citedExact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems with Applications

4 citations · 10 across the 24 of their papers we have counts for

collaborators

Showing cs.DSShow all

13 papers · 1 filter

cs.DS2023

$(min, +)$ Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences

Andrzej Lingas, Mia Persson

We study the time complexity of computing the $(min, +)$ matrix product of two $n \times n$ integer matrices in terms of $n$ and the number of monotone subsequences the rows of the…

cs.DS2023

Finding Small Complete Subgraphs Efficiently

Ke Chen, Adrian Dumitrescu, Andrzej Lingas

(I) We revisit the algorithmic problem of finding all triangles in a graph $G = (V, E)$ with $n$ vertices and $m$ edges. According to a result of Chiba and Nishizeki (1985), this task…

cs.DS2022

Perpetual maintenance of machines with different urgency requirements

Leszek Gąsieniec, Tomasz Jurdziński, Ralf Klasing +4

A garden $G$ is populated by $n \geq 1$ bamboos $b_{1}, b_{2}, ..., b_{n}$ with the respective daily growth rates $h_{1} \geq h_{2} \geq \dots \geq h_{n}$ . It is assumed that the initial heights of…

cs.DS2021

Breaking the hegemony of the triangle method in clique detection

Mirosław Kowaluk, Andrzej Lingas

We consider the fundamental problem of detecting/counting copies of a fixed pattern graph in a host graph. The recent progress on this problem has not included complete pattern gra…

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