A characterization of signed hypergraphs and its applications to VLSI via minimization and logic synthesis

A recently introduced graph-theoretic notion of signed hypergraph is studie d. In particular, a structural characterization of balanced signed hypergra phs is given, and two optimization problems related to the balance property - the maximum balance and the minimum covering problems - are introduced a nd characterized. It is shown that both problems are NP-complete in general . Applications of the theory of signed hypergraphs to two VLSI optimization problems, namely via minimization and constrained logic encoding, are desc ribed. (C) 1999 Elsevier Science B.V. All rights reserved.