{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T12:07:53Z","timestamp":1759147673679},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J CIRCUIT SYST COMP"],"published-print":{"date-parts":[[2015,7]]},"abstract":"<jats:p>In this work we propose a game theory (GT)-based global router. It works in two steps: (i) Initial routing of all nets using maze routing with framing (MRF) and (ii) GT-based rip-up and reroute (R&amp;R) process. In initial routing, the nets are divided into several small subsets which are routed concurrently using multithreading (MT). The main task of the GT-based R&amp;R process is to eliminate congestion. Nets are considered as players and each player employs two pure strategies: (attempt to improve its spanning tree, and, do not attempt to improve its spanning tree). The nets also have mixed strategies whose values act as probabilities for them to select any particular pure strategy. The nets which select their first strategy will go through the R&amp;R operation. We also propose an algorithm which computes the mixed strategies of nets. The advantage of using GT to select nets is that it reduces the number of nets and the number of iterations in the R&amp;R process. The performance of the proposed global router was evaluated on ISPD'98 benchmarks and compared with two recent global routers, namely, Box Router 2.0 (configured for speed) and Side-winder. The results show that the proposed global router with MT has a shorter runtime to converge to a valid solution than that of Box Router 2.0. It also outperforms Side-winder in terms of routability. The experimental results demonstrated that GT is a valuable technique in reducing the runtime of global routers.<\/jats:p>","DOI":"10.1142\/s0218126615500826","type":"journal-article","created":{"date-parts":[[2015,3,30]],"date-time":"2015-03-30T14:14:12Z","timestamp":1427724852000},"page":"1550082","source":"Crossref","is-referenced-by-count":9,"title":["A Game Theory-Based Heuristic for the Two-Dimensional VLSI Global Routing Problem"],"prefix":"10.1142","volume":"24","author":[{"given":"Umair F.","family":"Siddiqi","sequence":"first","affiliation":[{"name":"Center for Communications &amp; Information Technology Research, Research Institute, King Fahd University of Petroleum &amp; Minerals, Dhahran 31261, Saudi Arabia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sadiq M.","family":"Sait","sequence":"additional","affiliation":[{"name":"Center for Communications &amp; Information Technology Research, Department of Computer Engineering, College of Computer Science &amp; Engineering, King Fahd University of Petroleum &amp; Minerals, Dhahran 31261, Saudi Arabia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoichi","family":"Shiraishi","sequence":"additional","affiliation":[{"name":"Department of Mechanical Science and Technology, School of Science and Technology, Gunma University, 29-1 Honcho, Ota-Shi, Gunma 373-0052, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2015,5,26]]},"reference":[{"key":"rf1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-92106-2","volume-title":"Combinatorial Algorithms for Integrated Circuit and Layout","author":"Langauer T.","year":"1990"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1142\/4109"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-374364-0.50019-9"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2013.2265371"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1986.1270218"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2012.2234489"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2012.2234489"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1002\/9781118547168"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1109\/JCN.2008.6388348"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12775-5_9"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2006.885835"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1145\/1497561.1497575"}],"container-title":["Journal of Circuits, Systems and Computers"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218126615500826","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,31]],"date-time":"2020-08-31T08:26:03Z","timestamp":1598862363000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218126615500826"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,26]]},"references-count":13,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2015,5,26]]},"published-print":{"date-parts":[[2015,7]]}},"alternative-id":["10.1142\/S0218126615500826"],"URL":"https:\/\/doi.org\/10.1142\/s0218126615500826","relation":{},"ISSN":["0218-1266","1793-6454"],"issn-type":[{"value":"0218-1266","type":"print"},{"value":"1793-6454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,26]]}}}