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

Citation
Cj. Shi et Ja. Brzozowski, A characterization of signed hypergraphs and its applications to VLSI via minimization and logic synthesis, DISCR APP M, 90(1-3), 1999, pp. 223-243
Citations number
29
Categorie Soggetti
Engineering Mathematics
Volume
90
Issue
1-3
Year of publication
1999
Pages
223 - 243
Database
ISI
SICI code
Abstract
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.