Publications of Claudio Arbib

This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  ALL, with author Arbib C., in the category IASI Research Reports (or show them all):


IASI Research Report n. 284  


Arbib C., Lucertini M., Sara Nicoloso

Polynomial and NP-complete problems in programmed logic arrays folding.

ABSTRACT
Combinatorial optimization models for the problem of reducing the physical area of Programmed Logic Arrays (PLA) by folding are here considered. We define the representative hypergraph of the PLA as the hypergraph having the PLA topological matrix as its incidency matrix; the incompatibility graph of the PLA, as the intersection graph of its representative hypergraph; and the compatibility graph, as the complement of the incompatibility graph. We give a survey of some complexity results on variable-folding and block-folding problems. Among the original results, we prove that block-folding is NP-hard on PLA having a regular graph as representative hypergraph (in particular, on PLA having an edge-graph as incompatibility graph). On the other hand, we give polynomial algorithms for both block- and variable-folding problems on PLA whose compatibility graph does not contain a claw, a (K_5 - e) or a subdivided K_4 as induced subgraph (in particular, on PLA having an edge-graph as compatibility graph).
back
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -