Boosting Rectilinear Steiner Minimum Tree Algorithms with Augmented Bounding Volume Hierarchy

The rectilinear Steiner minimum tree (RSMT) problem computes the shortest network connecting a given set of points using only horizontal and vertical lines, possibly adding extra points (Steiner points) to minimize the total length. RSMT solvers seek to balance speed and accuracy. In this work, we design a framework to boost existing RSMT solvers, extending the Pareto front. Combined with GeoSteiner, our algorithm reaches 5.16\% length error on nets with 1000 pins. The average time needed is 0.46 seconds. This provides an effective way to solve large-scale RSMT problems with small-scale solvers.

Authors

Publication Details

Journal
ArXiv.org
Published
2025-03-04
Primary Topic
VLSI and FPGA Design Techniques
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Boosting Rectilinear Steiner Minimum Tree Algorithms with Augmented Bounding Volume Hierarchy

Puhan Yang, G. Li
ArXiv.org
VLSI and FPGA Design Techniques
article

Boosting Rectilinear Steiner Minimum Tree Algorithms with Augmented Bounding Volume Hierarchy

Puhan Yang, G. Li
article en

Abstract

The rectilinear Steiner minimum tree (RSMT) problem computes the shortest network connecting a given set of points using only horizontal and vertical lines, possibly adding extra points (Steiner points) to minimize the total length. RSMT solvers seek to balance speed and accuracy. In this work, we design a framework to boost existing RSMT solvers, extending the Pareto front. Combined with GeoSteiner, our algorithm reaches 5.16\% length error on nets with 1000 pins. The average time needed is 0.46 seconds. This provides an effective way to solve large-scale RSMT problems with small-scale solvers.

ArXiv.org
Openalex Percentile: Top 70%
VLSI and FPGA Design Techniques
Open Access PDFOpenAlex
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Boosting Rectilinear Steiner Minimum Tree Algorithms with Augmented Bounding Volume Hierarchy — Puhan Yang, G. Li · ArXiv.org (2025) | TGRS Research Map | TGRS