Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Improved Approximations for the Max k-Colored Clustering Problem Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Steiner Trees with Bounded RC-Delay

Author : Rudolf Scheifele

Published in: Approximation and Online Algorithms

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We consider the Minimum Elmore Delay Steiner Tree Problem, which arises as a key problem in the routing step in VLSI design: Here, we are given a set of pins located on the chip which have to be connected by metal wires in order to make the propagation of electrical signals possible. Challenging timing constraints require that these electrical signals travel as fast as possible. This is modeled as a problem of constructing a Steiner tree minimizing the Elmore delay [9] between a source vertex and a set of sink vertices. The problem is strongly \(NP\)-hard even for very restricted special cases, and although it is central in VLSI design (see e.g. [18]), no approximation algorithms were known until today.
In this work, we give the first constant-factor approximation algorithm. The algorithm achieves an approximation ratio of \(3.39\) in the rectilinear plane and \(4.11\) in metric graphs. We also demonstrate that our algorithm brings improvements on real world VLSI instances compared to the currently used standard method of computing short Steiner trees.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Generalized Hypergraph Matching via Iterated Packing and Local Ratio
next chapter Multiprocessor Jobs, Preemptive Schedules, and One-Competitive Online Algorithms
Footnotes
1
The Hanan Grid is the grid that is induced by the set of \(x\)- and \(y\)-coordinates of the vertices in \(\left\{ s \right\} \cup T\) – see Hanan [13].
 
2
Every general Steiner tree can be transformed into such a tree in linear time by adding additional Steiner points and edges of length \(0\).
 
3
\(\beta \le 2\) can always be assumed by not using anything worse than a minimum terminal spanning tree as initial solution.
 
4
A rectilinear minimum spanning tree can be computed in \(\mathcal {O}(|T| \log |T|)\) time using only edges of the Delaunay Triangulation.
 
5
The actual algorithm used is depending on the size of the terminal set.
 
Literature
1.
Arora, S.: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM 45, 753–782 (1998)CrossRefMATHMathSciNet
2.
Boese, K.D., Kahng, A.B., McCoy, B.A., Robins, G.: Fidelity and near-optimality of elmore-based routing constructions. In: IEEE International Conference on Computer Design, pp. 81–84 (1993)
3.
Boese, K.D., Kahng, A.B., McCoy, B.A., Robins, G.: Rectilinear steiner trees with minimum elmore delay. In: Proceedings of the 31st Annual Design Automation Conference, pp. 381–386. ACM, New York (1994)
4.
Boese, K.D., Kahng, A.B., McCoy, B.A., Robins, G.: Near-optimal critical sink routing tree constructions. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 14, 1417–1436 (1995)CrossRef
5.
Byrka, J., Grandoni, F., Rothvoss, T., Sanità, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60, 6:1–6:33 (2013)CrossRef
6.
Chu, C., Wong, Y.C.: FLUTE: fast lookup table based rectilinear steiner minimal tree algorithm for VLSI design. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 27, 70–83 (2008)CrossRef
7.
Córdova, J., Lee, Y.: A heuristic algorithm for the rectilinear steiner arborescence problem. Technical report, University of Puerto Rico, Computer Science Department (1994)
8.
9.
Elmore, W.: The transient response of damped linear networks with particular regard to wideband amplifiers. J. Appl. Phys. 19, 55–63 (1948)CrossRef
10.
11.
Gester, M., Müller, D., Nieberg, T., Panten, C., Schulte, C., Vygen, J.: BonnRoute: algorithms and data structures for fast and good VLSI routing. ACM Trans. Des. Autom. Electron. Syst. 18, 32:1–32:24 (2013)CrossRef
12.
Gupta, R., Tutuianu, B., Pileggi, L.: The elmore delay as a bound for RC trees with generalized input signals. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 16, 95–104 (1997)CrossRef
13.
14.
Held, S., Korte, B., Rautenbach, D., Vygen, J.: Combinatorial optimization in VLSI design. In: Combinatorial Optimization: Methods and Applications, pp. 33–96. IOS Press, Amsterdam (2011)
15.
Held, S., Rotter, D.: Shallow-light steiner arborescences with vertex delays. In: Goemans, M., Correa, J. (eds.) IPCO 2013. LNCS, vol. 7801, pp. 229–241. Springer, Heidelberg (2013) CrossRef
16.
17.
Kadodi, T.: Steiner routing based on elmore delay model for minimizing maximum propagation delay. Master’s thesis, Japan Advanced Institute of Science and Technology (1999)
18.
Kahng, A., Robins, G.: On Optimal Interconnections for VLSI. Kluwer Academic Publishers, Boston (1995)CrossRefMATH
19.
Karp, R.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)CrossRef
20.
Khuller, S., Raghavachari, B., Young, N.: Balancing minimum spanning and shortest path trees. In: Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 243–250. Society for Industrial and Applied Mathematics, Philadelphia (1993)
21.
Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, 5th edn. Springer, Heidelberg (2012)CrossRef
22.
Peyer, S.: Elmore-delay-optimale Steinerbäume and VLSI-Design. Diploma’s thesis (in german), Research Institute for Discrete Mathematics, University of Bonn (2000)
23.
Peyer, S., Zachariasen, M., Jørgensen, D.G.: Delay-related secondary objectives for rectilinear steiner minimum trees. Discret. Appl. Math. 136, 271–298 (2004)CrossRefMATH
24.
25.
Rao, S.B., Smith, W.D.: Approximating geometrical graphs via “spanners” and “banyans”. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 540–550. ACM, New York (1998)
26.
Rubinstein, J., Penfield, P., Horowitz, M.A.: Signal delay in RC tree networks. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 2, 202–211 (1983)CrossRef
27.
Scheifele, R.: Steiner trees with bounded elmore delay. Master’s thesis, Research Institute for Discrete Mathematics, University of Bonn (2013)
28.
29.
Metadata
Title
Steiner Trees with Bounded RC-Delay
Author
Rudolf Scheifele
Copyright Year
2015
Book
Approximation and Online Algorithms

Print ISBN: 978-3-319-18262-9

Electronic ISBN: 978-3-319-18263-6

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-18263-6_19

Premium Partner

    Image Credits