{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:52Z","timestamp":1725663292065},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540171799"},{"type":"electronic","value":"9783540472391"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-17179-7_10","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T14:07:45Z","timestamp":1330178865000},"page":"154-176","source":"Crossref","is-referenced-by-count":2,"title":["Via assignment in single row routing"],"prefix":"10.1007","author":[{"given":"Jayaram","family":"Bhasker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sartaj","family":"Sahni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Bondy J. and U.S.R.Murthy, Graph Theory with Applications, Elsevier North Holland Inc, 1976.","DOI":"10.1007\/978-1-349-03521-2"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Cohoon J. and S.Sahni, Heuristics for the Board Permutation Problem, Proc. 1983 IEEE ICCAD Conf.","DOI":"10.1109\/DAC.1983.1585709"},{"key":"10_CR3","series-title":"Research notes in Mathematics","volume-title":"Edge-Coloring of Graphs","author":"S. Fiorini","year":"1977","unstructured":"Fiorini S. and R.J. Wilson, Edge-Coloring of Graphs, Research notes in Mathematics, 16, Pitman, London, 1977."},{"key":"10_CR4","volume-title":"Computer and Intractibility: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey M.R. and D.S. Johnson, Computer and Intractibility: A Guide to the Theory of NP-Completeness, W.H.Freeman, San Francisco, 1979."},{"key":"10_CR5","unstructured":"Gonzalez T., An Approximation Algorithm for the Via Assignment Problem, ICCAD, 1983, pp 125\u2013128."},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"Goto S., I.Cederbaum and B.Ting, Suboptimal Solution of the Backboard Ordering with Channel Capacity Constraints, IEEE Trans Circuits and Systems, Nov 1977, pp 645\u2013652.","DOI":"10.1109\/TCS.1977.1084286"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Han S. and S.Sahni, Layering Algorithms for Single Row Routing, University of Minnesota, Technical report, June 1984.","DOI":"10.1145\/317825.317938"},{"key":"10_CR8","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1109\/TCAD.1984.1270080","volume":"3","author":"S. Han","year":"1984","unstructured":"Han S. and S. Sahni, Single Row Routing in Narrow Streets, IEEE Trans CAD, CAD-3, 3, 1984, pp 235\u2013241.","journal-title":"IEEE Trans CAD, CAD-3"},{"key":"10_CR9","unstructured":"Han S. and S.Sahni, A Fast Algorithm for Single Row Routing, University of Minnesota, Technical report, Jan 1984."},{"issue":"4","key":"10_CR10","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I. Holyer","year":"1981","unstructured":"Holyer I., The NP-Completeness of Edge-Coloring, Siam J. Computing, Vol 10, No 4, Nov 1981, pp 718\u2013720.","journal-title":"Siam J. Computing"},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"Hopcroft J. and R.Karp, An n 5\/2 Algorithm for Maximum Matching in Bipartite Graphs, Siam J. Computing, 1973, pp 225\u2013231.","DOI":"10.1137\/0202019"},{"key":"10_CR12","volume-title":"Fundamentals of Computer Algorithms","author":"E. Horowitz","year":"1978","unstructured":"Horowitz E. and S. Sahni, Fundamentals of Computer Algorithms, Computer science press, Potomac, MD, 1978."},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"Kuh E., T.Kashwabara and T.Fujisawa, On Optimal Single Row Routing, IEEE Trans Circuits and Systems, Vol CAS-26, No 6, June 1979.","DOI":"10.1109\/TCS.1979.1084650"},{"issue":"3","key":"10_CR14","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1109\/TC.1983.1676213","volume":"C-32","author":"R. Raghavan","year":"1983","unstructured":"Raghavan R. and S. Sahni, Single Row Routing, IEEE Trans Computers, C-32, 3, 1983, pp 209\u2013220.","journal-title":"IEEE Trans Computers"},{"issue":"5","key":"10_CR15","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1109\/TCS.1984.1085526","volume":"CAS-31","author":"R. Raghavan","year":"1984","unstructured":"Raghavan R. and S. Sahni, The Complexity of Single Row Routing, IEEE Trans Circuits and Systems, CAS-31, 5, 1984, pp 462\u2013472.","journal-title":"IEEE Trans Circuits and Systems"},{"key":"10_CR16","unstructured":"So H.C., Some Theoritical Results on the Routing of Multilayer Printed Wiring Boards, Proc IEEE Symp Circuits and Systems, 1974, pp 296\u2013303."},{"key":"10_CR17","volume-title":"Discrete Optimization Algorithms","author":"M. M. Syslo","year":"1983","unstructured":"Syslo M.M., N. Deo and J.S. Kowalik, Discrete Optimization Algorithms, Prentice Hall Inc, NJ, 1983."},{"issue":"3","key":"10_CR18","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1109\/TCAD.1984.1270073","volume":"CAD-3","author":"T. Tarng","year":"1984","unstructured":"Tarng T., M. Marek-Sadowska and E.S. Kuh, An Efficient Single Row Routing Algorithm, IEEE Trans CAD, CAD-3, 3, 1984, pp 178\u2013183.","journal-title":"IEEE Trans CAD"},{"key":"10_CR19","doi-asserted-by":"crossref","first-page":"768","DOI":"10.1109\/TCS.1976.1084169","volume":"CAS-23","author":"B. Ting","year":"1976","unstructured":"Ting B., E.S. Kuh and I. Shirakawa, The Multilayer Routing Problem: Algorithms and Necessary and Sufficient Conditions for the Single-Row Single-Layer Case, IEEE Trans Circuit and Systems, CAS-23, Dec. 1976, pp 768\u2013778.","journal-title":"IEEE Trans Circuit and Systems"},{"key":"10_CR20","unstructured":"Ting B.S. and E.S.Kuh, An Approach to the Routing of Multilayer Printed Circuit Boards, Proc IEEE Symp Circuits and Systems, 1978, pp 902\u2013911."},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"Ting B.S., E.S.Kuh and A.Sangiovanni-Vincentelli, Via Assignment Problem in Multilayer Printed Circuit Board, IEEE Trans Circuits and Systems, Vol CAS-26, Apr 79, pp 261\u2013271.","DOI":"10.1109\/TCS.1979.1084634"},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"Tsukiyama S., I.Shirakawa and S.Asahara, An Algorithm for the Via Assignment Problem in Multilayer Backboard Wiring, IEEE Trans Circuits and Systems, Vol CAS-26, Jun 79, pp 369\u2013377.","DOI":"10.1109\/TCS.1979.1084651"},{"key":"10_CR23","doi-asserted-by":"crossref","unstructured":"Tsukiyama S., E.S.Kuh and I.Shirakawa, On the Layering Problem of Multilayer PWB Wiring, IEEE Trans CAD, CAD-2, 1, Jan 83, pp 30\u201338.","DOI":"10.1109\/TCAD.1983.1270018"}],"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-17179-7_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:12:19Z","timestamp":1605625939000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-17179-7_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540171799","9783540472391"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-17179-7_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]}}}