Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Robert Albin Legenstein:

TR01-076 | 24th October 2001
Robert Albin Legenstein

On the Complexity of Knock-knee Channel-Routing with 3-Terminal Nets

In this article we consider a basic problem in the layout of
VLSI-circuits, the channel-routing problem in the knock-knee mode.
We show that knock-knee channel routing with 3-terminal nets is
NP-complete and thereby settling a problem that was open for more
than a decade. In 1987, Sarrafzadeh showed that knock-knee ... more >>>

TR01-071 | 24th October 2001
Robert Albin Legenstein

Neural Circuits for Pattern Recognition with Small Total Wire Length

One of the most basic pattern recognition problems is whether a
certain local feature occurs in some linear array to the left of
some other local feature. We construct in this article circuits that
solve this problem with an asymptotically optimal number of
threshold gates. Furthermore it is shown that ... more >>>

TR01-070 | 24th October 2001
Robert Albin Legenstein

Total Wire Length as a Salient Circuit Complexity Measure for Sensory Processing

We introduce em total wire length as salient complexity measure
for analyzing the circuit complexity of sensory processing in
biological neural systems and neuromorphic engineering. The new
complexity measure is applied in this paper to two basic
computational problems that arise in translation- and
scale-invariant pattern recognition, and hence appear ... more >>>

TR01-069 | 24th October 2001
Robert Albin Legenstein

Optimizing the Layout of a Balanced Tree

Revisions: 1

It is shown that the total wire length of layouts of a
balanced binary tree on a 2-dimensional grid can be reduced by 33%
if one does not choose the obvious ``symmetric'' layout strategy.
Furthermore it is shown that the more efficient layout strategy that
is presented in this article ... more >>>

ISSN 1433-8092 | Imprint