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