Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Graph Algorithms:
TR95-040 | 26th July 1995
Uri Zwick, Michael S. Paterson

The complexity of mean payoff games on graphs

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

TR96-057 | 18th November 1996
Oded Goldreich, Dana Ron

Property Testing and its connection to Learning and Approximation

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

TR97-040 | 17th September 1997
Dorit Dor, Shay Halperin, Uri Zwick

All Pairs Almost Shortest Paths

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

TR97-056 | 1st December 1997
Oded Goldreich

Combinatorial Property Testing (a survey).

Comments: 1

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

TR00-060 | 17th August 2000
Uri Zwick

All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication

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

TR04-013 | 10th February 2004
Oded Goldreich, Dana Ron

On Estimating the Average Degree of a Graph.

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

TR04-039 | 21st April 2004
Andrzej Lingas, Martin Wahlén

On approximation of the maximum clique minor containment problem and some subgraph homeomorphism problems

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

TR06-044 | 24th January 2006
Andreas Björklund, Thore Husfeldt

Inclusion-Exclusion Based Algorithms for Graph Colouring

We present a deterministic algorithm producing the number of
$k$-colourings of a graph on $n$ vertices in time
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 >>>

TR06-053 | 6th April 2006
Eldar Fischer, Orly Yahalom

Testing Convexity Properties of Tree Colorings

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

TR07-076 | 25th July 2007
Satyen Kale, C. Seshadhri

Testing Expansion in Bounded Degree Graphs

Revisions: 1

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

TR18-171 | 10th October 2018
Oded Goldreich

Testing Graphs in Vertex-Distribution-Free Models

Revisions: 1

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

TR21-034 | 9th March 2021
Oded Goldreich

Robust Self-Ordering versus Local Self-Ordering

We study two notions that refers to asymmetric graphs, which we view as graphs having a unique ordering that can be reconstructed by looking at an unlabeled version of the graph.

A {\em local self-ordering} procedure for a graph $G$ is given oracle access to an arbitrary isomorphic copy of ... more >>>

ISSN 1433-8092 | Imprint