Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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 >>>

TR00-051 | 14th July 2000
Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas

Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs and Planar Graphs

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 >>>

ISSN 1433-8092 | Imprint