Andrzej Lingas

ORCID

Publication Activity (10 Years)

Years Active: 1978-2024
Publications (10 Years): 64

Top Venues

CoRR

Inf. Process. Lett.

Algorithmica

J. Comput. Syst. Sci.

Publications

Leszek Gasieniec, Tomasz Jurdzinski, Ralf Klasing, Christos Levcopoulos, Andrzej Lingas, Jie Min, Tomasz Radzik
Perpetual maintenance of machines with different urgency requirements. J. Comput. Syst. Sci. 139 (2024)
Jesper Jansson, Christos Levcopoulos, Andrzej Lingas
The Voronoi Diagram of Weakly Smooth Planar Point Sets in O(log n) Deterministic Rounds on the Congested Clique. CoRR (2024)
Andrzej Lingas
Boolean Matrix Multiplication for Highly Clustered Data on the Congested Clique. CoRR (2024)
Andrzej Lingas
Rounds of the Congested Clique. CoRR (2024)
Miroslaw Kowaluk, Andrzej Lingas
Rare Siblings Speed-Up Deterministic Detection and Counting of Small Pattern Graphs. Algorithmica 85 (4) (2023)
Jesper Jansson, Christos Levcopoulos, Andrzej Lingas
Convex Hulls and Triangulations of Planar Point Sets on the Congested Clique. CCCG (2023)
Andrzej Lingas
Lower Bounds for Monotone q-Multilinear Boolean Circuits. SOFSEM (2023)
Adrian Dumitrescu, Andrzej Lingas
Finding Small Complete Subgraphs Efficiently. IWOCA (2023)
Andrzej Lingas, Mia Persson
Improved Lower Bounds for Monotone q-Multilinear Boolean Circuits. CoRR (2023)
Andrzej Lingas, Mia Persson
(min, +) Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences. CoRR (2023)
Jesper Jansson, Christos Levcopoulos, Andrzej Lingas
Convex Hulls and Triangulations of Planar Point Sets on the Congested Clique. CoRR (2023)
Jesper Jansson, Christos Levcopoulos, Andrzej Lingas
Online and Approximate Network Construction from Bounded Connectivity Constraints. Int. J. Found. Comput. Sci. 34 (5) (2023)
Artur Czumaj, Andrzej Lingas
On parallel time in population protocols. Inf. Process. Lett. 179 (2023)
Adrian Dumitrescu, Andrzej Lingas
Finding Small Complete Subgraphs Efficiently. CoRR (2023)
Andrzej Lingas, Mia Persson
$(\min ,+)$ Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences. COCOON (2) (2023)
Leszek Gasieniec, Ralf Klasing, Christos Levcopoulos, Andrzej Lingas, Jie Min, Tomasz Radzik
Perpetual maintenance of machines with different urgency requirements. CoRR (2022)
Stasys Jukna, Andrzej Lingas
Lower bounds for Boolean circuits of bounded negation width. J. Comput. Syst. Sci. 129 (2022)
Andrzej Lingas
A Note on Lower Bounds for Monotone Multilinear Boolean Circuits. Electron. Colloquium Comput. Complex. (2022)
Andrzej Lingas, Mia Persson, Dzmitry Sledneu
An Output-Sensitive Algorithm for All-Pairs Shortest Paths in Directed Acyclic Graphs. CALDAM (2022)
Miroslaw Kowaluk, Andrzej Lingas
A Multi-Dimensional Matrix Product - A Natural Tool for Parameterized Graph Algorithms. Algorithms 15 (12) (2022)
Leszek Gasieniec, Jesper Jansson, Christos Levcopoulos, Andrzej Lingas
Efficient Assignment of Identities in Anonymous Populations. OPODIS (2021)
Miroslaw Kowaluk, Andrzej Lingas
Breaking the hegemony of the triangle method in clique detection. CoRR (2021)
Jesper Jansson, Christos Levcopoulos, Andrzej Lingas
Online and Approximate Network Construction from Bounded Connectivity Constraints. CIAC (2021)
Leszek Gasieniec, Jesper Jansson, Christos Levcopoulos, Andrzej Lingas
Efficient Assignment of Identities in Anonymous Populations. CoRR (2021)
Miroslaw Kowaluk, Andrzej Lingas
Quantum and Approximation Algorithms for Maximum Witnesses of Boolean Matrix Products. CALDAM (2021)
Andrzej Lingas, Mia Persson, Dzmitry Sledneu
An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs. CoRR (2021)
Artur Czumaj, Andrzej Lingas
On Truly Parallel Time in Population Protocols. CoRR (2021)
Leszek Gasieniec, Jesper Jansson, Christos Levcopoulos, Andrzej Lingas, Mia Persson
Pushing the Online Boolean Matrix-vector Multiplication conjecture off-line and identifying its easy cases. J. Comput. Syst. Sci. 118 (2021)
Andrzej Lingas
Consequences of APSP, triangle detection, and 3SUM hardness for separation between determinism and non-determinism. LAGOS (2021)
Miroslaw Kowaluk, Andrzej Lingas
A simple approach to nondecreasing paths. Inf. Process. Lett. 162 (2020)
Andrzej Lingas
Solving Hard Problems by Protein Folding? TPNC (2020)
Miroslaw Kowaluk, Andrzej Lingas
Quantum and approximation algorithms for maximum witnesses of Boolean matrix products. CoRR (2020)
Andrzej Lingas
Consequences of APSP, triangle detection, and 3SUM hardness for separation between determinism and non-determinism. CoRR (2020)
Andrzej Lingas
Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth. Theor. Comput. Sci. 820 (2020)
Andrzej Lingas, Mia Persson
) Mechanical Operations. Int. J. Unconv. Comput. 15 (3) (2020)
Andrzej Lingas, Mia Persson
Computing the Boolean product of two n\times n Boolean matrices using O(n^2) mechanical operation. CoRR (2020)
Andrzej Lingas, Mateusz Miotk, Jerzy Topp, Pawel Zylinski
Graphs with equal domination and covering numbers. J. Comb. Optim. 39 (1) (2020)
Leszek Gasieniec, Jesper Jansson, Christos Levcopoulos, Andrzej Lingas, Mia Persson
Pushing the Online Matrix-Vector Conjecture Off-Line and Identifying Its Easy Cases. FAW (2019)
Stasys Jukna, Andrzej Lingas
Lower Bounds for DeMorgan Circuits of Bounded Negation Width. STACS (2019)
Dariusz Dereniowski, Andrzej Lingas, Dorota Osula, Mia Persson, Pawel Zylinski
Clearing directed subgraphs by mobile agents: Variations on covering with paths. J. Comput. Syst. Sci. 102 (2019)
Rolf Klein, Elmar Langetepe, Barbara Schwarzwald, Christos Levcopoulos, Andrzej Lingas
On a Fire Fighter's Problem. Int. J. Found. Comput. Sci. 30 (2) (2019)
Miroslaw Kowaluk, Andrzej Lingas
A fast deterministic detection of small pattern graphs in graphs without large cliques. Theor. Comput. Sci. 770 (2019)
Katharina Dannenberg, Jesper Jansson, Andrzej Lingas, Eva-Marta Lundell
The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets. Discret. Appl. Math. 257 (2019)
Miroslaw Kowaluk, Andrzej Lingas
Rare Siblings Speed-Up Deterministic Detection and Counting of Small Pattern Graphs. FCT (2019)
Andrzej Lingas
Small Normalized Boolean Circuits for Semi-disjoint Bilinear Forms Require Logarithmic Conjunction-depth. Electron. Colloquium Comput. Complex. 25 (2018)
Cecilia Bohler, Rolf Klein, Andrzej Lingas, Chih-Hung Liu
Forest-like abstract Voronoi diagrams in linear time. Comput. Geom. 68 (2018)
Rolf Klein, Christos Levcopoulos, Andrzej Lingas
Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems. Algorithms 11 (4) (2018)
Miroslaw Kowaluk, Andrzej Lingas
Are unique subgraphs not easier to find? Inf. Process. Lett. 134 (2018)
Peter Floderus, Jesper Jansson, Christos Levcopoulos, Andrzej Lingas, Dzmitry Sledneu
3D Rectangulations and Geometric Matrix Multiplication. Algorithmica 80 (1) (2018)
Jesper Jansson, Andrzej Lingas, Ramesh Rajaby, Wing-Kin Sung
Determining the Consistency of Resolved Triplets and Fan Triplets. J. Comput. Biol. 25 (7) (2018)
Andrzej Lingas, Mia Persson
Extreme Witnesses and Their Applications. Algorithmica 80 (12) (2018)
Andrzej Lingas
Small Normalized Boolean Circuits for Semi-disjoint Bilinear Forms Require Logarithmic Conjunction-depth. Computational Complexity Conference (2018)
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
A QPTAS for the base of the number of crossing-free structures on a planar point set. Theor. Comput. Sci. 711 (2018)
Anna Adamaszek, Artur Czumaj, Andrzej Lingas, Jakub Onufry Wojtaszczyk
Approximation Schemes for Capacitated Geometric Network Design. SIAM J. Discret. Math. 32 (4) (2018)
Stasys Jukna, Andrzej Lingas
Lower Bounds for Circuits of Bounded Negation Width. Electron. Colloquium Comput. Complex. 25 (2018)
Jesper Jansson, Andrzej Lingas, Ramesh Rajaby, Wing-Kin Sung
Determining the Consistency of Resolved Triplets and Fan Triplets. RECOMB (2017)
Andrzej Lingas, Mia Persson, Dzmitry Sledneu
Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model. TAMC (2017)
Leszek Gasieniec, Ralf Klasing, Christos Levcopoulos, Andrzej Lingas, Jie Min, Tomasz Radzik
Bamboo Garden Trimming Problem (Perpetual Maintenance of Machines with Different Attendance Urgency Factors). SOFSEM (2017)
Dariusz Dereniowski, Andrzej Lingas, Mia Persson, Dorota Urbanska, Pawel Zylinski
The Snow Team Problem - (Clearing Directed Subgraphs by Mobile Agents). FCT (2017)
Andrzej Lingas
Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the Boolean Convolution. TAMC (2017)
Dariusz Dereniowski, Andrzej Lingas, Dorota Osula, Mia Persson, Pawel Zylinski
The Snow Team Problem (Clearing Directed Subgraphs by Mobile Agents). CoRR (2017)
Leszek Gasieniec, Christos Levcopoulos, Andrzej Lingas, Rasmus Pagh, Takeshi Tokuyama
Efficiently Correcting Matrix Products. Algorithmica 79 (2) (2017)
Miroslaw Kowaluk, Andrzej Lingas
A Fast Deterministic Detection of Small Pattern Graphs in Graphs Without Large Cliques. WALCOM (2017)
Leszek Gasieniec, Christos Levcopoulos, Andrzej Lingas, Rasmus Pagh, Takeshi Tokuyama
Efficiently Correcting Matrix Products. CoRR (2016)
Andrzej Lingas, Mia Persson
A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows. Algorithmica 72 (2) (2015)
Peter Floderus, Miroslaw Kowaluk, Andrzej Lingas, Eva-Marta Lundell
Detecting and Counting Small Pattern Graphs. SIAM J. Discret. Math. 29 (3) (2015)
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set. ICALP (1) (2015)
Jesper Jansson, Andrzej Lingas, Eva-Marta Lundell
The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets. CPM (2015)
Peter Floderus, Miroslaw Kowaluk, Andrzej Lingas, Eva-Marta Lundell
Induced subgraph isomorphism: Are some patterns substantially easier than others? Theor. Comput. Sci. 605 (2015)
Andrzej Lingas, Mia Persson
Extreme Witnesses and Their Applications. COCOA (2015)
Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu
Detecting monomials with k distinct variables. Inf. Process. Lett. 115 (2) (2015)
Andrzej Lingas, Mia Persson, Dzmitry Sledneu
Iterative merging heuristics for correlation clustering. Int. J. Metaheuristics 3 (2) (2014)
Rolf Klein, Christos Levcopoulos, Andrzej Lingas
Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems. LATIN (2014)
Niklas Zechner, Andrzej Lingas
Efficient Algorithms for Subgraph Listing. Algorithms 7 (2) (2014)
Andrzej Lingas
Vector convolution in O(n) steps and matrix multiplication in O(n^2) steps : -). Electron. Colloquium Comput. Complex. 21 (2014)
Peter Floderus, Jesper Jansson, Christos Levcopoulos, Andrzej Lingas, Dzmitry Sledneu
3D Rectangulations and Geometric Matrix Multiplication. ISAAC (2014)
Leszek Gasieniec, Christos Levcopoulos, Andrzej Lingas
Efficiently Correcting Matrix Products. ISAAC (2014)
Jesper Jansson, Andrzej Lingas
Computing the rooted triplet distance between galled trees by counting triangles. J. Discrete Algorithms 25 (2014)
Christos Levcopoulos, Andrzej Lingas, Bengt J. Nilsson, Pawel Zylinski
Clearing Connections by Few Agents. FUN (2014)
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
A QPTAS for the Base of the Number of Triangulations of a Planar Point Set. CoRR (2014)
Andrzej Lingas, Leonidas Palios, Agnieszka Wasylewicz, Pawel Zylinski
Corrigendum to "Note on covering monotone orthogonal polygons" [Inf. Process. Lett. 104(6) (2007) 220-227]. Inf. Process. Lett. 114 (11) (2014)
Christos Levcopoulos, Andrzej Lingas
A note on a QPTAS for maximum weight triangulation of planar point sets. Inf. Process. Lett. 114 (8) (2014)
Peter Floderus, Miroslaw Kowaluk, Andrzej Lingas, Eva-Marta Lundell
Detecting and Counting Small Pattern Graphs. ISAAC (2013)
Miroslaw Kowaluk, Andrzej Lingas, Eva-Marta Lundell
Unique subgraphs are not easier to find. Int. J. Comput. Math. 90 (6) (2013)
Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu
Detecting Monomials with k Distinct Variables. Electron. Colloquium Comput. Complex. 20 (2013)
Peter Floderus, Andrzej Lingas, Mia Persson
Towards More Efficient Infection and Fire Fighting. Int. J. Found. Comput. Sci. 24 (1) (2013)
Frantisek Galcík, Leszek Gasieniec, Andrzej Lingas
Efficient broadcasting in radio networks with long-range interference. Distributed Comput. 26 (1) (2013)
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
Optimal cuts and partitions in tree metrics in polynomial time. Inf. Process. Lett. 113 (12) (2013)
Andrzej Lingas, Mia Persson
Simple Iterative Heuristics for Correlation Clustering. LSSC (2013)
Miroslaw Kowaluk, Andrzej Lingas, Eva-Marta Lundell
Counting and Detecting Small Subgraphs via Equations. SIAM J. Discret. Math. 27 (2) (2013)
Andrzej Lingas, Mia Persson
A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows. Euro-Par (2012)
Andrzej Lingas, Mia Persson
A fast parallel algorithm for minimum-cost small integral flows CoRR (2012)
Jesper Jansson, Richard S. Lemence, Andrzej Lingas
The Complexity of Inferring a Minimally Resolved Phylogenetic Supertree. SIAM J. Comput. 41 (1) (2012)
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
Optimal Cuts and Partitions in Tree Metrics in Polynomial Time CoRR (2012)
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
Optimal Cuts and Bisections on the Real Line in Polynomial Time CoRR (2012)
Andrzej Lingas, Dzmitry Sledneu
A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs. SOFSEM (2012)
Andrzej Lingas, Agnieszka Wasylewicz, Pawel Zylinski
Linear-Time 3-Approximation Algorithm for the R-Star Covering Problem. Int. J. Comput. Geom. Appl. 22 (2) (2012)
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
Optimal Cuts and Partitions in Tree Metrics in Polynomial Time. Electron. Colloquium Comput. Complex. 19 (2012)
Peter Floderus, Miroslaw Kowaluk, Andrzej Lingas, Eva-Marta Lundell
Induced Subgraph Isomorphism: Are Some Patterns Substantially Easier Than Others? COCOON (2012)
Piotr Berman, Marek Karpinski, Andrzej Lingas
Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems. Algorithmica 64 (2) (2012)

Andrzej Lingas.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Andrzej Lingas