Andrzej Lingas
Orcid: 0000-0003-4998-9844Affiliations:
- Lund University, Sweden
According to our database1,
Andrzej Lingas
authored at least 225 papers
between 1978 and 2025.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis Dataset OtherLinks
Online presence:
-
on zbmath.org
-
on orcid.org
-
on cs.lth.se
On csauthors.net:
Bibliography
2025
2024
J. Comput. Syst. Sci., February, 2024
A Note on Solving Problems of Substantially Super-linear Complexity in N<sup>o(1)</sup> Rounds of the Congested Clique.
CoRR, 2024
The Voronoi Diagram of Weakly Smooth Planar Point Sets in O(log n) Deterministic Rounds on the Congested Clique.
CoRR, 2024
Proceedings of the Euro-Par 2024: Parallel Processing, 2024
2023
Int. J. Found. Comput. Sci., August, 2023
Algorithmica, April, 2023
Proceedings of the SOFSEM 2023: Theory and Practice of Computer Science, 2023
Proceedings of the Combinatorial Algorithms - 34th International Workshop, 2023
$(\min ,+)$ Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences.
Proceedings of the Computing and Combinatorics - 29th International Conference, 2023
Convex Hulls and Triangulations of Planar Point Sets on the Congested Clique.
Proceedings of the 35th Canadian Conference on Computational Geometry, 2023
2022
J. Comput. Syst. Sci., 2022
Electron. Colloquium Comput. Complex., 2022
A Multi-Dimensional Matrix Product - A Natural Tool for Parameterized Graph Algorithms.
Algorithms, 2022
An Output-Sensitive Algorithm for All-Pairs Shortest Paths in Directed Acyclic Graphs.
Proceedings of the Algorithms and Discrete Applied Mathematics, 2022
2021
Pushing the Online Boolean Matrix-vector Multiplication conjecture off-line and identifying its easy cases.
J. Comput. Syst. Sci., 2021
Consequences of APSP, triangle detection, and 3SUM hardness for separation between determinism and non-determinism.
Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium, 2021
Quantum and Approximation Algorithms for Maximum Witnesses of Boolean Matrix Products.
Proceedings of the Algorithms and Discrete Applied Mathematics, 2021
2020
Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth.
Theor. Comput. Sci., 2020
Computing the Boolean Product of Two <i>n</i> × <i>n</i> Boolean Matrices Using <i>O</i>(<i>n</i><sup>2</sup>) Mechanical Operations.
Int. J. Unconv. Comput., 2020
Computing the Boolean product of two n\times n Boolean matrices using O(n^2) mechanical operation.
CoRR, 2020
Proceedings of the Theory and Practice of Natural Computing - 9th International Conference, 2020
2019
A fast deterministic detection of small pattern graphs in graphs without large cliques.
Theor. Comput. Sci., 2019
J. Comput. Syst. Sci., 2019
The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets.
Discret. Appl. Math., 2019
Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019
Proceedings of the Frontiers in Algorithmics - 13th International Workshop, 2019
2018
A QPTAS for the base of the number of crossing-free structures on a planar point set.
Theor. Comput. Sci., 2018
SIAM J. Discret. Math., 2018
J. Comput. Biol., 2018
Small Normalized Boolean Circuits for Semi-disjoint Bilinear Forms Require Logarithmic Conjunction-depth.
Electron. Colloquium Comput. Complex., 2018
Electron. Colloquium Comput. Complex., 2018
Algorithms, 2018
Approximation Schemes for Minimum-Cost k-Connectivity Problems in Geometric Graphs.
Proceedings of the Handbook of Approximation Algorithms and Metaheuristics, 2018
2017
Proceedings of the Theory and Applications of Models of Computation, 2017
Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the Boolean Convolution.
Proceedings of the Theory and Applications of Models of Computation, 2017
Bamboo Garden Trimming Problem (Perpetual Maintenance of Machines with Different Attendance Urgency Factors).
Proceedings of the SOFSEM 2017: Theory and Practice of Computer Science, 2017
Proceedings of the Fundamentals of Computation Theory - 21st International Symposium, 2017
2016
2015
Theor. Comput. Sci., 2015
The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets.
Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015
2014
J. Discrete Algorithms, 2014
Corrigendum to "Note on covering monotone orthogonal polygons" [Inf. Process. Lett. 104(6) (2007) 220-227].
Inf. Process. Lett., 2014
Inf. Process. Lett., 2014
Int. J. Metaheuristics, 2014
Electron. Colloquium Comput. Complex., 2014
CoRR, 2014
Proceedings of the Algorithms and Computation - 25th International Symposium, 2014
Proceedings of the Fun with Algorithms - 7th International Conference, 2014
2013
Inf. Process. Lett., 2013
Int. J. Found. Comput. Sci., 2013
Distributed Comput., 2013
Proceedings of the Large-Scale Scientific Computing - 9th International Conference, 2013
2012
SIAM J. Comput., 2012
Int. J. Comput. Geom. Appl., 2012
Algorithmica, 2012
A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs.
Proceedings of the SOFSEM 2012: Theory and Practice of Computer Science, 2012
2011
Int. J. Found. Comput. Sci., 2011
Algorithmica, 2011
Proceedings of the Theory and Applications of Models of Computation, 2011
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011
Proceedings of the Language and Automata Theory and Applications, 2011
2010
Int. J. Found. Comput. Sci., 2010
Proceedings of the SOFSEM 2010: Theory and Practice of Computer Science, 2010
2009
Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication.
SIAM J. Comput., 2009
Inf. Process. Lett., 2009
Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems with Applications
CoRR, 2009
Efficient broadcasting in known topology radio networks with long-range interference.
Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, 2009
PTAS for <i>k</i>-Tour Cover Problem on the Plane for Moderately Large Values of <i>k</i>.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009
2008
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008
Proceedings of the Distributed Computing, 22nd International Symposium, 2008
Proceedings of the WALCOM: Algorithms and Computation, Second International Workshop, 2008
2007
Proceedings of the Handbook of Approximation Algorithms and Metaheuristics., 2007
Theor. Comput. Sci., 2007
Theor. Comput. Sci., 2007
Inf. Process. Lett., 2007
Int. J. Found. Comput. Sci., 2007
Int. J. Comput. Geom. Appl., 2007
Algorithmica, 2007
Proceedings of the Theory and Applications of Models of Computation, 2007
Proceedings of the Algorithms, 2007
Proceedings of the Algorithmic Aspects in Information and Management, 2007
2006
Electron. Colloquium Comput. Complex., 2006
A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation.
Comput. Geom., 2006
Minimum-Energy Broadcasting in Wireless Networks in the <i>d</i>-Dimensional Euclidean Space (The <i>alpha</i><=<i>d</i> Case).
Proceedings of the Combinatorial and Algorithmic Aspects of Networking, Third Workshop, 2006
2005
Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs.
SIAM J. Comput., 2005
Inf. Process. Lett., 2005
Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth.
Inf. Process. Lett., 2005
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005
Proceedings of the Theory of Computing 2005, 2005
2004
J. Discrete Algorithms, 2004
Fundam. Informaticae, 2004
On approximation of the maximum clique minor containment problem and some subgraph homeomorphism problems
Electron. Colloquium Comput. Complex., 2004
Comput. Geom., 2004
Proceedings of the Algorithm Theory, 2004
2003
Parallel Process. Lett., 2003
Fundam. Informaticae, 2003
Proceedings of the Algorithms and Data Structures, 8th International Workshop, 2003
Improved Approximation Algorithms for Optimization Problems in Graphs with Superlogarithmic Treewidth.
Proceedings of the Algorithms and Computation, 14th International Symposium, 2003
Subexponential-Time Algorithms for Maximum Independent Set and Related Problems on Box Graphs.
Proceedings of the Computing and Combinatorics, 9th Annual International Conference, 2003
2002
Inf. Process. Lett., 2002
Adaptive Algorithms for Constructing Convex Hulls and Triangulations of Polygonal Chains.
Proceedings of the Algorithm Theory, 2002
Proceedings of the Algorithms and Computation, 13th International Symposium, 2002
Polynomial-Time Approximation Schemes for the Euclidean Survivable Network Design Problem.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002
2001
Theor. Comput. Sci., 2001
Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001
Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing, 2001
Proceedings of the 5th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M 2001), 2001
2000
Theor. Comput. Sci., 2000
Electron. Colloquium Comput. Complex., 2000
Approximation Algorithms for MAX-BISECTION on Low Degree Reg ular Graphs and Planar Graphs
Electron. Colloquium Comput. Complex., 2000
Algorithmica, 2000
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000
1999
J. Parallel Distributed Comput., 1999
Balanced Randomized Tree Splitting with Applications to Evolutionary Tree Constructions.
Proceedings of the STACS 99, 1999
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999
Proceedings of the Automata, 1999
1998
Theory Comput. Syst., 1998
J. Parallel Distributed Comput., 1998
Inf. Process. Lett., 1998
Proceedings of the STACS 98, 1998
Ultrafast Randomized Parallel Construction and Approximation Algorithms for Spanning Forests in Dense Graphs.
Proceedings of the Parallel and Distributed Processing, 10 IPPS/SPDP'98 Workshops Held in Conjunction with the 12th International Parallel Processing Symposium and 9th Symposium on Parallel and Distributed Processing, Orlando, Florida, USA, March 30, 1998
Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998
Subexponential-time algorithms for minimum weight triangulations and related problems.
Proceedings of the 10th Canadian Conference on Computational Geometry, 1998
Inferring Ordered Trees from Local Constraints.
Proceedings of Computing: The Fourth Australasian Theory Symposium (CATS'98), 1998
1997
Theor. Comput. Sci., 1997
Parallel Process. Lett., 1997
Proceedings of the Computing and Combinatorics, Third Annual International Conference, 1997
1996
Guest Editor's Foreword.
Nord. J. Comput., 1996
A Simple NC-Algorithm for a Maximal Independent set in a Hypergraph of Poly-Log Arboricity.
Inf. Process. Lett., 1996
Inf. Process. Lett., 1996
A Linear-Time Randomized Algorithm for the Bounded Voronoi Diagram of a Simple Polygon.
Int. J. Comput. Geom. Appl., 1996
Proceedings of the Mathematical Foundations of Computer Science 1996, 1996
1995
Int. J. Comput. Geom. Appl., 1995
Algorithmica, 1995
Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1995
1994
Editor's Foreword.
Nord. J. Comput., 1994
A Linear-time Construction of the Relative Neighborhood Graph From the Delaunay Triangulation.
Comput. Geom., 1994
Proceedings of the Mathematical Foundations of Computer Science 1994, 1994
Proceedings of the Algorithms and Computation, 5th International Symposium, 1994
1993
Int. J. Found. Comput. Sci., 1993
Proceedings of the Algorithms and Computation, 4th International Symposium, 1993
Proceedings of the Seventh International Parallel Processing Symposium, 1993
A Note on Generalizations of Chew's Algorithm for the Voronoi Diagram of a Convex Polygon.
Proceedings of the 5th Canadian Conference on Computational Geometry, 1993
1992
Discret. Comput. Geom., 1992
There Are Planar Graphs Almost as Good as the Complete Graphs and Almost as Cheap as Minimum Spanning Trees.
Algorithmica, 1992
Proceedings of the LATIN '92, 1992
Proceedings of the Algorithms and Computation, Third International Symposium, 1992
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1992
1991
Proceedings of the Algorithms and Data Structures, 1991
Dynamic Detection of Forest of Tree-Connected Meshes.
Proceedings of the International Conference on Parallel Processing, 1991
Greedy Triangulation Approximates the Optimum and Can Be Implemented in Linear Time in the Average Case.
Proceedings of the Advances in Computing and Information, 1991
1990
A Note on a Parallel Heuristic for Minimum.
Bull. EATCS, 1990
Proceedings of the Algorithms, 1990
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1990
1989
On Parallel Complexity of the Subgraph Homeomorphism and the Subgraph Isomorphism Problem for Classes of Planar Graphs.
Theor. Comput. Sci., 1989
Theor. Comput. Sci., 1989
Heuristics for Optimum Binary Search Trees and Minimum Weight Triangulation Problems.
Theor. Comput. Sci., 1989
Inf. Process. Lett., 1989
Inf. Process. Lett., 1989
Ther Are Planar Graphs Almost as Good as the Complete Graphs and as Short as Minimum Spanning Trees.
Proceedings of the Optimal Algorithms, International Symposium, Varna, Bulgaria, May 29, 1989
1988
Greedy Triangulation acn be Efficiently Implemented in the Average Case (Extended Abstract).
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1988
Proceedings of the SWAT 88, 1988
A Polynomial-Time Algorithm for Subgraph Isomorphism of Two-Connected Series-Parallel Graphs.
Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988
1987
Algorithmica, 1987
Nearly Optimal Heuristics for Binary Search Trees with Geometric Generalizations (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987
Fast Parallel Algorithms for the Subgraph Homophormism and the Subgraph Isomorphism Problem for Classes of Planat Graphs.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1987
1986
On Approximation Behavior and Implementation of the Greedy Triangulation for Convex Planar Point Sets.
Proceedings of the Second Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry, 1986
1985
Proceedings of the First Annual Symposium on Computational Geometry, 1985
1984
Proceedings of the STACS 84, 1984
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1984
1983
Proceedings of the Theoretical Computer Science, 1983
Proceedings of the Logic Programming Workshop '83, Praia da Falésia, Algarve, Portugal, 26 June, 1983
The Greedy and Delauney Triangulations are not Bad in the Average Case and Minimum Weight Geometric Triangulation of Multi-Connected Polygons is NP-Complete.
Proceedings of the Fundamentals of Computation Theory, 1983
Proceedings of the CAAP'83, 1983
1982
1981
Proceedings of the CAAP '81, 1981
1979
The complexity of distributive computations.
Proceedings of the Fundamentals of Computation Theory, 1979
1978
Proceedings of the Automata, 1978