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 problem ... more >>>

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, it is ... more >>>

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

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 consider (randomized) algorithms ... more >>>

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 $\Ot(n^{2+\mu})$ ... more >>>

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 number ... more >>>

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

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 polynomial space approximation algorithms that find ... more >>>

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

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