{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T11:59:32Z","timestamp":1759147172644,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,12,2]],"date-time":"2015-12-02T00:00:00Z","timestamp":1449014400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["Project 61125401, Project 61376040 and Project 61274032"],"award-info":[{"award-number":["Project 61125401, Project 61376040 and Project 61274032"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"SRC","award":["2014-TS-2559"],"award-info":[{"award-number":["2014-TS-2559"]}]},{"DOI":"10.13039\/501100003399","name":"Shanghai Science and Technology Committee","doi-asserted-by":"crossref","award":["13XD1401100"],"award-info":[{"award-number":["13XD1401100"]}],"id":[{"id":"10.13039\/501100003399","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF","award":["CCF-1115550, CCF-1218906 and CNS-1441695"],"award-info":[{"award-number":["CCF-1115550, CCF-1218906 and CNS-1441695"]}]},{"DOI":"10.13039\/501100012166","name":"National Basic Research Program of China","doi-asserted-by":"crossref","award":["2011CB309701"],"award-info":[{"award-number":["2011CB309701"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2015,12,2]]},"abstract":"<jats:p>\n            In this article we present a\n            <jats:italic>pairwise coloring<\/jats:italic>\n            (PWC) approach to tackle the layout decomposition problem for\n            <jats:italic>triple patterning lithography<\/jats:italic>\n            (TPL). The main idea is to reduce the problem to a set of bi-coloring problems. The overall solution is refined by applying a bi-coloring method for pairs of color sets per pass. One obvious advantage of this method is that the existing\n            <jats:italic>double patterning lithography<\/jats:italic>\n            (DPL) techniques can be reused effortlessly. Moreover, we observe that each pass can be fulfilled efficiently by integrating an SPQR-tree-graph-division-based bi-coloring method. In addition, to prevent the solution getting stuck in the local minima, an\n            <jats:italic>adaptive multi-start<\/jats:italic>\n            (AMS) approach is incorporated. Adaptive starting points are generated according to the vote of previous solutions. The experimental results show that our method is competitive with other works on both solution quality and runtime performance.\n          <\/jats:p>","DOI":"10.1145\/2764904","type":"journal-article","created":{"date-parts":[[2015,12,4]],"date-time":"2015-12-04T13:43:07Z","timestamp":1449236587000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Layout Decomposition with Pairwise Coloring and Adaptive Multi-Start for Triple Patterning Lithography"],"prefix":"10.1145","volume":"21","author":[{"given":"Ye","family":"Zhang","sequence":"first","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wai-Shing","family":"Luk","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yunfeng","family":"Yang","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hai","family":"Zhou","sequence":"additional","affiliation":[{"name":"Northwestern University, Evanston, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Changhao","family":"Yan","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David Z.","family":"Pan","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuan","family":"Zeng","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,12,2]]},"reference":[{"volume-title":"Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties","author":"Ausiello Giorgio","key":"e_1_2_1_1_1","unstructured":"Giorgio Ausiello . 1999. Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties . Springer . Giorgio Ausiello. 1999. Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties. Springer."},{"key":"e_1_2_1_2_1","unstructured":"Kenneth D. Boese Andrew B. Kahng and Sudhakar Muddu. 1993. On the big valley and adaptive multi-start for discrete global optimizations. Tech. rep. TR-930 15. http:\/\/ftp.cs.ucla.edu\/tech-report\/1993-reports\/930015.pdf.  Kenneth D. Boese Andrew B. Kahng and Sudhakar Muddu. 1993. On the big valley and adaptive multi-start for discrete global optimizations. Tech. rep. TR-930 15. http:\/\/ftp.cs.ucla.edu\/tech-report\/1993-reports\/930015.pdf."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(94)90065-5"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISQED.2013.6523667"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1129601.1129625"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/288548.289079"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2228360.2228579"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2013.2288678"},{"key":"e_1_2_1_9_1","volume-title":"Proc. SPIE 8327","author":"Ghaida Rani S.","year":"2012","unstructured":"Rani S. Ghaida , Kanak B. Agarwal , Lars W. Liebmann , Sani R. Nassif , and Puneet Gupta . 2012 . A novel methodology for triple\/multiple-patterning layout decomposition . Proc. SPIE 8327 . Rani S. Ghaida, Kanak B. Agarwal, Lars W. Liebmann, Sani R. Nassif, and Puneet Gupta. 2012. A novel methodology for triple\/multiple-patterning layout decomposition. Proc. SPIE 8327."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2012.2232710"},{"key":"e_1_2_1_11_1","volume-title":"Kochenberger","author":"Glover Fred","year":"2003","unstructured":"Fred Glover and Gary A . Kochenberger . 2003 . Handbook of Metaheuristics. Springer . Fred Glover and Gary A. Kochenberger. 2003. Handbook of Metaheuristics. Springer."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCG.1983.262975"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/647552.729400"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204019"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.644032"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202012"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1509456.1509563"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463209.2488818"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133429.2133451"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214021"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/646251.685681"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1950815.1950966"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD'13)","author":"Tian Haitong","key":"e_1_2_1_24_1","unstructured":"Haitong Tian , Yuelin Du , Hongbo Zhang , Zigang Xiao , and Martin D. F. Wong . 2013. Constrained pattern assignment for standard cell based triple patterning lithography . In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD'13) . 178--185. Haitong Tian, Yuelin Du, Hongbo Zhang, Zigang Xiao, and Martin D. F. Wong. 2013. Constrained pattern assignment for standard cell based triple patterning lithography. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD'13). 178--185."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429384.2429396"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735023.1735054"},{"volume-title":"Proceedings of the 15th IEEE\/ACM Asia and South Pacific Design Automation Conference (ASPDAC'10)","author":"Yang Jae-Seok","key":"e_1_2_1_27_1","unstructured":"Jae-Seok Yang , Katrina Lu , Minsik Cho , Kun Yuan , and David Z. Pan . 2010. A new graph-theoretic, multi-objective layout decomposition framework for double patterning lithography . In Proceedings of the 15th IEEE\/ACM Asia and South Pacific Design Automation Conference (ASPDAC'10) . 637--644. Jae-Seok Yang, Katrina Lu, Minsik Cho, Kun Yuan, and David Z. Pan. 2010. A new graph-theoretic, multi-objective layout decomposition framework for double patterning lithography. In Proceedings of the 15th IEEE\/ACM Asia and South Pacific Design Automation Conference (ASPDAC'10). 637--644."},{"volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD'13)","author":"Yu Bei","key":"e_1_2_1_28_1","unstructured":"Bei Yu , Yen-Hung Lin , Luk-Pat Gerard , Duo Ding , Kevin Lucas , and David Z. Pan . 2013. A high-performance triple patterning layout decomposer with balanced density . In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD'13) . 163--169. Bei Yu, Yen-Hung Lin, Luk-Pat Gerard, Duo Ding, Kevin Lucas, and David Z. Pan. 2013. A high-performance triple patterning layout decomposer with balanced density. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD'13). 163--169."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2593069.2593152"},{"volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD'11)","author":"Yu Bei","key":"e_1_2_1_30_1","unstructured":"Bei Yu , Kun Yuan , Boyang Zhang , Duo Ding , and David Z. Pan . 2011. Layout decomposition for triple patterning lithography . In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD'11) . 1--8. Bei Yu, Kun Yuan, Boyang Zhang, Duo Ding, and David Z. Pan. 2011. Layout decomposition for triple patterning lithography. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD'11). 1--8."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2009.2035577"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2561828.2561864"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.vlsi.2013.09.002"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2764904","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2764904","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:12:23Z","timestamp":1750227143000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2764904"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,2]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,12,2]]}},"alternative-id":["10.1145\/2764904"],"URL":"https:\/\/doi.org\/10.1145\/2764904","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2015,12,2]]},"assertion":[{"value":"2014-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}