Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SHIRLEY HALEVY:
All reports by Author Shirley Halevy:

TR07-054 | 25th May 2007
Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur

Testing Properties of Constraint-Graphs

We study a model of graph related formulae that we call
the \emph{Constraint-Graph model}. A
constraint-graph is a labeled multi-graph (a graph where loops
and parallel edges are allowed), where each edge $e$ is labeled
by a distinct Boolean variable and every vertex is
associate with a Boolean function over ... more >>>


TR05-153 | 9th December 2005
Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur

Testing Orientation Properties

We propose a new model for studying graph related problems
that we call the \emph{orientation model}. In this model, an undirected
graph $G$ is fixed, and the input is any possible edge orientation
of $G$. A property is now a property of the directed graph that is
obtained by a ... more >>>




ISSN 1433-8092 | Imprint