Survey of Metaheuristics for Steiner Trees, Wire-LengthDriven Routing, and Constrained Spanning TreeProblems in VLSI*

References

[1] M. A. Breuer and A. D. Friedman, Diagnosis and Reliable Design of Digital Systems, Computer Science Press, 1976.

[2] S. Hassoun and T. Sasao, Logic Synthesis and Verification, Springer, 2002.

[3] W. J. Dally and J. W. Poulton, Digital Systems Engineering, Cambridge University Press, 1998.

[4] L. Scheffer, L. Lavagno, and G. Martin, EDA for IC Implementation, Circuit Design, and Process Technology, CRC Press, 2006.

[5] G. Gielen and R. A. Rutenbar, “Computer-aided design of analog and mixed-signal integrated circuits,” Proc. IEEE, vol. 88, no. 12, pp. 1825–1854, 2000.

[6] N. Sherwani, Algorithms for VLSI Physical Design Automation, Springer Science & Business Media, 2012.

[7] J. Cong and S. K. Lim, “Edge separability-based circuit clustering with application to multilevel circuit partitioning,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 23, no. 3, pp. 346–357, 2004.

[8] M. Sarrafzadeh and C. K. Wong, An Introduction to VLSI Physical Design, McGraw-Hill, 1996.

[9] T. Ohtsuki (Ed.), Advances in CAD for VLSI, North-Holland, 1986.

[10] R. H. J. M. Otten and R. K. Brayton, “Planning for performance,” in Proc. 35th ACM/IEEE Design Automation Conf., 1998, pp. 122–127.

[11] H. Yao and M. D. F. Wong, “A Steiner tree based algorithm for simultaneous escape routing and layer assignment,” in Proc. ACM/IEEE Int. Symp. Physical Design, 2006, pp. 189–196.

[12] [M. B. Tahir and S. M. Saeed, “Simulated annealing based VLSI global routing for interconnect length and congestion optimization,” Int. J. Comp. Appl., vol. 107, no. 7, pp. 10–15, 2014.

[13] D. Z. Chen and H. Wang, “Oblivious routing for Steiner trees in VLSI design,” J. Algorithms, vol. 55, no. 1, pp. 1–19, 2005.

[14] K. L. M. Leung and T. F. Gonzalez, “Fast algorithms for VLSI routing using Steiner trees,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 15, no. 9, pp. 1093–1100, 1996.

[15] G. A. Sigl, K. Doll, and F. M. Johannes, “Analytical placement: A linear or a quadratic objective function?,” in Proc. 28th ACM/IEEE Design Automation Conf., 1991, pp. 427–432.

[16] C. Chu and Y. C. Wong, “FLUTE: Fast lookup table based wirelength estimation technique,” in Proc. IEEE/ACM Int. Conf. Comput.-Aided Design, 2004, pp. 696–701.

[17] H. H. Yang and D. F. Wong, “Efficient Steiner tree construction based on a new exact algorithm,” in Proc. ACM/IEEE Design Automation Conf., 2000, pp. 280–285.

[18] M. J. Hutton et al., “FPGA placement and routing challenges,” IEEE Design & Test of Computers, vol. 18, no. 2, pp. 12–22, 2001.

[19] C. A. C. Coello, “Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey,” Computer Methods in Applied Mechanics and Engineering, vol. 191, no. 11–12, pp. 1245–1287, 2002.

[20] M. Dorigo and T. Stützle, Ant Colony Optimization, Cambridge, MA: MIT Press, 2004.

[21] J. Kennedy and R. Eberhart, “Particle swarm optimization,” in Proc. IEEE Int. Conf. Neural Networks, 1995, pp. 1942–1948.

[22] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671–680, 1983.

[23] Y. Shi and R. C. Eberhart, “Parameter selection in particle swarm optimization,” in Proc. Int. Conf. Evolutionary Programming, 1998, pp. 591–600.

[24] C. Solnon, “Ant colony optimization for constraint solving,” Artificial Intelligence, vol. 174, no. 8, pp. 643–671, 2010.

[25] F. Xhafa and A. Abraham, “Metaheuristics for scheduling in distributed computing environments,” Studies in Computational Intelligence, vol. 146, pp. 1–43, 2008.

[26] F. Glover, “Tabu search—Part I,” ORSA Journal on Computing, vol. 1, no. 3, pp. 190–206,1989.

[27] T. Chen et al., “A survey of deep learning for VLSI physical design automation,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 39, no. 10, pp. 2107–2122, 2020.

@article{1718966,
      author = {Jitendra Singh, Mantripragada Shabda Pyari},
      title = {Survey of Metaheuristics for Steiner Trees, Wire-LengthDriven Routing, and Constrained Spanning TreeProblems in VLSI*},
      journal = {Iconic Research And Engineering Journals},
      year = {2026},
      volume = {9},
      number = {12},
      pages = {1845-1855},
      issn = {2456-8880},
      url = {https://www.irejournals.com/formatedpaper/1718966.pdf},
      abstract = {Routing in Very Large-Scale Integration (VLSI) is a challenging task that involves managing interconnect length, congestion, power consumption, and timing. With the rapid growth of semiconductor technology, traditional algorithms like Integer Linear Programming (ILP) and dynamic programming often become too slow and impractical for large-scale circuits. Overcome this, metaheuristic algorithms such as Genetic Algorithms (GA), Simulated Annealing (SA), Ant Colony Optimization (ACO), and Particle Swarm Optimization (PSO) offer effective solutions. These algorithms are particularly useful for NP-hard problems like Steiner tree construction and wire-length optimization, striking a balance between accuracy and computational effort. This paper provides a comprehensive overview of metaheuristic applications in VLSI routing, analyzing their strengths, limitations, and real-world performance. It also highlights emerging trends like AI-powered optimization and hybrid algorithms. By offering valuable insights, this survey serves as a helpful resource for researchers and engineers navigating the complexities of modern VLSI design.},
      keywords = {VLSI Routing, Wire-Length Minimization, Steiner Tree Construction, Constrained Spanning Tree, Global Routing.},
      month = {June},
      doi = {https://doi.org/10.64388/IREV9I12-1718966}
  }