Shortest paths and Steiner trees in VLSI routing

MaRDI QIDQ3520140zbMATH OpenFDO

Authors Sven Peyer

Publication date 20 August 2008

Full work available at URL http://d-nb.info/987223828/34

zbMATH Keywords

shortest pathsroutingSteiner treesVLSIDijkstra's algorithmrectilinear obstaclesvery-large-scale integrationaugmented Hanan gridBonnRoutedisjoint wire connectionsrectilinear Steiner minimum treeRSMTshortest rectilinear Steiner treeVLSI routing problem

Mathematics Subject Classification ID

Applications of graph theory (05C90) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Network design and communication in computer systems (68M10) Software, source code, etc. for problems pertaining to computer science (68-04)

Recommendations

• Delay-related secondary objectives for rectilinear Steiner minimum trees.
• A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing
• Approximation of rectilinear Steiner trees with length restrictions on obstacles.
• Steiner trees with bounded RC-delay
• scientific article; zbMATH DE number 219265

Cited in

(13)

• Steiner trees with bounded RC-delay
• A deep-submicron Steiner tree.
• A branch-and-price algorithm for switch-box routing
• Rectilinear group Steiner trees and applications in VLSI design
• VLSI routing in polynomial time
• scientific article; zbMATH DE number 946301 (Why is no real title available?)
• Faster goal-oriented shortest path search for bulk and incremental detailed routing
• Faster goal-oriented shortest path search for bulk and incremental detailed routing
• Preprocessing Steiner problems from VLSI layout
• Rectilinear paths with minimum segment lengths
• A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing
• A PSO-based timing-driven octilinear Steiner tree algorithm for VLSI routing considering bend reduction
• Approximation of rectilinear Steiner trees with length restrictions on obstacles.

Describes a project that uses

Uses Software

• GeoSteiner

This page was built for publication: Shortest paths and Steiner trees in VLSI routing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3520140)