Arrow Research search

Author name cluster

Andrzej Lingas

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

26 papers
2 author rows

Possible papers

26

SODA Conference 2011 Conference Paper

Counting and detecting small subgraphs via equations and matrix multiplication

  • Miroslaw Kowaluk
  • Andrzej Lingas
  • Eva-Marta Lundell

We present a general technique for detecting and counting small subgraphs. It consists in forming special linear combinations of the numbers of occurrences of different induced subgraphs of fixed size in a graph. The combinations can be efficiently computed by rectangular matrix multiplication. Our two main results utilizing the technique are as follows. Let H be a fixed graph with k vertices and an independent set of size s. 1. Detecting if an n -vertex graph contains a (non-necessarily induced) subgraph isomorphic to H can be done in time, where ω( p, q, r ) is the exponent of fast arithmetic matrix multiplication of an n p × n q matrix by an n q × n r matrix. 2. When s = 2, counting the number of (non-necessarily induced) subgraphs isomorphic to H can be done in the same time, i. e. , in time. (This improves for s = 2 on a counting algorithm of Vassilevska and Williams, running in time O ( n k–s +3 ).) It follows in particular that we can count the number of subgraphs isomorphic to any H on four vertices that is not K 4 in time O ( n ω ), where ω = ω(1, 1, 1) is known to be smaller than 2. 376. Similarly, we can count the number of subgraphs isomorphic to any H on five vertices that is not K 5 in time O ( n ω (2, 1, 1 )), where ω(2, 1, 1) is known to be smaller than 3. 334.

Details

MFCS Conference 1996 Conference Paper

On the Power of Nonconservative PRAM

  • Anders Dessmark
  • Andrzej Lingas

Abstract An alternative simple method of exploiting word parallelism in a nonconservative RAM and PRAM model is considered. In effect, improved bounds for parallel integer sorting in the nonconservative and conservative EREW PRAM models are obtained.

Details

MFCS Conference 1994 Conference Paper

On Parallel Complexity of Maximum f-matching and the Degree Sequence Problem

  • Anders Dessmark
  • Andrzej Lingas
  • Oscar Garrido

Abstract We present a randomized NC solution to the problem of constructing a maximum (cardinality) f -matching. As a corollary, we obtain a randomized NC algorithm for the problem of constructing a graph satisfying a sequence d 1, d 2, .. ., d n of equality degree constraints. We provide an optimal NC algorithm for the decision version of the degree sequence problem and an approximation NC algorithm for the construction version of this problem. Our main result is an NC algorithm for constructing if possible a graph satisfying the degree constraints d 1, d 2, .. ., d n in case d i ≤ \(\sqrt {\Sigma _{j = 1}^n d_j /5 }\) for i =1, .. ., n.

Details