## SEARCH

#### Institution

- Lund University 5 (%)
- Kyoto University 2 (%)
- Malmö University 1 (%)
- University of Bonn 1 (%)

#### Author

##### ( see all 7)

- Lingas, Andrzej 5 (%)
- Sledneu, Dzmitry [x] 5 (%)
- Floderus, Peter 2 (%)
- Jansson, Jesper 2 (%)
- Levcopoulos, Christos 2 (%)

#### Publication

## CURRENTLY DISPLAYING:

Most articles

Fewest articles

# Search Results

Showing 1 to 5 of 5 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})$ .

## 3D Rectangulations and Geometric Matrix Multiplication

### Algorithms and Computation (2014-01-01): 8889 , January 01, 2014

The problem of partitioning an input rectilinear polyhedron $$P$$ into a minimum number of 3D rectangles is known to be NP-hard. We first develop a $$4$$ -approximation algorithm for the special case in which $$P$$ is a 3D histogram. It runs in $$O(m \log m)$$ time, where $$m$$ is the number of corners in $$P$$ . We then apply it to compute the arithmetic matrix product of two $$n \times n$$ matrices $$A$$ and $$B$$ with nonnegative integer entries, yielding a method for computing $$A \times B$$ in $$\tilde{O}(n^2+ \min \{ r_Ar_B, n\min \{r_A,\ r_B\}\})$$ time, where $$\tilde{O}$$ suppresses polylogarithmic (in $$n$$ ) factors and where $$r_A$$ and $$r_B$$ denote the minimum number of 3D rectangles into which the 3D histograms induced by $$A$$ and $$B$$ can be partitioned, respectively.

## A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set

### Automata, Languages, and Programming (2015-01-01): 9134 , January 01, 2015

The number of triangulations of a planar *n* point set *S* is known to be
$$c^n$$
, where the base *c* lies between 2.43 and 30. Similarly, the number of spanning trees on *S* is known to be
$$d^n$$
, where the base *d* lies between 6.75 and 141.07. The fastest known algorithm for counting triangulations of *S* runs in
$$O^*(2^n)$$
time while that for counting spanning trees runs in
$$O^*(7.125^n)$$
time. The fastest known arbitrarily close approximation algorithms for the base of the number of triangulations of *S* and the base of the number of spanning trees of *S*, respectively, run in time subexponential in *n*. We present the first quasi-polynomial approximation schemes for the base of the number of triangulations of *S* and the base of the number of spanning trees on *S*, respectively.

## 3D Rectangulations and Geometric Matrix Multiplication

### Algorithmica (2016-11-16): 1-19 , November 16, 2016

The problem of partitioning an orthogonal polyhedron *P* into a minimum number of 3D rectangles is known to be NP-hard. In this paper, we first develop a 4-approximation algorithm for the special case of the problem in which *P* is a *3D histogram*. It runs in
$$O(m \log m)$$
time, where *m* is the number of corners in *P*. We then apply it to exactly compute the arithmetic matrix product of two
$$n \times n$$
matrices *A* and *B* with nonnegative integer entries, yielding a method for computing
$$A \times B$$
in
$$\tilde{O}(n^2 + \min \{ r_A r_B,\, n \min \{r_A,\ r_B\}\})$$
time, where
$$\tilde{O}$$
suppresses polylogarithmic (in *n*) factors and where
$$r_A$$
and
$$r_B$$
denote the minimum number of 3D rectangles into which the 3D histograms induced by *A* and *B* can be partitioned, respectively.

## Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model

### Theory and Applications of Models of Computation (2017-01-01): 10185 , January 01, 2017

We study the complexity of the so called semi-disjoint bilinear forms over different semi-rings, in particular the *n*-dimensional vector convolution and
$$n\times n$$
matrix product. We consider a powerful unit-cost computational model over the ring of integers allowing for several additional operations and generation of large integers. We show the following dichotomy for such a powerful model: while almost all arithmetic semi-disjoint bilinear forms have the same asymptotic time complexity as that yielded by naive algorithms, matrix multiplication, the so called distance matrix product, and vector convolution can be solved in a linear number of steps. It follows in particular that in order to obtain a non-trivial lower bounds for these three basic problems one has to assume restrictions on the set of allowed operations and/or the size of used integers.