{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T17:59:35Z","timestamp":1649095175674},"reference-count":22,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Fundamentals"],"published-print":{"date-parts":[[2016]]},"DOI":"10.1587\/transfun.e99.a.1813","type":"journal-article","created":{"date-parts":[[2016,9,30]],"date-time":"2016-09-30T22:21:39Z","timestamp":1475274099000},"page":"1813-1821","source":"Crossref","is-referenced-by-count":0,"title":["On the Three-Dimensional Channel Routing"],"prefix":"10.1587","volume":"E99.A","author":[{"given":"Satoshi","family":"TAYU","sequence":"first","affiliation":[{"name":"Department of Information and Communications Engineering, Tokyo Institute of Technology"}]},{"given":"Toshihiko","family":"TAKAHASHI","sequence":"additional","affiliation":[{"name":"Institute of Science and Technology, Academic Assembly, Niigata University"}]},{"given":"Eita","family":"KOBAYASHI","sequence":"additional","affiliation":[{"name":"Department of Information and Communications Engineering, Tokyo Institute of Technology"}]},{"given":"Shuichi","family":"UENO","sequence":"additional","affiliation":[{"name":"Department of Information and Communications Engineering, Tokyo Institute of Technology"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"[1] N. Alon, \u201cA simple algorithm for edge-coloring bipartite multigraphs,\u201d Inform. Process. Lett., vol.85, no.6, pp.301-302, 2003.","DOI":"10.1016\/S0020-0190(02)00446-5"},{"key":"2","doi-asserted-by":"crossref","unstructured":"[2] J. Baliga, \u201cChips Go Vertical,\u201d IEEE Spectr., vol.41, no.3, pp.43-47, 2004.","DOI":"10.1109\/MSPEC.2004.1270547"},{"key":"3","doi-asserted-by":"crossref","unstructured":"[3] K. Banerjee, S.J. Souri, P. Kapur, and K.C. Saraswat, \u201c3-D ICs: A novel chip design for improving deep-submicrometer interconnect performance and systems-on-chip integration,\u201d Proc. IEEE, vol.89, no.5, pp.602-633, 2001.","DOI":"10.1109\/5.929647"},{"key":"4","doi-asserted-by":"crossref","unstructured":"[4] M.L. Brady, D.J. Brown, and P.J. McGUINESS, \u201cThe three-dimensional channel routing problem,\u201d Algorithmic Aspects of VLSI Layout, Lecture Notes Series on Computing, vol.2, pp.213-244, World Scientific, 1993.","DOI":"10.1142\/9789812794468_0007"},{"key":"5","doi-asserted-by":"crossref","unstructured":"[5] R. Cole and J. Hopcroft, \u201cOn edge coloring bipartite graphs,\u201d SIAM J. Comput., vol.11, no.3, pp.540-546, 1982.","DOI":"10.1137\/0211043"},{"key":"6","doi-asserted-by":"crossref","unstructured":"[6] R. Cole, K. Ost, and S. Schirra, \u201cEdge-coloring bipartite multigraphs in O<\/i>(E<\/i>log D<\/i>) time,\u201d Combinatorica, vol.21, no.1, pp.5-12, 2001.","DOI":"10.1007\/s004930170002"},{"key":"7","doi-asserted-by":"crossref","unstructured":"[7] S. Das, A. Fan, K.-N. Chen, C.S. Tan, N. Checka, and R. Reif, \u201cTechnology, performance, and computer-aided design of three-dimensional integrated circuits,\u201d Proc. 2004 International Symposium on Physical Design, ISPD'04, pp.108-115, 2004.","DOI":"10.1145\/981066.981091"},{"key":"8","doi-asserted-by":"crossref","unstructured":"[8] D. Dolev, K. Karplus, A. Siegel, A. Strong, and J.D. Ullman, \u201cOptimal wiring between rectangles,\u201d Proc. Thirteenth Annual ACM Symposium on Theory of Computing, STOC'81, pp.312-317, 1981.","DOI":"10.1145\/800076.802484"},{"key":"9","doi-asserted-by":"crossref","unstructured":"[9] R.J. Enbody, G. Lynn, and K.H. Tan, \u201cRouting the 3-D chip,\u201d Proc. 28th Conference on ACM\/IEEE Design Automation Conference, DAC'91, pp.132-137, 1991.","DOI":"10.1145\/127601.127644"},{"key":"10","doi-asserted-by":"crossref","unstructured":"[10] D.S. Johnson, \u201cThe NP-completeness column: An ongoing gulde,\u201d J. Algorithm., vol.3, no.4, pp.381-395, 1982.","DOI":"10.1016\/0196-6774(82)90032-3"},{"key":"11","unstructured":"[11] D. K\u00f6nig, \u201cGr\u00e1fok \u00e9s alklmaz\u00e1suk a determinnsok \u00e9s a halmazok elm\u00e9let\u00e9re,\u201d Mathematikai \u00e9s Term\u00e9szettudom\u00e1nyi \u00c9rtes\u00edt\u00f6, vol.34, pp.104-119, 1916."},{"key":"12","unstructured":"[12] S. Loyd, Mathematical Puzzles of Sam Loyd, Dover, New York, 1959."},{"key":"13","unstructured":"[13] R. M\u00f6hring, D. Wagner, and F. Wagner, \u201cVLSI network design,\u201d ch. 8, in Handbooks in Operations Research and Management Science, ed., M.O. Ball, T.L. Magnanti, C.L. Monma, and G.L. Nemhauser, North-Holland, 1995."},{"key":"14","doi-asserted-by":"crossref","unstructured":"[14] S.T. Obenaus and T.H. Szymanski, \u201cGravity: Fast placement for 3-D VLSI,\u201d ACM Trans. Des. Autom. Electron. Syst., vol.8, no.3, pp.298-315, 2003.","DOI":"10.1145\/785411.785413"},{"key":"15","doi-asserted-by":"crossref","unstructured":"[15] D. Ratner and M. Warmuth, \u201cThe (n<\/i>2<\/sup>-1)-puzzle and related relocation problems,\u201d J. Symb. Comput., vol.10, no.2, pp.111-137, 1990.","DOI":"10.1016\/S0747-7171(08)80001-6"},{"key":"16","doi-asserted-by":"crossref","unstructured":"[16] A. Recski and D. Szeszl\u00e9r, \u201cRouting vertex disjoint Steiner-trees in a cubic grid and connections to VLSI,\u201d Discrete Appl. Math., vol.155, no.1, pp.44-52, 2007.","DOI":"10.1016\/j.dam.2006.05.010"},{"key":"17","doi-asserted-by":"crossref","unstructured":"[17] M. Sarrafzadeh, \u201cChannel-routing problem in the knock-knee mode is NP-complete,\u201d IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol.6, no.4, pp.503-506, 1987.","DOI":"10.1109\/TCAD.1987.1270298"},{"key":"18","doi-asserted-by":"crossref","unstructured":"[18] T.G. Szymanski, \u201cDogleg channel routing is NP-complete,\u201d IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol.4, no.1, pp.31-41, 1985.","DOI":"10.1109\/TCAD.1985.1270096"},{"key":"19","doi-asserted-by":"crossref","unstructured":"[19] S. Tayu, P. Hurtig, Y. Horikawa, and S. Ueno, \u201cOn the three-dimensional channel routing,\u201d Proc. 2005 IEEE International Symposium on Circuits and Systems, pp.180-183, 2005.","DOI":"10.1109\/ISCAS.2005.1464554"},{"key":"20","doi-asserted-by":"crossref","unstructured":"[20] S. Tayu and S. Ueno, \u201cThe complexity of three-dimensional channel routing,\u201d Proc. 5th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, pp.279-288, 2007.","DOI":"10.1109\/ISCAS.2007.378297"},{"key":"21","doi-asserted-by":"crossref","unstructured":"[21] S. Tayu and S. Ueno, \u201cOn the complexity of three-dimensional channel routing,\u201d Proc. 2007 IEEE International Symposium on Circuits and Systems, pp.3399-3402, 2007.","DOI":"10.1109\/ISCAS.2007.378297"},{"key":"22","doi-asserted-by":"crossref","unstructured":"[22] C.C. Tong and C.-L. Wu, \u201cRouting in a three-dimensional chip,\u201d IEEE Trans. Comput., vol.44, no.1, pp.106-117, 1995.","DOI":"10.1109\/12.368006"}],"container-title":["IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E99.A\/10\/E99.A_1813\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,14]],"date-time":"2019-09-14T05:07:33Z","timestamp":1568437653000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E99.A\/10\/E99.A_1813\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"references-count":22,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2016]]}},"URL":"https:\/\/doi.org\/10.1587\/transfun.e99.a.1813","relation":{},"ISSN":["0916-8508","1745-1337"],"issn-type":[{"value":"0916-8508","type":"print"},{"value":"1745-1337","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}