Andrzej Lingas
1 – 100 of 111
- show: 100
- |
- sort: year (new to old)
Close
Embed this list
<iframe src=""
width=""
height=""
allowtransparency="true"
frameborder="0">
</iframe>
- 2019
- A fast deterministic detection of small pattern graphs in graphs without large cliques
- The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets
- Clearing directed subgraphs by mobile agents : Variations on covering with paths
- Rare Siblings Speed-Up Deterministic Detection and Counting of Small Pattern Graphs
-
Pushing the Online Matrix-Vector Conjecture Off-Line and Identifying Its Easy Cases
Gasieniec, Leszek ; Jansson, Jesper LU ; Levcopoulos, Christos LU
;
Lingas, Andrzej
LU
and
Persson, Mia
LU
(2019)
In Lecture Notes in Computer Science
11458.
p.156-169
Mark
-
On a Fire Fighter’s Problem
Klein, Rolf ; Langetepe, Elmar ; Levcopoulos, Christos LU
;
Lingas, Andrzej
LU
and
Schwarzwald, Barbara
(2019)
In International Journal of Foundations of Computer Science
30(02).
p.231-246
Mark
- Lower bounds for Demorgan circuits of bounded negation width
- Graphs with equal domination and covering numbers
- 2018
-
3D Rectangulations and Geometric Matrix Multiplication
SAVONEN FLODERUS, PETER LU ; Jansson, Jesper ; Levcopoulos, Christos LU
;
Lingas, Andrzej
LU
and
SLEDNEU, DZMITRY
LU
(2018)
In Algorithmica
80(1).
p.136-154
Mark
- Forest-like abstract Voronoi diagrams in linear time
- Are unique subgraphs not easier to find?
- Extreme Witnesses and Their Applications
- Determining the consistency of resolved triplets and fan triplets
- Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems
- A QPTAS for the base of the number of crossing-free structures on a planar point set
- Approximation schemes for capacitated geometric network design
- 2017
-
Efficiently Correcting Matrix Products
Gasieniec, Leszek ; Levcopoulos, Christos LU
;
Lingas, Andrzej
LU
;
Pagh, Rasmus
and
Tokuyama, Takeshi
(2017)
In Algorithmica
79(2).
p.428-443
Mark
- The snow team problem : (Clearing Directed subgraphs by mobile agents)
-
Bamboo Garden Trimming Problem (Perpetual Maintenance of Machines with Different Attendance Urgency Factors)
Levcopoulos, Christos LU
;
Lingas, Andrzej
LU
;
Gąsieniec, Leszek
;
Klasing, Ralf
;
Min, Jie
and
Radzik, Tomasz
(2017)
10139.
p.229-240
Mark
- Bounds for semi-disjoint bilinear forms in a unit-cost computational model
- Towards an almost quadratic lower bound on the monotone circuit complexity of the Boolean convolution
- Determining the consistency of resolved triplets and fan triplets
- A fast deterministic detection of small pattern graphs in graphs without large cliques
- 2016
-
Efficiently Correcting Matrix Products (arXiv 2016)
Levcopoulos, Christos LU
;
Levcopoulos, Christos
LU
;
Lingas, Andrzej
LU
;
Pagh, Rasmus
and
Tokuyama, Takeshi
(2016)
Mark
- 2015
- Induced subgraph isomorphism: Are some patterns substantially easier than others?
- A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set
- A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows
- Detecting monomials with k distinct variables
- Detecting and Counting Small Pattern Graphs
- 2014
-
A note on a QPTAS for maximum weight triangulation of planar point sets
Levcopoulos, Christos LU
and
Lingas, Andrzej
LU
(2014)
In Information Processing Letters
114(8).
p.414-416
Mark
- Iterative merging heuristics for correlation clustering
-
3D Rectangulations and Geometric Matrix Multiplication
Floderus, Peter LU ; Jansson, Jesper ; Levcopoulos, Christos LU
;
Lingas, Andrzej
LU
and
Sledneu, Dzmitry
LU
(2014)
8889.
p.65-78
Mark
-
Clearing Connections by Few Agents
Levcopoulos, Christos LU
;
Lingas, Andrzej
LU
;
Nilsson, Bengt J
LU
and
Zylinski, Pawel
(2014)
8496.
p.289-300
Mark
- Simple Iterative Heuristics for Correlation Clustering
- Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems.
- Efficiently Correcting Matrix Products
- 2013
- Counting and Detecting Small Subgraphs via Equations
- Towards more efficient infection and fire fighting
- Detecting and Counting Small Pattern Graphs
- Efficient broadcasting in radio networks with long-range interference
- Unique subgraphs are not easier to find
- Optimal cuts and partitions in tree metrics in polynomial time
- 2012
- Linear-time 3-approximation algorithm for the r-star covering problem
- Exact and approximation algorithms for geometric and capacitated set cover problems
- A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs
- The complexity of inferring a minimally resolved phylogenetic supertree
- An Approximation Algorithm for Directed Shallow Steiner Trees
- 2011
- Approximation algorithms for buy-at-bulk geometric network design
- A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication
- 2010
- PTAS for k-tour cover poblem on the plane for moderately large values of k
- Approximability of edge matching puzzles
- 2009
- Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
- Faster multi-witnesses for Boolean matrix multiplication
- A fast output-sensitive algorithm for Boolean matrix multiplication
- An exact algorithm for subgraph homeomorphism
- Efficient broadcasting in known toplogy radio networks with long-range interference
- Efficient approximation algorithms for shortest cycles in undirected graphs
- PTAS for k-tour cover poblem on the plane for moderately large values of k
- 2008
- A path cover technique for LCAs in dags
- Linear-time 3-approximation algorithm for the r-star covering problem
- Efficient approximation algorithms for shortest cycles in undirected graphs
- Efficient Broadcasting in Known Geometric Radio Networks with Non-uniform Ranges
- Max-stretch reduction for tree spanners
- Approximate clustering of incomplete fingerprints
- Minimum k-connected geometric networks
- 2007
- Unique lowest common ancestors in dags are almost as easy as matrix multiplication
- Embedding point sets into plane graphs of small dilation
- Approximating the maximum clique minor and some subgraph homeomorphism problems.
- Note on covering monotone orthogonal polygons with star-shaped polygons
- Faster algorithms for finding lowest common ancestors in directed acyclic graphs
- Polynomial-time algorithms for the ordered maximum agreement subtree problem
- On the approximability of maximum and minimum edge clique partition problems
- On exact complexity of subgraph homeomorphism
- Finding a heaviest triangle is not harder than matrix multiplication
- Approximating the maximum independent set and minimum vertex coloring on box graphs
- 2006
-
A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation
Klein, Rolf ; Levcopoulos, Christos LU
and
Lingas, Andrzej
LU
(2006)
In Computational Geometry
34(1).
p.28-34
Mark
- Performing work in broadcast networks
- Finding a heaviest triangle is no harder than matrix multiplication
- Minimum-energy broadcasting in wireless networks in the d-dimensional Euclidean space (the alpha
- On the approximability of maximum and minimum edge clique partition problems
- 2005
- Embedding point sets into plane graphs of small dilation
- Polynomial time approximation schemes for max-bisection on planar and geometric graphs
- A note on maximum independent set and related problems on box graphs
- Approximate clustering of fingerprint vectors with missing values
- Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
- LCA queries in directed acyclic graphs
- Max-stretch reduction for tree spanners
- 2004
- Subexponential-time framework for optimal embeddings of graphs in integer lattices
- A fast algorithm for approximating the detour of a polygonal chain
- Approximation algorithms for Hamming clustering problems
- Approximation algorithms for MAX-BISECTION on low degree regular graphs
- Polynomial-time algorithms for the ordered maximum agreement subtree problem
- 2003
- Trade-offs between load and degree in virtual path layouts
- Improved approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
- Subexponential-time algorithms for maximum independent set and related problems on box graphs
- A fast algorithm for optimal alignment between similar ordered trees
- An improved bound on Boolean matrix multiplication for highly clustered data
- Fundamentals of computation theory
- 2002
- Gossiping with bounded size messages in ad hoc radio networks (Extended abstract)
- A geometric approach to Boolean matrix multiplication