All reports by Author Miroslaw Kowaluk:

__
TR06-111
| 18th July 2006
__

Artur Czumaj, Miroslaw Kowaluk, Andrzej Lingas#### Faster algorithms for finding lowest common ancestors in directed acyclic graphs

Revisions: 2

__
TR00-051
| 14th July 2000
__

Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas#### Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs and Planar Graphs

Artur Czumaj, Miroslaw Kowaluk, Andrzej Lingas

We present two new methods for finding a lowest common ancestor (LCA)

for each pair of vertices of a directed acyclic graph (dag) on

n vertices and m edges.

The first method is a natural approach that solves the all-pairs LCA

problem for the input dag in time O(nm).

The ... more >>>

Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas

The max-bisection problem is to find a partition of the vertices of a

graph into two equal size subsets that maximizes the number of edges with

endpoints in both subsets.

We obtain new improved approximation ratios for the max-bisection problem on

the low degree $k$-regular graphs for ...
more >>>