2018/06/13 by Matthieu De Laere, De Laere, Matthieu, San Tu Pham +3 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Artificial Intelligence (cs.AI) #Data Management and Algorithms #FOS: Computer and information sciences #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.1806.06685
openalex publication_date 2018/06/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Steiner Tree Problem (STP) in graphs is an important problem with various applications in many areas such as design of integrated circuits, evolution theory, networking, etc. In this paper, we propose an algorithm to solve the STP. The algorithm includes a reducer and a solver using Variable Neighborhood Descent (VND), interacting with each other during the search. New constructive heuristics and a vertex score system for intensification purpose are proposed. The algorithm is tested on a set of benchmarks which shows encouraging results.