Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Efficient Algorithms:
TR96-022 | 15th March 1996
Martin Sauerhoff, Ingo Wegener, Ralph Werchner

Optimal Ordered Binary Decision Diagrams for Tree-like Circuits

Many Boolean functions have short representations by OBDDs (ordered
binary decision diagrams) if appropriate variable orderings are used.
For tree-like circuits, which may contain EXOR-gates, it is proved
that some depth first traversal leads to an optimal variable ordering.
Moreover, an optimal variable ordering and the resulting OBDD
can ... more >>>

TR02-021 | 11th April 2002
Andreas Jakoby, Maciej Liskiewicz, RĂ¼diger Reischuk

Space Efficient Algorithms for Directed Series-Parallel Graphs

The subclass of directed series-parallel graphs plays an important role in
computer science. Whether a given graph is series-parallel is a
well studied problem in algorithmic graph theory, for which fast sequential and
parallel algorithms have been developed in a sequence of papers.
Also methods are known to solve ... more >>>

ISSN 1433-8092 | Imprint