Title :
A faster dynamic programming algorithm for exact rectilinear Steiner minimal trees
Author :
Ganley, Joseph L. ; Cohoon, James P.
Author_Institution :
Dept. of Comput. Sci., Virginia Univ., Charlottesville, VA, USA
Abstract :
An exact rectilinear Steiner minimal tree algorithm is presented that improves upon the time and space complexity of previous guarantees and is easy to implement. Experimental evidence is presented that demonstrates that the algorithm also works well in practice
Keywords :
VLSI; circuit layout CAD; computational complexity; dynamic programming; network routing; network topology; trees (mathematics); RSMT problem; VLSI; dynamic programming algorithm; exact rectilinear Steiner minimal trees; routing; space complexity; time complexity; Algorithm design and analysis; Circuits; Computer science; Dynamic programming; Heuristic algorithms; Polynomials; Routing; Steiner trees; Testing; Very large scale integration;
Conference_Titel :
VLSI, 1994. Design Automation of High Performance VLSI Systems. GLSV '94, Proceedings., Fourth Great Lakes Symposium on
Conference_Location :
Notre Dame, IN
Print_ISBN :
0-8186-5610-7
DOI :
10.1109/GLSV.1994.289962
