All reports by Author Artur Czumaj:

__
TR12-035
| 5th April 2012
__

Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler#### Finding Cycles and Trees in Sublinear Time

Revisions: 1
,
Comments: 1

__
TR07-083
| 23rd August 2007
__

Artur Czumaj, Asaf Shapira, Christian Sohler#### Testing Hereditary Properties of Non-Expanding Bounded-Degree Graphs

__
TR06-115
| 26th July 2006
__

Artur Czumaj, Andrzej Lingas#### Finding a Heaviest Triangle is not Harder than Matrix Multiplication

__
TR06-111
| 18th July 2006
__

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

Revisions: 2

Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler

(This is a revised version of work that was posted on arXiv in July 2010.)

We present sublinear-time (randomized) algorithms for finding simple cycles of length at least $k\geq3$ and tree-minors in bounded-degree graphs.

The complexity of these algorithms is related to the distance

of the graph from being ...
more >>>

Artur Czumaj, Asaf Shapira, Christian Sohler

We study property testing in the model of bounded degree graphs. It

is well known that in this model many graph properties cannot be

tested with a constant number of queries and it seems reasonable to

conjecture that only few are testable with o(sqrt{n}) queries.

Therefore in this paper ...
more >>>

Artur Czumaj, Andrzej Lingas

We show that for any $\epsilon > 0$, a maximum-weight triangle in an

undirected graph with $n$ vertices and real weights assigned to

vertices can be found in time $\O(n^{\omega} + n^{2 + \epsilon})$,

where $\omega $ is the exponent of fastest matrix multiplication

algorithm. By the currently best bound ...
more >>>

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