Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Improved Approximations for the Max k-Colored Clustering Problem Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Steiner Trees with Bounded RC-Delay

verfasst von : Rudolf Scheifele

Erschienen in: Approximation and Online Algorithms

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Generalized Hypergraph Matching via Iterated Packing and Local Ratio
Nächstes Kapitel Multiprocessor Jobs, Preemptive Schedules, and One-Competitive Online Algorithms
Fußnoten
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.
 
Literatur
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.
Shi, W., Su, C.: The rectilinear steiner arborescence problem is NP-complete. SIAM J. Comput. 35, 729–740 (2005)CrossRefMathSciNet
29.
Metadaten
Titel
Steiner Trees with Bounded RC-Delay
verfasst von
Rudolf Scheifele
Copyright-Jahr
2015
Buch
Approximation and Online Algorithms

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

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

Copyright-Jahr: 2015

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