Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR98-003 | 3rd November 1997
I. Cahit, M. Tezer

Irregular Assignments of the Forest of Paths

An irregular assignement of $G$ is labelling $f: E \ra
\{1,2,...,m\}$ of the
edge-set of $G$ such that all of the induced vertex labels computed as
$\sigma_{v\in e}f(e)$ are distinct. The minimal number $m$ for which this
is possible is called the minimal irregularity strength $s_{m}(G)$ of $G$.
The ... more >>>


TR98-002 | 8th January 1998
Jayram S. Thathachar

On Separating the Read-k-Times Branching Program Hierarchy

We obtain an exponential separation between consecutive
levels in the hierarchy of classes of functions computable by
polynomial-size syntactic read-$k$-times branching programs, for
{\em all\/} $k>0$, as conjectured by various
authors~\cite{weg87,ss93,pon95b}. For every $k$, we exhibit two
explicit functions that can be computed by linear-sized
read-$(\kpluso)$-times branching programs but ... more >>>


TR98-001 | 17th December 1997
Detlef Sieling

On the Existence of Polynomial Time Approximation Schemes for OBDD Minimization

Revisions: 1

The size of Ordered Binary Decision Diagrams (OBDDs) is
determined by the chosen variable ordering. A poor choice may cause an
OBDD to be too large to fit into the available memory. The decision
variant of the variable ordering problem is known to be
NP-complete. We strengthen this result by ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint