{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:09:26Z","timestamp":1753884566055,"version":"3.41.2"},"reference-count":45,"publisher":"World Scientific Pub Co Pte Ltd","issue":"09","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J CIRCUIT SYST COMP"],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:p> In this paper, Pseudo-Boolean Satisfiability (PB-SAT)-based congestion reduction and overflow minimization techniques are introduced for constructing congestion-aware rectilinear Steiner trees for global routing in IC design. Since congestion in different routing channels is a big issue in routing nets, various congestion minimization approaches have been proposed by many researchers. However, the increasing complexity of integrated circuits and the reduction of their size make the congestion problem more complicated. The proposed method can produce a congestion-free routing solution by generating a suitable rectilinear Steiner tree for circuit nets. To reduce the complexity of the problem, the nets are solved individually using a Minimum Bounding Box (MBB)-based heuristic technique. The algorithm is validated by utilizing the well-known ISPD 98 global routing benchmarks. Experimental results prove that the methodology is capable of routing most of the nets within the given routing capacity satisfying all the routing parameters. The results also show that the algorithm can produce congestion-aware Steiner trees efficiently within a nominal time-bound. <\/jats:p>","DOI":"10.1142\/s0218126622501651","type":"journal-article","created":{"date-parts":[[2022,3,7]],"date-time":"2022-03-07T03:09:07Z","timestamp":1646622547000},"source":"Crossref","is-referenced-by-count":0,"title":["Congestion-Aware Rectilinear Steiner Tree Construction Using PB-SAT"],"prefix":"10.1142","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5574-6334","authenticated-orcid":false,"given":"Sudeshna","family":"Kundu","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, National Institute of Technology, Mahatma Gandhi Rd, A-Zone, Durgapur, West Bengal 713209, India"}]},{"given":"Suchismita","family":"Roy","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, National Institute of Technology, Mahatma Gandhi Rd, A-Zone, Durgapur, West Bengal 713209, India"}]},{"given":"Shyamapada","family":"Mukherjee","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, National Institute of Technology, NIT Road, Fakiratilla, Silchar, Assam 788010, India"}]}],"member":"219","published-online":{"date-parts":[[2022,3,5]]},"reference":[{"key":"S0218126622501651BIB001","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.2986138"},{"key":"S0218126622501651BIB002","doi-asserted-by":"publisher","DOI":"10.1142\/4109"},{"key":"S0218126622501651BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-9260(01)00020-7"},{"volume-title":"Combinatorial Algorithms for Integrated Circuit Layout","year":"2012","author":"Lengauer T.","key":"S0218126622501651BIB004"},{"key":"S0218126622501651BIB005","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1961.5219222"},{"key":"S0218126622501651BIB006","doi-asserted-by":"publisher","DOI":"10.1137\/0204019"},{"key":"S0218126622501651BIB007","first-page":"71","volume":"80","author":"Deza A.","year":"2012","journal-title":"JCMCC-J. Combin. Math. Combin. Comput."},{"volume-title":"Algorithms for VLSI Physical Design Automation","year":"2007","author":"Sherwani N. A.","key":"S0218126622501651BIB008"},{"key":"S0218126622501651BIB009","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2001.968655"},{"key":"S0218126622501651BIB010","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2004.826547"},{"key":"S0218126622501651BIB011","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2007.907003"},{"key":"S0218126622501651BIB012","first-page":"503","volume-title":"Proc. 2007 IEEE\/ACM Int. Conf. Comput.-aided Design","author":"Cho M.","year":"2007"},{"key":"S0218126622501651BIB013","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2007.357994"},{"key":"S0218126622501651BIB014","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.923255"},{"key":"S0218126622501651BIB015","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2008.4483946"},{"key":"S0218126622501651BIB016","doi-asserted-by":"publisher","DOI":"10.1109\/FPGA.1995.242049"},{"key":"S0218126622501651BIB017","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2012.2235124"},{"key":"S0218126622501651BIB018","doi-asserted-by":"publisher","DOI":"10.1142\/S0218126615500826"},{"key":"S0218126622501651BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/j.vlsi.2015.12.007"},{"key":"S0218126622501651BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/s10470-019-01513-y"},{"key":"S0218126622501651BIB021","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2009.4796543"},{"key":"S0218126622501651BIB022","first-page":"231","volume-title":"Int. Symp. Quality Electronic Design (ISQED)","author":"Lu J.","year":"2013"},{"key":"S0218126622501651BIB023","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2011.6105336"},{"key":"S0218126622501651BIB024","doi-asserted-by":"publisher","DOI":"10.1145\/1629911.1629999"},{"key":"S0218126622501651BIB025","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2009.2013991"},{"key":"S0218126622501651BIB026","doi-asserted-by":"publisher","DOI":"10.1145\/1353610.1353625"},{"key":"S0218126622501651BIB027","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2007.907068"},{"key":"S0218126622501651BIB028","first-page":"1","author":"Liu G.","year":"2020","journal-title":"J. Ambient Intell. Human. Comput."},{"key":"S0218126622501651BIB029","doi-asserted-by":"publisher","DOI":"10.1145\/774572.774638"},{"key":"S0218126622501651BIB030","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2004.842808"},{"key":"S0218126622501651BIB031","doi-asserted-by":"publisher","DOI":"10.1109\/ICATCCT.2016.7912075"},{"key":"S0218126622501651BIB032","doi-asserted-by":"publisher","DOI":"10.1142\/S0218126620500577"},{"key":"S0218126622501651BIB033","doi-asserted-by":"publisher","DOI":"10.1049\/ip-cdt:20050164"},{"key":"S0218126622501651BIB034","doi-asserted-by":"publisher","DOI":"10.1166\/jolpe.2018.1547"},{"key":"S0218126622501651BIB035","first-page":"502","volume-title":"Int. Conf. Theory and Applications of Satisfiability Testing","author":"E\u00e9n N.","year":"2003"},{"key":"S0218126622501651BIB036","first-page":"165","volume":"2","author":"Sheini H. M.","year":"2006","journal-title":"J. Satisf. Bool. Model. Comput."},{"key":"S0218126622501651BIB037","first-page":"209","volume":"2","author":"Manquinho V. M.","year":"2006","journal-title":"J. Satisf. Bool. Model. Comput."},{"key":"S0218126622501651BIB038","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2007.1075"},{"key":"S0218126622501651BIB039","doi-asserted-by":"publisher","DOI":"10.1109\/BRACIS.2014.43"},{"key":"S0218126622501651BIB040","doi-asserted-by":"publisher","DOI":"10.1109\/ICCCAS.2013.6765397"},{"key":"S0218126622501651BIB041","doi-asserted-by":"publisher","DOI":"10.1109\/ISVLSI.2009.38"},{"key":"S0218126622501651BIB043","doi-asserted-by":"publisher","DOI":"10.1145\/1497561.1497575"},{"key":"S0218126622501651BIB044","first-page":"232","volume-title":"Proc. 2008 Asia and South Pacific Design Automation Conf.","author":"Gao J.-R.","year":"2008"},{"key":"S0218126622501651BIB045","first-page":"344","volume-title":"2008 IEEE\/ACM Int Conf. Computer-Aided Design","author":"Zhang Y.","year":"2008"},{"key":"S0218126622501651BIB046","doi-asserted-by":"publisher","DOI":"10.1145\/2767127"}],"container-title":["Journal of Circuits, Systems and Computers"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218126622501651","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,27]],"date-time":"2022-05-27T08:15:54Z","timestamp":1653639354000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0218126622501651"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,5]]},"references-count":45,"journal-issue":{"issue":"09","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["10.1142\/S0218126622501651"],"URL":"https:\/\/doi.org\/10.1142\/s0218126622501651","relation":{},"ISSN":["0218-1266","1793-6454"],"issn-type":[{"type":"print","value":"0218-1266"},{"type":"electronic","value":"1793-6454"}],"subject":[],"published":{"date-parts":[[2022,3,5]]},"article-number":"2250165"}}