## SEARCH

#### Keywords

Time complexity Matrix multiplication Randomized algorithms Approximation algorithms Boolean vector convolution Computational geometry Geometric networks Geometric optimization Matrix product verification Network design Phylogenetic tree Semi-disjoint bilinear form Survivable network design k-connectivity 1-shot protocols#### Country

##### ( see all 18)

- Sweden 101 (%)
- Germany 15 (%)
- United Kingdom 15 (%)
- United States 14 (%)
- Japan 12 (%)

#### Institution

##### ( see all 72)

- Lund University 87 (%)
- Linköping University 10 (%)
- University of Liverpool 10 (%)
- Warsaw University 7 (%)
- Kyoto University 6 (%)

#### Author

##### ( see all 91)

- Lingas, Andrzej [x] 106 (%)
- Levcopoulos, Christos 18 (%)
- Czumaj, Artur 11 (%)
- Jansson, Jesper 11 (%)
- Dessmark, Anders 9 (%)

#### Publication

##### ( see all 54)

- Algorithms and Computation 10 (%)
- Automata, Languages and Programming 10 (%)
- Algorithmica 9 (%)
- Algorithms and Data Structures 6 (%)
- Combinatorial Pattern Matching 6 (%)

#### Subject

##### ( see all 61)

- Computer Science [x] 106 (%)
- Algorithm Analysis and Problem Complexity 80 (%)
- Theory of Computation 55 (%)
- Computation by Abstract Devices 33 (%)
- Discrete Mathematics in Computer Science 32 (%)

## CURRENTLY DISPLAYING:

Most articles

Fewest articles

Showing 1 to 10 of 106 matching Articles
Results per page:

## 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-01-01): 7147 , January 01, 2012

We consider the problem of computing all-pairs shortest paths in a directed graph with non-negative real weights assigned to vertices.

For an *n*×*n* 0 − 1 matrix *C*, let *K*_{C} be the complete weighted graph on the rows of *C* where the weight of an edge between two rows is equal to their Hamming distance. Let *MWT*(*C*) be the weight of a minimum weight spanning tree of *K*_{C}.

We show that the all-pairs shortest path problem for a directed graph *G* on *n* vertices with non-negative real weights and adjacency matrix *A*_{G} can be solved by a combinatorial randomized algorithm in time
$$\widetilde{O}(n^{2}\sqrt{n + \min\{MWT(A_G), MWT(A_G^t)\}})$$
As a corollary, we conclude that the transitive closure of a directed graph *G* can be computed by a combinatorial randomized algorithm in the aforementioned time.

We also conclude that the all-pairs shortest path problem for vertex-weighted uniform disk graphs induced by point sets of bounded density within a unit square can be solved in time $\widetilde{O}(n^{2.75})$ .

## Improved Approximation Algorithms for Optimization Problems in Graphs with Superlogarithmic Treewidth

### Algorithms and Computation (2003-01-01) 2906: 544-553 , January 01, 2003

In this paper we present two novel generic schemes for approximation algorithms for optimization
-hard graph problems constrained to partial *k*-trees. Our first scheme yields *deterministic polynomial-time algorithms* achieving typically an approximation factor of
, where *k* = polylog (*n*). The second scheme yields *randomized polynomial-time algorithms* achieving an approximation factor of
for
. Both our approximation methods lead to the best known approximation guarantees for some basic optimization problems. In particular, we obtain best known polynomial-time approximation guarantees for the classical *maximum independent set* problem in partial trees.

## Fast Approximation Schemes for Euclidean Multi-connectivity Problems

### Automata, Languages and Programming (2000-01-01) 1853: 856-868 , January 01, 2000

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 schemes either significantly improves the previously known upper time-bound or is the first PTAS for the considered problem.

We provide a randomized approximation scheme for finding a biconnected graph spanning a set of points in a multi-dimensional Euclidean space and having the expected total cost within (1 + ε) of the optimum. For any constant dimension and ε, our scheme runs in time *O(n* log *n*). It can be turned into Las Vegas one without affecting its asymptotic time complexity, and also efficiently derandomized. The only previously known truly polynomial-time approximation (randomized) scheme for this problem runs in expected time *n*·*(logn)*^{O}^{((loglogn)}^{9)} in the simplest planar case. The efficiency of our scheme relies on transformations of nearly optimal low cost special spanners into sub-multigraphs having good decomposition and approximation properties and a simple subgraph connectivity characterization. By using merely the spanner transformations, we obtain a very fast polynomial-time approximation scheme for finding a minimum-cost *k*-edge connected multigraph spanning a set of points in a multi-dimensional Euclidean space. For any constant dimension, ε, and *k*, this PTAS runs in time *O*(*n* log*n*). Furthermore, by showing a low-cost transformation of a *k*-edge connected graph maintaining the *k*-edge connectivity and developing novel decomposition properties, we derive a PTAS for Euclidean minimum-cost *k*-edge connectivity. It is substantially faster than that previously known.

Finally, by extending our techniques, we obtain the first PTAS for the problem of Euclidean minimum-cost Steiner biconnectivity. This scheme runs in time *O*(n log *n*) for any constant dimension and ε. As a byproduct, we get the first known non-trivial upper bound on the number of Steiner points in an optimal solution to an instance of Euclidean minimum-cost Steiner biconnectivity.

## Minimum k-Connected Geometric Networks

### Encyclopedia of Algorithms (2008-01-01): 1-6 , January 01, 2008

## On the power of nonconservative PRAM

### Mathematical Foundations of Computer Science 1996 (1996-01-01) 1113: 303-311 , January 01, 1996

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.

## Maximum tree-packing in time O(n5/2)

### Computing and Combinatorics (1995-01-01) 959: 121-130 , January 01, 1995

The problem of determining the maximum number of node-disjoint subtrees of a tree *T* on *n*_{t} nodes isomorphic to a tree *S* on *n*_{s} nodes is shown to be solvable in time *O*(n
_{s}^{3/2}
n_{t}). The same asymptotic bounds are observed for the corresponding problems where topological imbedding and subgraph homeomorphism are respectively substituted for subgraph isomorphism.

## A polynomial-time algorithm for subgraph isomorphism of two-connected series-parallel graphs

### Automata, Languages and Programming (1988-01-01) 317: 394-409 , January 01, 1988

We present the first polynomial-time algorithm for the problem of subgraph isomorphism for two-connected series-parallel graphs, using a new decomposition technique. We also show that this problem is in random NC, and that it is in NC if the input graphs are of bounded valence.

## An application of maximum bipartite c-matching to subtree isomorphism'

### CAAP'83 (1983-01-01) 159: 284-299 , January 01, 1983

## A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication

### Algorithms - ESA 2009 (2009-01-01) 5757: 408-419 , January 01, 2009

We use randomness to exploit the potential sparsity of the Boolean matrix product in order to speed up the computation of the product. Our new fast output-sensitive algorithm for Boolean matrix product and its witnesses is randomized and provides the Boolean product and its witnesses almost certainly. Its worst-case time performance is expressed in terms of the input size and the number of non-zero entries of the product matrix. It runs in time
$\widetilde{O}(n^2s^{\omega/2 - 1}),$
where the input matrices have size *n*×*n*, the number of non-zero entries in the product matrix is at most *s*, *ω* is the exponent of the fast matrix multiplication and
$\widetilde{O}(f(n))$
denotes *O*(*f*(*n*)log^{d}*n*) for some constant *d*. By the currently best bound on *ω*, its running time can be also expressed as
$\widetilde{O}(n^2s^{0.188})$
. Our algorithm is substantially faster than the output-sensitive column-row method for Boolean matrix product for *s* larger than *n*^{1.232} and it is never slower than the fast
$\widetilde{O}(n^{\omega})$
-time algorithm for this problem.

We also present a partial derandomization of our algorithm as well as its generalization to include the Boolean product of rectangular Boolean matrices. Finally, we show several applications of our output-sensitive algorithms.

## A simple randomized parallel algorithm for maximal f-matchings

### LATIN '92 (1992-01-01) 583: 165-176 , January 01, 1992

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
$$\mathcal{O}$$
(log^{2}*n*) time on an arbitrary *Crcw Pram* with a linear number of processors. Also we slightly improve a constant coefficient in the analysis of the Israeli-Itai algorithm. Finally we present more efficient NC algorithms for maximal *f*-matchings for several non-trivial graph classes and a faster RNC algorithm for approximate-maximal *f*-matching in general graphs.