Person:293198: Difference between revisions

From MaRDI portal
Person:293198
Created automatically from import230924090903
 
m AuthorDisambiguator moved page Andrzej Lingas to Andrzej Lingas: Duplicate
 
(No difference)

Latest revision as of 01:54, 9 December 2023

Available identifiers

zbMath Open lingas.andrzejMaRDI QIDQ293198

List of research outcomes

PublicationDate of PublicationType
https://portal.mardi4nfdi.de/entity/Q61285712024-04-15Paper
Greedy triangulation can be efficiently implemented in the average case2024-02-28Paper
Finding small complete subgraphs efficiently2023-12-22Paper
Maximum tree-packing in time O(n5/2)2023-12-12Paper
Perpetual maintenance of machines with different urgency requirements2023-10-24Paper
Online and Approximate Network Construction from Bounded Connectivity Constraints2023-08-18Paper
Lower bounds for monotone \(q\)-multilinear Boolean circuits2023-08-14Paper
An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs2023-05-08Paper
Fast skeleton construction2023-05-08Paper
Rare siblings speed-up deterministic detection and counting of small pattern graphs2023-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 histogram2022-12-16Paper
Fast algorithms for greedy triangulation2022-12-09Paper
A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon2022-12-09Paper
On parallel time in population protocols2022-10-28Paper
On parallel complexity of maximum f-matching and the degree sequence problem2022-08-18Paper
An O(n log n) algorithm for computing a link center in a simple polygon2022-08-16Paper
Lower Bounds for DeMorgan Circuits of Bounded Negation Width2022-07-18Paper
Lower bounds for Boolean circuits of bounded negation width2022-06-13Paper
Quantum and approximation algorithms for maximum witnesses of Boolean matrix products2022-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 cases2021-03-10Paper
A simple approach to nondecreasing paths2020-10-07Paper
https://portal.mardi4nfdi.de/entity/Q51219142020-09-22Paper
Simple Iterative Heuristics for Correlation Clustering2020-08-25Paper
Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth2020-04-21Paper
Graphs with equal domination and covering numbers2020-02-03Paper
Rare siblings speed-up deterministic detection and counting of small pattern graphs2020-01-30Paper
Approximation algorithms for the geometric firefighter and budget fence problems2019-10-29Paper
Pushing the online matrix-vector conjecture off-line and identifying its easy cases2019-10-11Paper
On a Fire Fighter’s Problem2019-06-24Paper
Clearing directed subgraphs by mobile agents. Variations on covering with paths2019-05-03Paper
A fast deterministic detection of small pattern graphs in graphs without large cliques2019-05-02Paper
Efficient algorithms for subgraph listing2019-03-26Paper
The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets2019-03-11Paper
Approximation Schemes for Capacitated Geometric Network Design2018-11-28Paper
Extreme witnesses and their applications2018-10-18Paper
Are unique subgraphs not easier to find?2018-04-04Paper
Determining the consistency of resolved triplets and fan triplets2018-03-22Paper
3D rectangulations and geometric matrix multiplication2018-02-28Paper
Forest-like abstract Voronoi diagrams in linear time2018-02-19Paper
A QPTAS for the base of the number of crossing-free structures on a planar point set2018-02-16Paper
Faster algorithms for subgraph isomorphism of κ-connected partial κ-trees2017-12-05Paper
The snow team problem (clearing directed subgraphs by mobile agents)2017-11-22Paper
Efficiently correcting matrix products2017-10-10Paper
https://portal.mardi4nfdi.de/entity/Q53651322017-09-29Paper
Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model2017-05-19Paper
Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the Boolean Convolution2017-05-19Paper
A Fast Deterministic Detection of Small Pattern Graphs in Graphs Without Large Cliques2017-05-05Paper
Bamboo Garden Trimming Problem (Perpetual Maintenance of Machines with Different Attendance Urgency Factors)2017-04-04Paper
On parallel complexity of planar triangulations2017-01-19Paper
A note on parallel complexity of maximum \(f\)-matching2016-06-09Paper
The do-all problem in broadcast networks2016-03-04Paper
Extreme Witnesses and Their Applications2016-02-05Paper
Induced subgraph isomorphism: are some patterns substantially easier than others?2015-10-30Paper
A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set2015-10-27Paper
Efficiently Correcting Matrix Products2015-09-11Paper
3D Rectangulations and Geometric Matrix Multiplication2015-09-11Paper
The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets2015-08-20Paper
Detecting and Counting Small Pattern Graphs2015-08-17Paper
A fast parallel algorithm for minimum-cost small integral flows2015-07-10Paper
https://portal.mardi4nfdi.de/entity/Q29346912014-12-18Paper
Detecting monomials with \(k\) distinct variables2014-12-09Paper
Optimal cuts and partitions in tree metrics in polynomial time2014-08-13Paper
Efficient broadcasting in known topology radio networks with long-range interference2014-07-23Paper
Corrigendum to ``Note on covering monotone orthogonal polygons2014-07-18Paper
A note on a QPTAS for maximum weight triangulation of planar point sets2014-04-30Paper
Computing the rooted triplet distance between galled trees by counting triangles2014-04-01Paper
Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems2014-03-31Paper
Detecting and Counting Small Pattern Graphs2014-01-14Paper
Unique subgraphs are not easier to find2013-10-22Paper
Counting and Detecting Small Subgraphs via Equations2013-09-26Paper
TOWARDS MORE EFFICIENT INFECTION AND FIRE FIGHTING2013-07-30Paper
Efficient broadcasting in radio networks with long-range interference2013-06-25Paper
Performing work in broadcast networks2013-06-13Paper
LINEAR-TIME 3-APPROXIMATION ALGORITHM FOR THE r-STAR COVERING PROBLEM2012-11-23Paper
Exact and approximation algorithms for geometric and capacitated set cover problems2012-11-21Paper
Induced Subgraph Isomorphism: Are Some Patterns Substantially Easier Than Others?2012-09-25Paper
Computing the Rooted Triplet Distance between Galled Trees by Counting Triangles2012-08-14Paper
A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs2012-06-15Paper
The Complexity of Inferring a Minimally Resolved Phylogenetic Supertree2012-05-30Paper
APPROXIMATION ALGORITHMS FOR BUY-AT-BULK GEOMETRIC NETWORK DESIGN2012-03-13Paper
A fast output-sensitive algorithm for Boolean matrix multiplication2011-08-16Paper
Approximation Schemes for Capacitated Geometric Network Design2011-07-06Paper
Near Approximation of Maximum Weight Matching through Efficient Weight Reduction2011-07-01Paper
Unique Small Subgraphs Are Not Easier to Find2011-06-03Paper
Subexponential-Time Algorithms for Maximum Independent Set and Related Problems on Box Graphs2011-03-18Paper
PTAS FOR k-TOUR COVER PROBLEM ON THE PLANE FOR MODERATELY LARGE VALUES OF k2011-01-19Paper
Efficient approximation algorithms for shortest cycles in undirected graphs2010-08-16Paper
Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems2010-07-20Paper
Faster multi-witnesses for Boolean matrix multiplication2010-06-16Paper
Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication2010-04-29Paper
Algorithms and Data Structures2010-04-20Paper
Note on covering monotone orthogonal polygons with star-shaped polygons2010-03-24Paper
Approximability of Edge Matching Puzzles2010-01-28Paper
PTAS for k-Tour Cover Problem on the Plane for Moderately Large Values of k2009-12-17Paper
An exact algorithm for subgraph homeomorphism2009-12-10Paper
Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth2009-12-04Paper
A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication2009-10-29Paper
Approximation Algorithms for Buy-at-Bulk Geometric Network Design2009-10-20Paper
A note on maximum independent set and related problems on box graphs2009-08-27Paper
Algorithms and Computation2009-08-07Paper
Approximating the maximum clique minor and some subgraph homeomorphism problems2009-06-22Paper
Efficient Broadcasting in Known Geometric Radio Networks with Non-uniform Ranges2008-11-20Paper
Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication2008-09-25Paper
A Path Cover Technique for LCAs in Dags2008-07-15Paper
Minimum-Energy Broadcasting in Wireless Networks in the d-Dimensional Euclidean Space (The α≤d Case)2008-04-17Paper
Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs2008-04-15Paper
Max-stretch reduction for tree spanners2008-04-03Paper
Linear-Time 3-Approximation Algorithm for the r-Star Covering Problem2008-03-25Paper
Approximating the Maximum Independent Set and Minimum Vertex Coloring on Box Graphs2008-01-04Paper
On Exact Complexity of Subgraph Homeomorphism2007-11-13Paper
Polynomial-time algorithms for the ordered maximum agreement subtree problem2007-08-20Paper
Faster algorithms for finding lowest common ancestors in directed acyclic graphs2007-07-16Paper
EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION2007-07-13Paper
Approximation algorithms for Hamming clustering problems2007-04-26Paper
ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS2007-04-25Paper
Algorithms and Computation2006-11-14Paper
Algorithms and Data Structures2006-10-25Paper
A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation2006-04-28Paper
Automata, Languages and Programming2006-01-10Paper
Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs2005-10-28Paper
Combinatorial Pattern Matching2005-09-07Paper
Algorithm Theory - SWAT 20042005-09-07Paper
https://portal.mardi4nfdi.de/entity/Q46542702005-03-03Paper
https://portal.mardi4nfdi.de/entity/Q48290022004-11-29Paper
https://portal.mardi4nfdi.de/entity/Q30464802004-08-12Paper
https://portal.mardi4nfdi.de/entity/Q47371732004-08-11Paper
https://portal.mardi4nfdi.de/entity/Q47372242004-08-11Paper
A fast algorithm for approximating the detour of a polygonal chain.2004-03-14Paper
https://portal.mardi4nfdi.de/entity/Q44329752003-10-29Paper
https://portal.mardi4nfdi.de/entity/Q44278712003-09-14Paper
https://portal.mardi4nfdi.de/entity/Q47961852003-03-02Paper
Approximation algorithms for time-dependent orienteering.2003-01-21Paper
On adaptive deterministic gossiping in ad hoc radio networks.2003-01-21Paper
https://portal.mardi4nfdi.de/entity/Q47827452002-12-02Paper
https://portal.mardi4nfdi.de/entity/Q47785602002-11-18Paper
https://portal.mardi4nfdi.de/entity/Q45477532002-08-21Paper
Efficient Merging and Construction of Evolutionary Trees2002-08-01Paper
https://portal.mardi4nfdi.de/entity/Q27625182002-01-09Paper
https://portal.mardi4nfdi.de/entity/Q42522992001-12-18Paper
https://portal.mardi4nfdi.de/entity/Q27542022001-12-09Paper
Approximation algorithms for maximum two-dimensional pattern matching2001-08-20Paper
https://portal.mardi4nfdi.de/entity/Q27239442001-07-08Paper
https://portal.mardi4nfdi.de/entity/Q45256792001-01-24Paper
https://portal.mardi4nfdi.de/entity/Q49533462001-01-14Paper
Maximum packing for biconnected outerplanar graphs2000-09-15Paper
Faster algorithms for subgraph isomorphism of \(k\)-connected partial \(k\)-trees2000-08-27Paper
Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time2000-06-04Paper
https://portal.mardi4nfdi.de/entity/Q49422332000-03-21Paper
An optimal algorithm for broadcasting multiple messages in trees2000-03-19Paper
https://portal.mardi4nfdi.de/entity/Q49426432000-03-16Paper
https://portal.mardi4nfdi.de/entity/Q42510502000-01-19Paper
On the complexity of constructing evolutionary trees1999-11-21Paper
https://portal.mardi4nfdi.de/entity/Q42684371999-10-31Paper
https://portal.mardi4nfdi.de/entity/Q42524021999-06-17Paper
https://portal.mardi4nfdi.de/entity/Q42467391999-06-15Paper
https://portal.mardi4nfdi.de/entity/Q42190461999-06-08Paper
Minimum convex partition of a polygon with holes by cuts in given directions1998-11-11Paper
A nearly parallel algorithm for the Voronoi diagram of a convex polygon1998-10-22Paper
Improved bounds for integer sorting in the EREW PRAM model1998-07-29Paper
Maximum tree-packing in time \(O(n^{5/2})\)1998-07-22Paper
https://portal.mardi4nfdi.de/entity/Q43645831997-12-15Paper
A simple randomized parallel algorithm for maximal f-matchings1997-02-28Paper
On 2-QBF truth testing in parallel1997-02-28Paper
Multilist layering: Complexity and applications1997-02-28Paper
A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity1997-02-27Paper
A LINEAR-TIME RANDOMIZED ALGORITHM FOR THE BOUNDED VORONOI DIAGRAM OF A SIMPLE POLYGON1996-12-16Paper
ON COMPUTING VORONOI DIAGRAMS FOR SORTED POINT SETS1996-04-16Paper
Optimal parallel algorithms for rectilinear link-distance problems1995-08-27Paper
MANHATTONIAN PROXIMITY IN A SIMPLE POLYGON1995-08-20Paper
https://portal.mardi4nfdi.de/entity/Q47646241995-06-08Paper
A linear-time construction of the relative neighborhood graph from the Delaunay triangulation1994-09-25Paper
PARALLEL ALGORITHMS FOR FINDING MAXIMAL k-DEPENDENT SETS AND MAXIMAL f-MATCHINGS1994-03-27Paper
https://portal.mardi4nfdi.de/entity/Q42815301994-03-10Paper
https://portal.mardi4nfdi.de/entity/Q40374071993-05-18Paper
Fast algorithms for greedy triangulation1992-12-14Paper
An \(O(n\log n)\) algorithm for computing the link center of a simple polygon1992-09-27Paper
There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees1992-09-27Paper
An unfeasible matching problem1992-06-28Paper
https://portal.mardi4nfdi.de/entity/Q39712671992-06-25Paper
Bit complexity of matrix products1991-01-01Paper
https://portal.mardi4nfdi.de/entity/Q33597851990-01-01Paper
https://portal.mardi4nfdi.de/entity/Q34843761989-01-01Paper
Subtree isomorphism is NC reducible to bipartite perfect matching1989-01-01Paper
Voronoi diagrams with barriers and the shortest diagonal problem1989-01-01Paper
On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs1989-01-01Paper
Heuristics for optimum binary search trees and minimum weight triangulation problems1989-01-01Paper
Subgraph isomorphism for biconnected outerplanar graphs in cubic time1989-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37967551988-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37982561988-01-01Paper
https://portal.mardi4nfdi.de/entity/Q38041901988-01-01Paper
Recognizing polygons, or how to spy1988-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37835951987-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37859671987-01-01Paper
A New Heuristic for Minimum Weight Triangulation1987-01-01Paper
On approximation behavior of the greedy triangulation for convex polygons1987-01-01Paper
Algorithms for minimum length partitions of polygons1987-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37310301986-01-01Paper
The greedy and Delaunay triangulations are not bad in the average case1986-01-01Paper
https://portal.mardi4nfdi.de/entity/Q32176011984-01-01Paper
https://portal.mardi4nfdi.de/entity/Q33393061984-01-01Paper
https://portal.mardi4nfdi.de/entity/Q33106341983-01-01Paper
https://portal.mardi4nfdi.de/entity/Q33116581983-01-01Paper
https://portal.mardi4nfdi.de/entity/Q39485881982-01-01Paper
https://portal.mardi4nfdi.de/entity/Q39624801982-01-01Paper
https://portal.mardi4nfdi.de/entity/Q39120321981-01-01Paper
https://portal.mardi4nfdi.de/entity/Q38592571979-01-01Paper
https://portal.mardi4nfdi.de/entity/Q41921121978-01-01Paper
https://portal.mardi4nfdi.de/entity/Q41944581978-01-01Paper
https://portal.mardi4nfdi.de/entity/Q41396891977-01-01Paper

Research outcomes over time


Doctoral students

No records found.


Known relations from the MaRDI Knowledge Graph

PropertyValue
MaRDI profile typeMaRDI person profile
instance ofhuman


This page was built for person: Andrzej Lingas