Andrzej Lingas

From MaRDI portal
(Redirected from Person:293198)



List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

PublicationDate of PublicationType
Quantum and approximation algorithms for maximum witnesses of Boolean matrix products
International Journal of Foundations of Computer Science
2024-10-30Paper
\((\min ,+)\) matrix and vector products for inputs decomposable into few monotone subsequences2024-08-22Paper
Efficient assignment of identities in anonymous populations
(available as arXiv preprint)
2024-04-15Paper
Greedy triangulation can be efficiently implemented in the average case
Graph-Theoretic Concepts in Computer Science
2024-02-28Paper
Finding small complete subgraphs efficiently
Lecture Notes in Computer Science
2023-12-22Paper
Maximum tree-packing in time O(n5/2)
Lecture Notes in Computer Science
2023-12-12Paper
Perpetual maintenance of machines with different urgency requirements
Journal of Computer and System Sciences
2023-10-24Paper
Online and Approximate Network Construction from Bounded Connectivity Constraints
International Journal of Foundations of Computer Science
2023-08-18Paper
Lower bounds for monotone \(q\)-multilinear Boolean circuits
Lecture Notes in Computer Science
2023-08-14Paper
Fast skeleton construction
Lecture Notes in Computer Science
2023-05-08Paper
An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs
Algorithms and Discrete Applied Mathematics
2023-05-08Paper
Rare siblings speed-up deterministic detection and counting of small pattern graphs
Algorithmica
2023-04-11Paper
Online and approximate network construction from bounded connectivity constraints2023-03-22Paper
Minimum convex partition of a polygon with holes by cuts in given directions2023-01-25Paper
A linear-time construction of the relative neighborhood graph within a histogram
Lecture Notes in Computer Science
2022-12-16Paper
Fast algorithms for greedy triangulation
SWAT 90
2022-12-09Paper
A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon
Algorithm Theory — SWAT '94
2022-12-09Paper
On parallel time in population protocols
Information Processing Letters
2022-10-28Paper
On parallel complexity of maximum \(f\)-matching and the degree sequence problem
Mathematical Foundations of Computer Science 1994
2022-08-18Paper
An \(O(n \log n)\) algorithm for computing a link center in a simple polygon
STACS 89
2022-08-16Paper
Lower Bounds for DeMorgan Circuits of Bounded Negation Width2022-07-18Paper
Lower bounds for Boolean circuits of bounded negation width
Journal of Computer and System Sciences
2022-06-13Paper
Quantum and approximation algorithms for maximum witnesses of Boolean matrix products
(available as arXiv preprint)
2022-03-24Paper
Solving hard problems by protein folding?2021-07-06Paper
Pushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy cases
Journal of Computer and System Sciences
2021-03-10Paper
A simple approach to nondecreasing paths
Information Processing Letters
2020-10-07Paper
scientific article; zbMATH DE number 7250166 (Why is no real title available?)2020-09-22Paper
Simple iterative heuristics for correlation clustering
Large-Scale Scientific Computing
2020-08-25Paper
Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth
Theoretical Computer Science
2020-04-21Paper
Graphs with equal domination and covering numbers
Journal of Combinatorial Optimization
2020-02-03Paper
Rare siblings speed-up deterministic detection and counting of small pattern graphs
Fundamentals of Computation Theory
2020-01-30Paper
Approximation algorithms for the geometric firefighter and budget fence problems
Algorithms
2019-10-29Paper
Pushing the online matrix-vector conjecture off-line and identifying its easy cases2019-10-11Paper
On a fire fighter's problem
International Journal of Foundations of Computer Science
2019-06-24Paper
Clearing directed subgraphs by mobile agents. Variations on covering with paths
Journal of Computer and System Sciences
2019-05-03Paper
A fast deterministic detection of small pattern graphs in graphs without large cliques
Theoretical Computer Science
2019-05-02Paper
Efficient algorithms for subgraph listing
Algorithms
2019-03-26Paper
The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets
Discrete Applied Mathematics
2019-03-11Paper
Approximation schemes for capacitated geometric network design
SIAM Journal on Discrete Mathematics
2018-11-28Paper
Extreme witnesses and their applications
Algorithmica
2018-10-18Paper
Are unique subgraphs not easier to find?
Information Processing Letters
2018-04-04Paper
Determining the consistency of resolved triplets and fan triplets2018-03-22Paper
3D rectangulations and geometric matrix multiplication
Algorithmica
2018-02-28Paper
Forest-like abstract Voronoi diagrams in linear time
Computational Geometry
2018-02-19Paper
A QPTAS for the base of the number of crossing-free structures on a planar point set
Theoretical Computer Science
2018-02-16Paper
Faster algorithms for subgraph isomorphism of \(k\)-connected partial \(k\)-trees
Algorithms — ESA '96
2017-12-05Paper
The snow team problem (clearing directed subgraphs by mobile agents)
(available as arXiv preprint)
2017-11-22Paper
Efficiently correcting matrix products
Algorithmica
2017-10-10Paper
Counting and detecting small subgraphs via equations and matrix multiplication2017-09-29Paper
Towards an almost quadratic lower bound on the monotone circuit complexity of the Boolean convolution
Lecture Notes in Computer Science
2017-05-19Paper
Bounds for semi-disjoint bilinear forms in a unit-cost computational model
Lecture Notes in Computer Science
2017-05-19Paper
A fast deterministic detection of small pattern graphs in graphs without large cliques
WALCOM: Algorithms and Computation
2017-05-05Paper
Bamboo garden trimming problem (perpetual maintenance of machines with different attendance urgency factors)
SOFSEM 2017: Theory and Practice of Computer Science
2017-04-04Paper
On parallel complexity of planar triangulations
Lecture Notes in Computer Science
2017-01-19Paper
A note on parallel complexity of maximum \(f\)-matching
Information Processing Letters
2016-06-09Paper
The do-all problem in broadcast networks
Proceedings of the twentieth annual ACM symposium on Principles of distributed computing
2016-03-04Paper
Extreme witnesses and their applications
Combinatorial Optimization and Applications
2016-02-05Paper
Induced subgraph isomorphism: are some patterns substantially easier than others?
Theoretical Computer Science
2015-10-30Paper
A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set
Automata, Languages, and Programming
2015-10-27Paper
Efficiently correcting matrix products
Algorithms and Computation
2015-09-11Paper
Efficiently correcting matrix products
Algorithms and Computation
2015-09-11Paper
3D rectangulations and geometric matrix multiplication
Algorithms and Computation
2015-09-11Paper
The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets
Combinatorial Pattern Matching
2015-08-20Paper
Detecting and counting small pattern graphs
SIAM Journal on Discrete Mathematics
2015-08-17Paper
A fast parallel algorithm for minimum-cost small integral flows
Algorithmica
2015-07-10Paper
Finding a heaviest triangle is not harder than matrix multiplication2014-12-18Paper
Detecting monomials with \(k\) distinct variables
Information Processing Letters
2014-12-09Paper
Optimal cuts and partitions in tree metrics in polynomial time
Information Processing Letters
2014-08-13Paper
Efficient broadcasting in known topology radio networks with long-range interference
Proceedings of the 28th ACM symposium on Principles of distributed computing
2014-07-23Paper
Corrigendum to ``Note on covering monotone orthogonal polygons
Information Processing Letters
2014-07-18Paper
A note on a QPTAS for maximum weight triangulation of planar point sets
Information Processing Letters
2014-04-30Paper
Computing the rooted triplet distance between galled trees by counting triangles
Journal of Discrete Algorithms
2014-04-01Paper
Approximation algorithms for the geometric firefighter and budget fence problems
LATIN 2014: Theoretical Informatics
2014-03-31Paper
Detecting and Counting Small Pattern Graphs
Algorithms and Computation
2014-01-14Paper
Unique subgraphs are not easier to find
International Journal of Computer Mathematics
2013-10-22Paper
Counting and detecting small subgraphs via equations
SIAM Journal on Discrete Mathematics
2013-09-26Paper
Towards more efficient infection and fire fighting
International Journal of Foundations of Computer Science
2013-07-30Paper
Efficient broadcasting in radio networks with long-range interference
Distributed Computing
2013-06-25Paper
Performing work in broadcast networks
Distributed Computing
2013-06-13Paper
Linear-time 3-approximation algorithm for the \(r\)-star covering problem
International Journal of Computational Geometry & Applications
2012-11-23Paper
Exact and approximation algorithms for geometric and capacitated set cover problems
Algorithmica
2012-11-21Paper
Induced subgraph isomorphism: are some patterns substantially easier than others?
Lecture Notes in Computer Science
2012-09-25Paper
Computing the rooted triplet distance between galled trees by counting triangles
Combinatorial Pattern Matching
2012-08-14Paper
A combinatorial algorithm for all-pairs shortest paths in directed vertex-weighted graphs with applications to disc graphs
SOFSEM 2012: Theory and Practice of Computer Science
2012-06-15Paper
The complexity of inferring a minimally resolved phylogenetic supertree
SIAM Journal on Computing
2012-05-30Paper
Approximation algorithms for buy-at-bulk geometric network design
International Journal of Foundations of Computer Science
2012-03-13Paper
A fast output-sensitive algorithm for Boolean matrix multiplication
Algorithmica
2011-08-16Paper
Approximation schemes for capacitated geometric network design
Automata, Languages and Programming
2011-07-06Paper
Near approximation of maximum weight matching through efficient weight reduction
Lecture Notes in Computer Science
2011-07-01Paper
Unique small subgraphs are not easier to find
Language and Automata Theory and Applications
2011-06-03Paper
Subexponential-time algorithms for Maximum Independent Set and related problems on box graphs
Lecture Notes in Computer Science
2011-03-18Paper
PTAS for \(k\)-tour cover problem on the plane for moderately large values of \(k^*\)
International Journal of Foundations of Computer Science
2011-01-19Paper
Efficient approximation algorithms for shortest cycles in undirected graphs
Information Processing Letters
2010-08-16Paper
Exact and approximation algorithms for geometric and capacitated set cover problems
Lecture Notes in Computer Science
2010-07-20Paper
Faster multi-witnesses for Boolean matrix multiplication
Information Processing Letters
2010-06-16Paper
Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
SIAM Journal on Computing
2010-04-29Paper
An improved bound on Boolean matrix multiplication for highly clustered data.
Lecture Notes in Computer Science
2010-04-20Paper
Note on covering monotone orthogonal polygons with star-shaped polygons
Information Processing Letters
2010-03-24Paper
Approximability of Edge Matching Puzzles
SOFSEM 2010: Theory and Practice of Computer Science
2010-01-28Paper
PTAS for \(k\)-tour cover problem on the plane for moderately large values of \(k\)
Algorithms and Computation
2009-12-17Paper
An exact algorithm for subgraph homeomorphism
Journal of Discrete Algorithms
2009-12-10Paper
Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
Information Processing Letters
2009-12-04Paper
A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication
Lecture Notes in Computer Science
2009-10-29Paper
Approximation Algorithms for Buy-at-Bulk Geometric Network Design
Lecture Notes in Computer Science
2009-10-20Paper
A note on maximum independent set and related problems on box graphs
Information Processing Letters
2009-08-27Paper
Algorithms and Computation
Lecture Notes in Computer Science
2009-08-07Paper
Approximating the maximum clique minor and some subgraph homeomorphism problems
Theoretical Computer Science
2009-06-22Paper
Efficient Broadcasting in Known Geometric Radio Networks with Non-uniform Ranges
Lecture Notes in Computer Science
2008-11-20Paper
Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication
Algorithms – ESA 2007
2008-09-25Paper
A Path Cover Technique for LCAs in Dags
Algorithm Theory – SWAT 2008
2008-07-15Paper
Minimum-Energy Broadcasting in Wireless Networks in the d-Dimensional Euclidean Space (The α≤d Case)
Combinatorial and Algorithmic Aspects of Networking
2008-04-17Paper
Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
Lecture Notes in Computer Science
2008-04-15Paper
Max-stretch reduction for tree spanners
Algorithmica
2008-04-03Paper
Linear-Time 3-Approximation Algorithm for the r-Star Covering Problem
WALCOM: Algorithms and Computation
2008-03-25Paper
Approximating the Maximum Independent Set and Minimum Vertex Coloring on Box Graphs
Algorithmic Aspects in Information and Management
2008-01-04Paper
On Exact Complexity of Subgraph Homeomorphism
Lecture Notes in Computer Science
2007-11-13Paper
Polynomial-time algorithms for the ordered maximum agreement subtree problem
Algorithmica
2007-08-20Paper
Faster algorithms for finding lowest common ancestors in directed acyclic graphs
Theoretical Computer Science
2007-07-16Paper
EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION
International Journal of Computational Geometry & Applications
2007-07-13Paper
Approximation algorithms for Hamming clustering problems
Journal of Discrete Algorithms
2007-04-26Paper
ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS
International Journal of Foundations of Computer Science
2007-04-25Paper
Algorithms and Computation
Lecture Notes in Computer Science
2006-11-14Paper
Algorithms and Data Structures
Lecture Notes in Computer Science
2006-10-25Paper
A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation
Computational Geometry
2006-04-28Paper
Automata, Languages and Programming
Lecture Notes in Computer Science
2006-01-10Paper
Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
SIAM Journal on Computing
2005-10-28Paper
Algorithm Theory - SWAT 2004
Lecture Notes in Computer Science
2005-09-07Paper
Combinatorial Pattern Matching
Lecture Notes in Computer Science
2005-09-07Paper
scientific article; zbMATH DE number 2140434 (Why is no real title available?)2005-03-03Paper
scientific article; zbMATH DE number 2119728 (Why is no real title available?)2004-11-29Paper
scientific article; zbMATH DE number 2089211 (Why is no real title available?)2004-08-12Paper
scientific article; zbMATH DE number 2086637 (Why is no real title available?)2004-08-11Paper
scientific article; zbMATH DE number 2086687 (Why is no real title available?)2004-08-11Paper
A fast algorithm for approximating the detour of a polygonal chain.
Computational Geometry
2004-03-14Paper
scientific article; zbMATH DE number 1998340 (Why is no real title available?)2003-10-29Paper
scientific article; zbMATH DE number 1979525 (Why is no real title available?)2003-09-14Paper
scientific article; zbMATH DE number 1875426 (Why is no real title available?)2003-03-02Paper
Approximation algorithms for time-dependent orienteering.
Information Processing Letters
2003-01-21Paper
On adaptive deterministic gossiping in ad hoc radio networks.
Information Processing Letters
2003-01-21Paper
scientific article; zbMATH DE number 1839476 (Why is no real title available?)2002-12-02Paper
scientific article; zbMATH DE number 1830739 (Why is no real title available?)2002-11-18Paper
scientific article; zbMATH DE number 1786462 (Why is no real title available?)2002-08-21Paper
Efficient merging and construction of evolutionary trees
Journal of Algorithms
2002-08-01Paper
scientific article; zbMATH DE number 1688377 (Why is no real title available?)2002-01-09Paper
scientific article; zbMATH DE number 1305417 (Why is no real title available?)2001-12-18Paper
scientific article; zbMATH DE number 1670876 (Why is no real title available?)2001-12-09Paper
Approximation algorithms for maximum two-dimensional pattern matching
Theoretical Computer Science
2001-08-20Paper
scientific article; zbMATH DE number 1615274 (Why is no real title available?)2001-07-08Paper
scientific article; zbMATH DE number 1555916 (Why is no real title available?)2001-01-24Paper
scientific article; zbMATH DE number 1444316 (Why is no real title available?)2001-01-14Paper
Maximum packing for biconnected outerplanar graphs
Discrete Applied Mathematics
2000-09-15Paper
Faster algorithms for subgraph isomorphism of \(k\)-connected partial \(k\)-trees
Algorithmica
2000-08-27Paper
Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time
Theoretical Computer Science
2000-06-04Paper
scientific article; zbMATH DE number 1419215 (Why is no real title available?)2000-03-21Paper
An optimal algorithm for broadcasting multiple messages in trees
Journal of Parallel and Distributed Computing
2000-03-19Paper
scientific article; zbMATH DE number 1414306 (Why is no real title available?)2000-03-16Paper
scientific article; zbMATH DE number 1304319 (Why is no real title available?)2000-01-19Paper
On the complexity of constructing evolutionary trees
Journal of Combinatorial Optimization
1999-11-21Paper
scientific article; zbMATH DE number 1354124 (Why is no real title available?)1999-10-31Paper
scientific article; zbMATH DE number 1305511 (Why is no real title available?)1999-06-17Paper
scientific article; zbMATH DE number 1301093 (Why is no real title available?)1999-06-15Paper
scientific article; zbMATH DE number 1223730 (Why is no real title available?)1999-06-08Paper
Minimum convex partition of a polygon with holes by cuts in given directions
Theory of Computing Systems
1998-11-11Paper
A nearly parallel algorithm for the Voronoi diagram of a convex polygon
Theoretical Computer Science
1998-10-22Paper
Improved bounds for integer sorting in the EREW PRAM model
Journal of Parallel and Distributed Computing
1998-07-29Paper
Maximum tree-packing in time \(O(n^{5/2})\)
Theoretical Computer Science
1998-07-22Paper
scientific article; zbMATH DE number 1088267 (Why is no real title available?)1997-12-15Paper
A simple randomized parallel algorithm for maximal f-matchings
Information Processing Letters
1997-02-28Paper
On 2-QBF truth testing in parallel
Information Processing Letters
1997-02-28Paper
Multilist layering: Complexity and applications
Theoretical Computer Science
1997-02-28Paper
A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity
Information Processing Letters
1997-02-27Paper
A LINEAR-TIME RANDOMIZED ALGORITHM FOR THE BOUNDED VORONOI DIAGRAM OF A SIMPLE POLYGON
International Journal of Computational Geometry & Applications
1996-12-16Paper
ON COMPUTING VORONOI DIAGRAMS FOR SORTED POINT SETS
International Journal of Computational Geometry & Applications
1996-04-16Paper
Optimal parallel algorithms for rectilinear link-distance problems
Algorithmica
1995-08-27Paper
MANHATTONIAN PROXIMITY IN A SIMPLE POLYGON
International Journal of Computational Geometry & Applications
1995-08-20Paper
scientific article; zbMATH DE number 751133 (Why is no real title available?)1995-06-08Paper
A linear-time construction of the relative neighborhood graph from the Delaunay triangulation
Computational Geometry
1994-09-25Paper
PARALLEL ALGORITHMS FOR FINDING MAXIMAL k-DEPENDENT SETS AND MAXIMAL f-MATCHINGS
International Journal of Foundations of Computer Science
1994-03-27Paper
scientific article; zbMATH DE number 512837 (Why is no real title available?)1994-03-10Paper
scientific article; zbMATH DE number 177538 (Why is no real title available?)1993-05-18Paper
Fast algorithms for greedy triangulation
BIT
1992-12-14Paper
There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees
Algorithmica
1992-09-27Paper
An \(O(n\log n)\) algorithm for computing the link center of a simple polygon
Discrete & Computational Geometry
1992-09-27Paper
An unfeasible matching problem
BIT
1992-06-28Paper
scientific article; zbMATH DE number 8779 (Why is no real title available?)1992-06-25Paper
Bit complexity of matrix products
Information Processing Letters
1991-01-01Paper
scientific article; zbMATH DE number 4213471 (Why is no real title available?)1990-01-01Paper
On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs
Theoretical Computer Science
1989-01-01Paper
Heuristics for optimum binary search trees and minimum weight triangulation problems
Theoretical Computer Science
1989-01-01Paper
scientific article; zbMATH DE number 4155926 (Why is no real title available?)1989-01-01Paper
Voronoi diagrams with barriers and the shortest diagonal problem
Information Processing Letters
1989-01-01Paper
Subgraph isomorphism for biconnected outerplanar graphs in cubic time
Theoretical Computer Science
1989-01-01Paper
Subtree isomorphism is NC reducible to bipartite perfect matching
Information Processing Letters
1989-01-01Paper
Recognizing polygons, or how to spy
The Visual Computer
1988-01-01Paper
scientific article; zbMATH DE number 4062598 (Why is no real title available?)1988-01-01Paper
scientific article; zbMATH DE number 4064506 (Why is no real title available?)1988-01-01Paper
scientific article; zbMATH DE number 4072379 (Why is no real title available?)1988-01-01Paper
A New Heuristic for Minimum Weight Triangulation
SIAM Journal on Algebraic Discrete Methods
1987-01-01Paper
scientific article; zbMATH DE number 4047146 (Why is no real title available?)1987-01-01Paper
scientific article; zbMATH DE number 4049079 (Why is no real title available?)1987-01-01Paper
On approximation behavior of the greedy triangulation for convex polygons
Algorithmica
1987-01-01Paper
Algorithms for minimum length partitions of polygons
BIT
1987-01-01Paper
scientific article; zbMATH DE number 3963193 (Why is no real title available?)1986-01-01Paper
The greedy and Delaunay triangulations are not bad in the average case
Information Processing Letters
1986-01-01Paper
scientific article; zbMATH DE number 3872705 (Why is no real title available?)1984-01-01Paper
scientific article; zbMATH DE number 3883609 (Why is no real title available?)1984-01-01Paper
scientific article; zbMATH DE number 3841230 (Why is no real title available?)1983-01-01Paper
scientific article; zbMATH DE number 3839975 (Why is no real title available?)1983-01-01Paper
scientific article; zbMATH DE number 3784283 (Why is no real title available?)1982-01-01Paper
scientific article; zbMATH DE number 3767037 (Why is no real title available?)1982-01-01Paper
scientific article; zbMATH DE number 3723874 (Why is no real title available?)1981-01-01Paper
scientific article; zbMATH DE number 3660791 (Why is no real title available?)1979-01-01Paper
scientific article; zbMATH DE number 3633714 (Why is no real title available?)1978-01-01Paper
scientific article; zbMATH DE number 3630813 (Why is no real title available?)1978-01-01Paper
scientific article; zbMATH DE number 3568031 (Why is no real title available?)1977-01-01Paper


Research outcomes over time


This page was built for person: Andrzej Lingas