{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:06:39Z","timestamp":1725494799440},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540662792"},{"type":"electronic","value":"9783540484479"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48447-7_3","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T21:42:14Z","timestamp":1194990134000},"page":"25-36","source":"Crossref","is-referenced-by-count":5,"title":["The T-join Problem in Sparse Graphs: Applications to Phase Assignment Problem in VLSI Mask Layout"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Berman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew B.","family":"Kahng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Devendra","family":"Vidhani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Zelikovsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,7,18]]},"reference":[{"key":"3_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft and J. D. Ulman, The Design and Analysis of Computer Algorithms, Addison Wesley, Reading, MA, 1974."},{"key":"3_CR2","unstructured":"F. Barahona, \u201cPlanar multicommodity flows, max cut and the Chinese postman problem\u201d, In W. Cook and P. D. Seymour, eds., Polyhedral Combinatorics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1 (1990), pp. 189\u2013202."},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"P. Berman, A. B. Kahng, D. Vidhani, H. Wang and A. Zelikovsky, \u201cOptimal Phase Conflict Removal for Layout of Dark Field Alternating Phase Shifting Masks\u201d, Proc. ACM\/IEEE Intl. Symp. on Physical Design, 1999, to appear.","DOI":"10.1145\/299996.300037"},{"key":"3_CR4","volume-title":"Combinatorial Optimization","author":"W. J. Cook","year":"1998","unstructured":"W. J. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Shrijver, Combinatorial Optimization, Willey Inter-Science, New York, 1998."},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"W. Cook and A. Rohe, \u201cComputing Minimum-Weight Perfect Matchings\u201d, http:\/\/www.or.uni-bonn.de\/home\/rohe\/matching.html , manuscript, August, 1998.","DOI":"10.1287\/ijoc.11.2.138"},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1145\/115234.115366","volume":"38","author":"H. N. Gabow","year":"1991","unstructured":"H. N. Gabow and R. E. Tarjan, \u201cFaster scaling algorithms for general graph matching problems\u201d, Journal of the ACM 38 (1991) 815\u2013853.","journal-title":"Journal of the ACM"},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"M. X. Goemans","year":"1995","unstructured":"M. X. Goemans and D. P. Williamson, \u201cA general approximation technique for constrained forest problems\u201d, SIAM Journal on Computing 24 (1995) 296\u2013317.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"3_CR8","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/0204019","volume":"4","author":"F. O. Hadlock","year":"1975","unstructured":"F. O. Hadlock, \u201cFinding a Maximum Cut of a Planar Graph in Polynomial Time\u201d, SIAM J. Computing 4(3) (1975), pp. 221\u2013225.","journal-title":"SIAM J. Computing"},{"key":"3_CR9","unstructured":"A. B. Kahng and H. Wang, \u201cToward Lithography-Aware Layout: Preliminary Litho Notes\u201d, manuscript, July 1997."},{"key":"3_CR10","first-page":"222","volume":"1604","author":"A. B. Kahng","year":"1998","unstructured":"A. B. Kahng, H. Wang and A. Zelikovsky, \u201cAutomated Layout and Phase Assignment Techniques for Dark Field Alternating PSM\u201d, SPIE 11th Annual BACUS Symposium on Photomask Technology, SPIE 1604 (1998), pp. 222\u2013231.","journal-title":"SPIE 11th Annual BACUS Symposium on Photomask Technology"},{"issue":"11","key":"3_CR11","doi-asserted-by":"publisher","first-page":"1828","DOI":"10.1109\/T-ED.1982.21037","volume":"ED-29","author":"M. D. Levenson","year":"1982","unstructured":"M. D. Levenson, N. S. Viswanathan and R. A. Simpson, \u201cImproving Resolution in Photolithography with a Phase-Shifting Mask\u201d, IEEE Trans. on Electron Devices ED-29(11) (1982), pp. 1828\u20131836.","journal-title":"IEEE Trans. on Electron Devices"},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R. J. Lipton","year":"1979","unstructured":"R. J. Lipton and R. E. Tarjan, \u201cA separator theorem for planar graphs\u201d, SIAM J. Appl. Math., 36 (1979), pp. 177\u2013189.","journal-title":"SIAM J. Appl. Math."},{"key":"3_CR13","doi-asserted-by":"publisher","first-page":"6584","DOI":"10.1143\/JJAP.34.6584","volume":"34","author":"A. Moniwa","year":"1995","unstructured":"A. Moniwa, T. Terasawa, K. Nakajo, J. Sakemi and S. Okazaki, \u201cHeuristic Method for Phase-Conict Minimization in Automatic Phase-Shift Mask Design\u201d, Jpn. J. Appl. Phys. 34 (1995), pp. 6584\u20136589.","journal-title":"Jpn. J. Appl. Phys."},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"M. M\u00fcller-Hannemann and K. Weihe, \u201cImproved Approximations for Minimum Cardinality Quadrangulations of Finite Element Meshes\u201d, Proc. ESA\u201997, Graz, Austria, pp. 364\u2013377.","DOI":"10.1007\/3-540-63397-9_28"},{"key":"3_CR15","doi-asserted-by":"publisher","first-page":"6774","DOI":"10.1143\/JJAP.33.6774","volume":"33","author":"K. Ooi","year":"1994","unstructured":"K. Ooi, K. Koyama and M. Kiryu, \u201cMethod of Designing Phase-Shifting Masks Utilizing a Compactor\u201d, Jpn. J. Appl. Phys. 33 (1994), pp. 6774\u20136778.","journal-title":"Jpn. J. Appl. Phys."},{"key":"3_CR16","first-page":"502","volume":"10","author":"G. I. Orlova","year":"1972","unstructured":"G. I. Orlova and Y. G. Dorfman, \u201cFinding the Maximum Cut in a Graph\u201d, Engr. Cybernetics 10 (1972), pp. 502\u2013506.","journal-title":"Engr. Cybernetics"},{"key":"3_CR17","unstructured":"SIA, The National Technology Roadmap for Semiconductors, Semiconductor Industry Association, December 1997."},{"key":"3_CR18","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1287\/ijoc.8.1.29","volume":"8","author":"D. P. Williamson","year":"1996","unstructured":"D. P. Williamson and M. X. Goemans, \u201cComputational experience with an approximation algorithm on large-scale Euclidean matching instances\u201d, INFORMS Journal of Computing, 8 (1996) 29\u201340.","journal-title":"INFORMS Journal of Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48447-7_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,28]],"date-time":"2020-04-28T02:32:13Z","timestamp":1588041133000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48447-7_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662792","9783540484479"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-48447-7_3","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}