Graph folding and programmable logic array
作者:
T. C. Hu,
Y. S. Kuo,
期刊:
Networks
(WILEY Available online 1987)
卷期:
Volume 17,
issue 1
页码: 19-37
ISSN:0028-3045
年代: 1987
DOI:10.1002/net.3230170103
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractThe problem of compacting a programmable logic array is formulated as the following graph problem. Given a red‐edge bipartite graph, how to add maximum number of independent green edges such that there are no cycles formed by alternating red and green edges. For this NP‐complete problem, we present a polynomial heuristic algorithm which gives an optimum solution when the red bipartite graph satisfies certain conditions, e.g., a tree. When the bipartite graph does not satisfy these conditions, the heuristic algorithm gives a solution with worst‐case error bound. For a red bipartite graph with given cardinality, we give a tight upper bound on the number of green
点击下载:
PDF
(735KB)
返 回