Uri Zwick, Michael S. Paterson

We study the complexity of finding the values and optimal strategies of

MEAN PAYOFF GAMES on graphs, a family of perfect information games

introduced by Ehrenfeucht and Mycielski and considered by Gurvich,

Karzanov and Khachiyan. We describe a pseudo-polynomial time algorithm

for the solution of such games, the decision ...
more >>>

Oded Goldreich, Dana Ron

In this paper, we consider the question of determining whether

a function $f$ has property $P$ or is $\e$-far from any

function with property $P$.

The property testing algorithm is given a sample of the value

of $f$ on instances drawn according to some distribution.

In some cases,

more >>>

Dorit Dor, Shay Halperin, Uri Zwick

Let G=(V,E) be an unweighted undirected graph on n vertices. A simple

argument shows that computing all distances in G with an additive

one-sided error of at most 1 is as hard as Boolean matrix

multiplication. Building on recent work of Aingworth, Chekuri and

Motwani, we describe an \tilde{O}(min{n^{3/2}m^{1/2},n^{7/3}) time

more >>>

Oded Goldreich

We consider the question of determining whether

a given object has a predetermined property or is ``far'' from any

object having the property.

Specifically, objects are modeled by functions,

and distance between functions is measured as the fraction

of the domain on which the functions differ.

We ...
more >>>

Uri Zwick

We present two new algorithms for solving the {\em All

Pairs Shortest Paths\/} (APSP) problem for weighted directed

graphs. Both algorithms use fast matrix multiplication algorithms.

The first algorithm

solves the APSP problem for weighted directed graphs in which the edge

weights are integers of small absolute value in ...
more >>>

Oded Goldreich, Dana Ron

Following Feige, we consider the problem of

estimating the average degree of a graph.

Using ``neighbor queries'' as well as ``degree queries'',

we show that the average degree can be approximated

arbitrarily well in sublinear time, unless the graph is extremely sparse

(e.g., unless the graph has a sublinear ...
more >>>

Andrzej Lingas, Martin Wahlén

We consider the ``minor'' and ``homeomorphic'' analogues of the maximum clique problem, i.e., the problems of determining the largest $h$ such that the input graph has a minor isomorphic to $K_h$ or a subgraph homeomorphic to $K_h,$ respectively.We show the former to be approximable within $O(\sqrt {n} \log^{1.5} n)$ by ... more >>>

Andreas Björklund, Thore Husfeldt

We present a deterministic algorithm producing the number of

$k$-colourings of a graph on $n$ vertices in time

$2^nn^{O(1)}$.

We also show that the chromatic number can be found by a

polynomial space algorithm running in time $O(2.2461^n)$.

Finally, we present a family of ...
more >>>

Eldar Fischer, Orly Yahalom

A coloring of a graph is {\it convex} if it

induces a partition of the vertices into connected subgraphs.

Besides being an interesting property from a theoretical point of

view, tests for convexity have applications in various areas

involving large graphs. Our results concern the important subcase

of testing for ...
more >>>

Satyen Kale, C. Seshadhri

We consider the problem of testing graph expansion in the bounded degree model. We give a property tester that given a graph with degree bound $d$, an expansion bound $\alpha$, and a parameter $\epsilon > 0$, accepts the graph with high probability if its expansion is more than $\alpha$, and ... more >>>

Oded Goldreich

Prior studies of testing graph properties presume that the tester can obtain uniformly distributed vertices in the tested graph (in addition to obtaining answers to the some type of graph-queries).

Here we envision settings in which it is only feasible to obtain random vertices drawn according to an arbitrary distribution ...
more >>>