An improved bound on Boolean matrix (2009)
Leszek G Asieniec, Andrzej Lingas
multiplication for highly clustered data
PTAS for k-tour cover problem on the plane for moderately large values of k (2009)
Adamaszek, Anna, Czumaj, Artur, Lingas, Andrzej
Let P be a set of n points in the Euclidean plane and let O be the origin point in the plane. In the k-tour cover problem (called frequently the capacitated vehicle routing problem), the goal is to...
Berman, Piotr, Karpinski, Marek, Lingas, Andrzej
First, we study geometric variants of the standard set cover motivated by assignment of directional antenna and shipping with deadlines, providing the first known polynomial-time exact solutions....
Approximating the maximum clique minor and some (2008)
Noga Alon, Andrzej Lingas, Martin Wahlen
subgraph homeomorphism problems
Approximation algorithms for optimization problems in (2008)
Artur Czumaj, Magnús M. Halldórsson, Andrzej Lingas, Johan Nilsson
graphs with superlogarithmic treewidth
IOS Press A Fast Algorithm for Optimal Alignment between Similar Ordered Trees (2008)
Jesper Jansson, Andrzej Lingas
Abstract. We present a fast algorithm for optimal alignment between two similar ordered trees with node labels. Let ¢ and £ be two such trees with ¤ ¢ ¤ and ¤ £ ¤ nodes, respectively. If...
Artur Czumaj, Mirosław Kowaluk, Andrzej Lingas
algorithms for finding lowest common ancestors
We present a new algorithm for solving the all-pairs lowest common ancestor problem in directed acyclic graphs (dags). Our algorithm runs in time O(n 2+λ), where λ satisfies the equation ω(1, λ,...
Approximation Schemes for Minimum-Cost k-Connectivity (2008)
Problems In Geometric, Artur Czumaj, Andrzej Lingas
this paper. Note that, in particular, this includes the Steiner tree problem (see, e.g., [2]), in which {0, 1} for any vertex v V . It also includes the most widely applied variant of the...
Finding a Heaviest Triangle is not Harder than (2008)
Matrix Multiplication Artur, Artur Czumaj, Andrzej Lingas
We show that for any # > 0, a maximum-weight triangle in an undirected graph with n vertices and real weights assigned to vertices can be found in time O(n is the exponent of fastest matrix...
Leszek Gasieniec, Jesper Jansson, Andrzej Lingas
In this paper we study a few important tree optimization problems with applications to computational biology. These problems ask for trees that are consistent with an as large part of the given data...
Anil Maheshwari, Andrzej Lingas, Andrzej Lingas
We present optimal parallel solutions to reporting paths between pairs of nodes in an n\Gammanode tree. Our algorithms are deterministic and designed to run on an exclusive read exclusive write...
Inferring Ordered Trees from Local Constraints (2007)
Leszek Asieniec, Jesper Jansson, Andrzej Lingas, Anna Ostlin
. We consider a problem of inferring an ordered tree from a set of local constraints on its leaves which we term as the ordered local consensus tree problem. Using our efficient decremental interval...
Bogdan S. Chlebus, Dariusz R. Kowalski, Andrzej Lingas
Abstract: The problem of performing t tasks in a distributed system on p failure-prone processors is one of the fundamental problems in distributed computing. If the tasks are similar and independent...
Ecient Approximation Algorithms for the Hamming Center Problem (2007)
Jesper Jansson, Andrzej Lingas
The Hamming center problem for a set S of k binary strings, each of length n, asks for a binary string of length n that minimizes the maximum Hamming distance between and any string in S. The...
Leszek Gasieniec, Jesper Jansson, Andrzej Lingas, Anna Ostlin
Abstract. We consider a problem of inferring an ordered tree from a set of local constraints on its leaves which we term as the ordered local consensus tree problem. Using our efficient decremental...
Leszek Gasieniec, Jesper Jansson, Andrzej Lingas
Abstract. In this paper we study a few important tree optimization problems with applications to computational biology. These problems ask for trees that are consistent with an as large part of the...
We present the first truly polynomial-time approximation scheme (PTAS) for the minimum-cost k-vertex- (or, k-edge-) connected spanning subgraph problem for complete
Fast approximation schemes for Euclidean minimum-cost multi-connectivity (2007)
We present fast approximation algorithms for various variants of the minimum-cost k-connected spanning subgraph problem in geometrical graphs. We provide a randomized approximation scheme for nding a...
On parallel complexity of maximum f-matching and the degree (2007)
Anders Dessmark, Oscar Garrido, Andrzej Lingas
sequence problem
Christos Levcopoulos, Andrzej Lingas, Hristo Djidjev
Let q be a nonnegative integer. For a graph G, the maximum q-dependent set problem is to find a maximum cardinality subset of the set of vertices of G such that none of the vertices in the subset has...
Klaus Jansen, Marek Karpinski, Andrzej Lingas, Eike Seidel
Abstract. The Max-Bisection and Min-Bisection problems are to nd a partition of the vertices of a graph into two equal size subsets that respectively maximizes or minimizes the number of edges with...
On the Approximability of Maximum and Minimum Edge Clique Partition Problems (2006)
Anders Dessmark, Jesper Jansson, Andrzej Lingas, Eva-marta Lundell, Mia Persson
We consider the following clustering problems: given a general undirected graph, partition its vertices into disjoint clusters such that each cluster forms a clique and the number of edges within the...
Approximate Clustering of Fingerprint Vectors with Missing Values (2005)
Andres Figueroa, Avraham Goldstein, Tao Jiang, Maciej Kurowski, Andrzej Lingas, Mia Persson
We study the problem of clustering fingerprints with at most p missing values (CMV(p) for short) naturally arising in oligonucleotide fingerprinting, which is an e#cient method for characterizing DNA...
Embedding Point Sets into Plane Graphs of Small Dilation (2005)
Annette Ebbers-Baumann, Ansgar Grüne, Marek Karpinski, Rolf Klein, Christian Knauer, Andrzej Lingas
Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S?EvenforasetS as simple as five points evenly placed on the circle, this question seems...
Embedding point sets into plane graphs of small dilation (2005)
Annette Ebbers-baumann, Ansgar Grüne, Marek Karpinski, Rolf Klein, Christian Knauer, Andrzej Lingas
Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S? Even for a set S as simple as five points evenly placed on the circle, this question...
Artur Czumaj, Andrzej Lingas, Johan Nilsson
In this paper we present two novel generic schemes for approximation algorithms for optimization to partial k-trees. Our first scheme yields deterministic polynomialtime algorithms achieving...
Approximation algorithms for time-dependent orienteering (2002)
Fomin, Fedor V., Lingas, Andrzej
The time-dependent orienteering problem is dual to the time-dependent traveling salesman problem. It consists of visiting a maximum number of sites within a given deadline. The traveling time between...
On adaptive deterministic gossiping in ad hoc radio networks (2002)
Gasieniec, Leszek, Lingas, Andrzej
We study deterministic algorithms for gossiping problem in ad hoc radio networks. The efficiency of communication algorithms in radio networks is very often expressed in terms of: maximum...
Polynomial-time approximation schemes for the Euclidean survivable network design problem (2002)
Artur Czumaj, Andrzej Lingas, Hairong Zhao
Abstract. The survivable network design problem is a classical problem in combinatorial optimization of constructing a minimum-cost subgraph satisfying predetermined connectivity requirements. In...
A Fast Algorithm for Optimal Alignment between Similar Ordered Trees (2001)
Jansson, Jesper, Lingas, Andrzej
Not available.
Fast Boolean matrix multiplication for highly clustered data (2001)
Björklund, Andreas, Lingas, Andrzej
We consider the problem of computing the product of two n×n Boolean matrices A and B. For an n×n Boolean matrix C, let GC be the complete weighted graph on the rows of C where the weight of an edge...
Approximation algorithms for maximum two-dimensional pattern matching (2001)
Arikati,Srinivasa Rao, Dessmark,Anders, Lingas,Andrzej, Marathe,Madhav V.
Approximation algorithms for maximum two-dimensional pattern matching (2001)
Arikati, Srinivasa Rao, Dessmark, Anders, Lingas, Andrzej, Marathe, Madhav V.
The Do-All problem in broadcast networks (2001)
Bogdan S. Chlebus, Uniwersytet Warszawski, Dariusz R. Kowalski, Instytut Informatyki, Instytut Informatyki, Andrzej Lingas
The problem of performing t tasks in a distributed system on p failure-prone processors is one of the fundamental problems in distributed computing. If the tasks are similar and independent and the...
Oblivious gossiping in ad-hoc radio networks (2001)
Bogdan S. Chlebus, Andrzej Lingas, Aris T. Pagourtzis
We study oblivious deterministic and randomized algorithms for gossiping in unknown radio networks. In oblivious algorithms the fact (or probability in case of randomized algorithm) that a processor...
A fast algorithm for optimal alignment between similar ordered trees (2001)
Jesper Jansson, Andrzej Lingas
Abstract. We present a fast algorithm for optimal alignment between two similar ordered trees with node labels. Let S and T be two such trees with jSj and jT j nodes, respectively. An optimal...
Oblivious Gossiping in Ad-Hoc Radio Networks (2001)
Bogdan S. Chlebus, Leszek Gasieniec, Andrzej Lingas, Aris T. Pagourtzis, Bogdan S. Chlebus£leszek, Lingasþaris T. Pagourtzisüß
We study oblivious deterministic and randomized algorithms for gossiping in unknown radio networks. In oblivious algorithms the fact (or probability in case of randomized algorithm) that a processor...
Fast Approximation Schemes for Euclidean Multi-Connectivity Problems (2000)
Czumaj, Artur, Lingas, Andrzej
We present new polynomial-time approximation schemes (PTAS) for several basic minimum-cost multi-connectivity problems in geometrical graphs. We focus on low connectivity requirements. Each of our...
Approximation Algorithms for Hamming Clustering Problems (2000)
Leszek Gasieniec, Jesper Jansson, Andrzej Lingas
. We study Hamming versions of two classical clustering problems. The Hamming radius p-clustering problem (HRC) for a set S of k binary strings, each of length n, is to nd p binary strings of length...
Fast Approximation Schemes for Euclidean Multi-Connectivity Problems (Extended Abstract) (2000)
) Artur Czumaj 1?? and Andrzej Lingas 2 1 Department of Computer and Information Science, New Jersey Institute of Technology, Newark, NJ 07102-1982, USA. czumaj@cis.njit.edu 2 Department of Computer...
On the complexity of constructing evolutionary trees (1999)
Jesper Jansson, Andrzej Lingas, Anna Ostlin
Abstract. In this paper we study a few important tree optimization problems with applications to computational biology. These problems ask for trees that are consistent with an as large part of the...
Efficient merging, construction, and maintenance of evolutionary trees (1999)
We present new techniques of eciently merging and updating partial evolutionary trees in the so called experiment model. We show that two partial evolutionary trees for disjoint sets of species can...
Balanced randomized tree splitting with applications to evolutionary tree constructions (1999)
Ming-yang Kao, Andrzej Lingas, Anna Ostlin
Abstract. We present a new technique called balanced randomized tree splitting. It is useful in constructing unknown trees recursively. By applying it we obtain two new results on e#cient...
Efficient Merging, Construction, and Maintenance of Evolutionary Trees (1999)
Andrzej Lingas, Hans Olsson, Anna Östlin
. We present new techniques of eciently merging and updating partial evolutionary trees in the so called experiment model. We show that two partial evolutionary trees for disjoint sets of species can...
On Approximability of the Minimum-Cost k-Connected Spanning Subgraph Problem (1999)
We present the first truly polynomial-time approximation scheme (PTAS) for the minimum-cost k-vertex- (or, k- edge-) connected spanning subgraph problem for complete Euclidean graphs in R d :...
Efficient Approximation Algorithms for the Hamming Center Problem (1999)
Leszek Gasieniec, Jesper Jansson, Andrzej Lingas
The Hamming center problem for a set S of k binary strings, each of length n, is to find a binary string fi of length n that minimizes the maximum Hamming distance between fi and any string in S. Its...
Balanced randomized tree splitting with applications to evolutionary tree constructions (1999)
Ming-yang Kao, Andrzej Lingas, Anna Östlin
Abstract. We present a new technique called balanced randomized tree splitting. It is useful in constructing unknown trees recursively. By applying it we obtain two new results on efficient...
Anders Dessmark, Carsten Dorgerloh, Andrzej Lingas, Jurgen Wirtgen
Abstract. We present a rst randomized O(log (k) n) time and O(n+m) work CRCW-PRAM algorithm for nding a spanning forest of an undirected dense graph with n vertices. Furthermore we construct a...
A Polynomial Time Approximation Scheme for Euclidean Minimum Cost k-Connectivity (1998)
. We present polynomial-time approximation schemes for the problem of finding a minimum-cost k-connected Euclidean graph on a finite point set in R d : The cost of an edge in such a graph is equal to...
Anders Dessmark, Carsten Dorgerloh, Andrzej Lingas, Jürgen Wirtgen
We present a first randomized O(log (k) n) time and O(n+m) work CRCW-PRAM algorithm for finding a spanning forest of an undirected dense graph with n vertices. Furthermore we construct a randomized...
On the Complexity of Computing Evolutionary Trees (1997)
Leszek Gasieniec, Jesper Jansson, Andrzej Lingas, Anna Östlin
. In this paper we study a few important tree optimization problems with applications to computational biology. These problems ask for trees that are consistent with an as large part of the given...
Inferring Ordered Trees from Local Constraints (1997)
Leszek Gasieniec, Jesper Jansson, Andrzej Lingas, Anna Östlin
We consider a problem of inferring an ordered tree from a set of local constraints on its leaves which we term as the ordered local consensus tree problem. Using our efficient decremental interval...
Fast Skeleton Construction (1995)
For a polygon P , the skeleton of P is a partition of P into regions assigned to the edges of P: A point p inside P belongs to the region of an edge e if and only if e is the closest edge of P: We...
On Parallel Complexity of Planar Triangulations (1994)
Christos Levcopoulos, Andrzej Lingas, Cao Wang
The greedy triangulation of a finite planar point set is obtained by repeatedly inserting a shortest diagonal that doesn't intersect those already in the plane. We show that the problem of...
A Linear-Time Randomized Algorithm for the Bounded Voronoi Diagram of a Simple Polygon (1994)
For a polygon P , the bounded Voronoi diagram of P is a partition of P into regions assigned to the vertices of P: A point p inside P belongs to the region of a vertex v if and only if v is the...
The Maximum K-Dependent and F-Dependent Set Problem (1993)
Anders Dessmark, Klaus Jansen, Andrzej Lingas
this paper we analyze both problems for bipartite graphs, split graphs, cographs, trees and graphs with bounded treewidth. Among others, we show that the decision version of the maximum k-dependent...
Maintaining Discrete Probability Distributions Optimally (1993)
Hagerup, Torben, Mehlhorn, Kurt, Munro, I., Lingas, Andrzej, Karlsson, Rolf, Carlsson, Svante
Optimal Parallel Algorithms for Rectilinear Link Distance Problems (1992)
Andrzej Lingas, Anil Maheshwari, Jörg-Rüdiger Sack
We provide optimal parallel solutions to several link distance problems set in trapezoided rectilinear polygons. All our main parallel algorithms are deterministic and designed to run on the...
Christos Levcopoulos, Andrzej Lingas
Abstract. Let S be a set of n points in the plane. For an arbitrary positive rational r, we construct a planar straight-line graph on S that approximates the complete Euclidean graph on S within the...
Information Disseminating Schemes and Their Fault Tolerance in Hypercubes (1991)
Carlsson, Svante, Igarashi, Yoshihide, Kanai, Kumiko, Lingas, Andrzej, Miura, Kinya, Petersson, Ola
Upper and Lower Bounds for the Dictionary Problem (1988)
Dietzfelbinger, Martin, Mehlhorn, Kurt, Rohnert, H., Karlsson, Rolf, Lingas, Andrzej
Advances in minimum weight triangulation / (1983)
Thesis (doctoral)--Linköping University, 1983.
Faster Algorithms for Subgraph Isomorphism of k-connected Partial k-trees
Anders Dessmark, Andrzej Lingas, Andrzej Proskurowski
The problem of determining whether a k-connected partial k-tree is isomorphic to subgraph of another partial k-tree is shown to be solvable in time O(n k+2 ). The presented time-bounds considerably...
A Simple Randomized Parallel Algorithm for Maximal f-Matchings
Oscar Garrido, Stefan Jarominek, Andrzej Lingas, Wojciech Rytter
We show how to extend the RNC-algorithm for maximal matchings due to Israeli-Itai (presented in [5]) to compute maximal (with respect to set of edges inclusion) f-matchings. Our algorithm works in...