{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,27]],"date-time":"2024-04-27T19:19:57Z","timestamp":1714245597521},"reference-count":7,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":7223,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1987,1]]},"abstract":"Abstract<\/jats:title>The problem of compacting a programmable logic array is formulated as the following graph problem. Given a red\u2010edge 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\u2010complete 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\u2010case error bound. For a red bipartite graph with given cardinality, we give a tight upper bound on the number of green edges.<\/jats:p>","DOI":"10.1002\/net.3230170103","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T21:50:39Z","timestamp":1178920239000},"page":"19-37","source":"Crossref","is-referenced-by-count":20,"title":["Graph folding and programmable logic array"],"prefix":"10.1002","volume":"17","author":[{"given":"T. C.","family":"Hu","sequence":"first","affiliation":[]},{"given":"Y. S.","family":"Kuo","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Ramsey Theory","author":"Graham R.","year":"1980"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"G. D.Hachtel A. R.Newton andA. L.Sangiovanni\u2010Vincentelli An algorithm for optimal PLA folding. IEEE Trans. CAD Integrated Circuits Systems CAD\u20101 (No. 2 ) (1982) 63\u201377.","DOI":"10.1109\/TCAD.1982.1269996"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"G. D.Hachtel A. R.Newton andA. L.Sangiovanni\u2010Vincentelli Techniques for programmable logic array folding. Proceedings of 19th Design Automation Conference (1982)147\u2013155.","DOI":"10.1109\/DAC.1982.1585494"},{"key":"e_1_2_1_5_2","volume-title":"Graph folding and programmable logic array CS\u2010071","author":"Hu T. C.","year":"1982"},{"key":"e_1_2_1_6_2","unstructured":"M.Luby U.Vazirani V.Vazirani andA. L.Sangiovanni\u2010Vincentelli Some theoretical results on the optimal PLA folding problem. IEEE International Conference on Circuits and Systems (1982)165\u2013170."},{"key":"e_1_2_1_7_2","volume-title":"Introduction to VLSI Systems","author":"Mead C.","year":"1980"},{"key":"e_1_2_1_8_2","volume-title":"VLSI System Design","author":"Muroga S.","year":"1982"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230170103","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230170103","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T12:22:55Z","timestamp":1697890975000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230170103"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,1]]},"references-count":7,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1987,1]]}},"alternative-id":["10.1002\/net.3230170103"],"URL":"https:\/\/doi.org\/10.1002\/net.3230170103","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,1]]}}}