{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T03:11:31Z","timestamp":1777605091536,"version":"3.51.4"},"reference-count":29,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":5311,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[1999,1]]},"DOI":"10.1016\/s0166-218x(98)00092-4","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T15:07:02Z","timestamp":1027609622000},"page":"223-243","source":"Crossref","is-referenced-by-count":12,"title":["A characterization of signed hypergraphs and its applications to VLSI via minimization and logic synthesis"],"prefix":"10.1016","volume":"90","author":[{"given":"C.-J","family":"Shi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.A","family":"Brzozowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(98)00092-4_BIB1","series-title":"Graphs and Hypergraphs","author":"Berge","year":"1973"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB2","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF01584535","article-title":"Balanced matrices","volume":"2","author":"Berge","year":"1992","journal-title":"Math. Programming"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB3","series-title":"Graph Theory with Applications","author":"Bondy","year":"1976"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB4","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1109\/TCS.1983.1085357","article-title":"A graph-theoretic via minimization algorithm for two-layer printed boards","volume":"30","author":"Chen","year":"1993","journal-title":"IEEE Trans. Circuits Systems"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB5","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1137\/0402004","article-title":"Graph bipartition and via minimization","volume":"2","author":"Choi","year":"1989","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0166-218X(98)00092-4_BIB6","series-title":"Proc. 33rd Ann. IEEE Symp. on Foundations of Computer Science","article-title":"A class of logic problems solvable by linear programming","author":"Conforti","year":"1992"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB7","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/BF02591849","article-title":"Structural properties and recognition of restricted and strongly unimodular matrices","volume":"38","author":"Conforti","year":"1987","journal-title":"Math. Programming"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB8","series-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB9","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","article-title":"Some simplified NP-complete graph problems","author":"Garey","year":"1976","journal-title":"Theoret. Comput. Sci. 1"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB10","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1307\/mmj\/1028989917","article-title":"On the notation of balance of a signed graph","volume":"2","author":"Harary","year":"1953","journal-title":"Michigan Math. J."},{"key":"10.1016\/S0166-218X(98)00092-4_BIB11","series-title":"Proc. 8th Design Automat. Workshop","first-page":"155","article-title":"Wire routing optimizing channel assignment within large apertures","author":"Hashimoto","year":"1971"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB12","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1002\/jgt.3190160104","article-title":"A characterization of consistent marked graphs","volume":"16","author":"Hoede","year":"1992","journal-title":"J. Graph Theory"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB13","series-title":"Integer Programming and Network Flows","author":"Hu","year":"1970"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB14","article-title":"Layer assignment for printed circuit boards and integrated circuits","volume":"80","author":"Joy","year":"1992"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB15","series-title":"Proc. 25th IEEE\/ACM Design Automat. Conf.","first-page":"554","article-title":"Fast algorithm for optimal layer assignment","author":"Kuo","year":"1988"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB16","series-title":"Combinatorial Algorithms for Integrated Circuit Layout","author":"Lengauer","year":"1990"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB17","series-title":"Proc. 4th Ann. Symp. on Theoretical Aspects of Computer Science","first-page":"420","article-title":"On the contact minimization problem","author":"Molitor","year":"1987"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB18","unstructured":"R.Y. Pinter, Optimal layer assignment for interconnect, Proc. IEEE 1982 Circuits Comput. Conf., pp. 398\u2013401."},{"key":"10.1016\/S0166-218X(98)00092-4_BIB19_1","series-title":"Proc. 2nd Great Lakes Symp. on VLSI","first-page":"159","article-title":"A signed hypergraph model of constrained via minimization","author":"Shi","year":"1992"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB19_2","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1016\/0026-2692(92)90064-8","volume":"23","author":"Shi","year":"1992","journal-title":"Microelectron. J."},{"key":"10.1016\/S0166-218X(98)00092-4_BIB20","series-title":"Algorithmic Aspects of VLSI Layouts","first-page":"337","article-title":"Constrained via minimization and signed hypergraph partitioning","author":"Shi","year":"1993"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB21","article-title":"Optimum logic encoding and layout wiring for VLSI design: a graph-theoretic approach","author":"Shi","year":"1993"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB22","doi-asserted-by":"crossref","first-page":"1813","DOI":"10.1109\/43.251145","article-title":"An efficient algorithm for constrained encoding and its applications","volume":"12","author":"Shi","year":"1993","journal-title":"IEEE Trans. Comput. Aided Des."},{"key":"10.1016\/S0166-218X(98)00092-4_BIB23","series-title":"Proc. Canadian Conf. on VLSI","first-page":"2.7.1","article-title":"A hypergraph partitioning approach to the via minimization problem","author":"Shi","year":"1990"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB24","series-title":"IEEE Int. Symp. Circuits Systems","first-page":"689","article-title":"Global via minimization in generalized routing environment","author":"Stevens","year":"1979"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB25","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1016\/0095-8956(82)90028-4","article-title":"Alpha-balanced graphs and matrices and GF (3) -representability of matroids","volume":"32","author":"Truemper","year":"1982","journal-title":"J. Combin. Theory B"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB26","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1109\/31.20197","article-title":"A unified approach to the via minimization problem","volume":"36","author":"Xiong","year":"1989","journal-title":"IEEE Trans. Circuits Systems"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB27","series-title":"Proc. 10th Ann. ACM Symp. on Theory of Computing","first-page":"253","article-title":"Node-and edge-deletion NP-complete problems","author":"Yannakakis","year":"1979"},{"key":"10.1016\/S0166-218X(98)00092-4_BIB28","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1287\/moor.10.2.280","article-title":"On a class of totally unimodular matrices","volume":"10","author":"Yannakakis","year":"1985","journal-title":"Math. Oper. Res."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X98000924?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X98000924?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,22]],"date-time":"2019-04-22T21:50:24Z","timestamp":1555969824000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X98000924"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,1]]},"references-count":29,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1999,1]]}},"alternative-id":["S0166218X98000924"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(98)00092-4","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[1999,1]]}}}