{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:58:25Z","timestamp":1725663505061},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540520481"},{"type":"electronic","value":"9783540468721"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-52048-1_50","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:19:45Z","timestamp":1330204785000},"page":"280-290","source":"Crossref","is-referenced-by-count":1,"title":["Gate matrix layout revisited: Algorithmic performance and probabilistic analysis"],"prefix":"10.1007","author":[{"given":"Sajal K.","family":"Das","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Narsingh","family":"Deo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sushil","family":"Prasad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. S. Booth","year":"1976","unstructured":"Booth, K. S. and G. S. Leuker, \u201cTesting for the Consecutive Ones Property, Interval Graphs and Graph Planarity Using PQ-Tree Algorithms,\u201d J. Comput. Syst. Sci., Vol. 13, pp. 335\u201379, 1976.","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"23_CR2","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1109\/TCAD.1987.1270248","volume":"CAD-6","author":"N. Deo","year":"1987","unstructured":"Deo, N., M. S. Krishnamoorthy, and M. A. Langston, \u201cExact and Approximate Solutions for the Gate Matrix Layout Problem,\u201d IEEE Trans. Computer-Aided Design, Vol. CAD-6, No. 1, pp. 79\u201384, Jan. 1987.","journal-title":"IEEE Trans. Computer-Aided Design"},{"key":"23_CR3","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R. and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., San Francisco, California, 1979."},{"key":"23_CR4","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. C. Golumbic","year":"1976","unstructured":"Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1976."},{"key":"23_CR5","volume-title":"Fundamentals of Computer Algorithms","author":"H. E","year":"1978","unstructured":"Horowitz, E. and S. Sahni, Fundamentals of Computer Algorithms, Computer Science Press, Rockville, Maryland, 1978."},{"key":"23_CR6","unstructured":"Kashiwabara, T. and T. Fujisawa, \u201cAn NP-Complete Problem on Interval Graph,\u201d Proc. IEEE Int. Symp. Circuits and Systems, pp. 82\u201383, 1979."},{"key":"23_CR7","unstructured":"Leong, H. W., \u201cA New Algorithm for Gate Matrix Layout,\u201d Proc. IEEE Int. Conf. Computer-Aided Design, Nov. 1986."},{"key":"23_CR8","unstructured":"Li, J. T., \u201cAlgorithms for Gate Matrix Layout,\u201d Proc. IEEE Int. Symp. Circuits and Systems, pp. 1013\u201316, 1983."},{"key":"23_CR9","unstructured":"Lopez, A. D. and H. F. S. Law, \u201cA Dense Gate Matrix Layout Method for MOS VLSI,\u201d IEEE Trans. Electron Devices, pp. 1671\u201375, Aug. 1980."},{"issue":"9","key":"23_CR10","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1109\/TCS.1979.1084695","volume":"CAS-26","author":"T. Ohtsuki","year":"1979","unstructured":"Ohtsuki, T., H. Mori, E. S. Kuh, T. Kashiwabara, and T. Fujisawa, \u201cOne-Dimensional Logic Gate Assignment and Interval Graphs,\u201d IEEE Trans. Circuits and Systems, Vol CAS-26, No. 9, pp. 675\u201384, Sept. 1979.","journal-title":"IEEE Trans. Circuits and Systems"},{"key":"23_CR11","doi-asserted-by":"crossref","unstructured":"Ohtsuki, T., H. Mori, T. Kashiwabara, and T. Fujisawa, \u201cOn Minimal Augmentation to a Graph to Obtain an Interval Graph,\u201d J. Comput. Syst. Sci., pp. 60\u201397, Feb. 1981.","DOI":"10.1016\/0022-0000(81)90022-2"},{"key":"23_CR12","volume-title":"Gate Matrix Layout: Expected-Case Analysis and Performance of Algorithms","author":"S. Prasad","year":"1986","unstructured":"Prasad, S., Gate Matrix Layout: Expected-Case Analysis and Performance of Algorithms, M. S. Thesis, Dept. Comput. Sci., Washington State Univ., Pullman, WA, Aug. 1986."},{"key":"23_CR13","volume-title":"Combinatorial Algorithms: Theory and Practice","author":"E. M. Reingold","year":"1977","unstructured":"Reingold, E. M., J. Nievergelt, and N. Deo, Combinatorial Algorithms: Theory and Practice, Prentice-Hall, Englewood Cliffs, New Jersey, 1977."},{"key":"23_CR14","unstructured":"Wing, O., \u201cAutomated Gate Matrix Layout,\u201d Proc. IEEE Int. Symp. Circuits and Systems, Rome, Italy, pp. 681\u201385, 1982."},{"key":"23_CR15","unstructured":"Wing, O., \u201cInterval-Graph-Based Circuit Layout,\u201d Proc. IEEE Int. Conf. Computer-Aided Design, pp. 84\u201385, 1983."},{"issue":"3","key":"23_CR16","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1109\/TCAD.1985.1270118","volume":"CAD-4","author":"O. Wing","year":"1985","unstructured":"Wing, O., S. Huang, and R. Wang, \u201cGate Matrix Layout,\u201d IEEE Trans. Computer-Aided Design, Vol. CAD-4, No. 3, pp. 220\u201331, July 1985.","journal-title":"IEEE Trans. Computer-Aided Design"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-52048-1_50.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:06:27Z","timestamp":1619571987000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-52048-1_50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540520481","9783540468721"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-52048-1_50","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}