Skip to main content

2015 | OriginalPaper | Buchkapitel

2. Fixed Orientation Steiner Trees

verfasst von : Marcus Brazil, Martin Zachariasen

Erschienen in: Optimal Interconnection Trees in the Plane

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

This chapter covers the comparatively recent theory of Steiner trees for fixed orientation metrics. This is equivalent to solving the Steiner tree problem under a norm in which the unit ball is a centrally symmetric polygon. The chapter builds on some of the more general properties of normed Steiner trees from Chapter 1 Here the fundamental theory is developed in the first three sections, followed by discussions of global properties and algorithms.

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!

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!

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!

Fußnoten
1
The results of Widmayer et al. [400, 401] were also anticipated, in part, by earlier and contemporary papers such as [408] and [385].
 
2
The norms associated with the class of fixed orientation metrics have been referred to in the literature as ‘polyhedral norms’, in [408], or ‘block norms’, in [385]. Moreover, if we relax the condition that the polygon \(\mathcal{C}\) is centrally symmetric, then rather than having an associated norm, we have an associated gauge; see [145] for more details.
 
3
The first proof of Theorem 2.5 was given by Sarrafzadeh and Wong [338], albeit not covering the case where λ is a multiple of 3 correctly. Alternative (and correct) proofs using various proof techniques were given by Koh [235] (only for λ = 4), Li et al. [256] (only lower bounds), Brazil et al. [65], Swanepoel [358], Hayase [189] and Il’yutko [217].
 
4
Note that in λ-geometry these direction sets are the same as the ‘feasible direction sets’ defined in [70].
 
5
This theorem can be strengthened to include a lower bound of σ on the number of complementary coloured direction sets. This follows by proving a converse to Theorem 1.​28 showing that every set of supporting lines satisfying the centroid property corresponds to a Steiner configuration. The details can be found in [74], where some of the arguments rely on results from [274]. The main consequence of this lower bound is to show that the time complexity of the linear-time enumeration algorithm developed at the end of this section cannot be improved.
 
6
Zero-shifts were introduced by Du and Hwang [136] for λ = 3, and originally used as a technical tool in the quest for better bounds on the size of the generalised Hanan grid [235, 244, 245].
 
7
In 1999, Thurber and Xue [368] gave a linear programming formulation for the λ = 3 case, and in 2002, Xue and Thulasiraman [417] generalised the formulation to the general uniform orientation metric. Zachariasen [430] pointed out a non-trivial error in this formulation and presented a new and correct formulation, now generalised to all fixed orientation metrics. This latter formulation is the one briefly presented here.
 
8
Subsequently Li et al. [255] gave a simple algorithm to construct this triangular region based on finding median points and so-called mid-orientation lines. More generally, Shen [346] and Hayase [189] independently showed that when λ is a multiple of 3, the feasible region (called a ‘public domain’ in [346] and a ‘diamond area’ in [189]) is a convex polygon with up to six vertices; when λ is not a multiple of 3, then the minimum Steiner tree for three terminals is unique and the feasible region contains a single point.
 
9
This theorem has been shown over time to hold for increasingly larger classes of fixed orientation problems. In 1992 Du and Hwang [136] proved that Theorem 2.29 holds for λ = 3 (uniform metric with three orientations). They also conjectured that for any i > 0 there exists a fixed orientation metric and a terminal set N such that all minimum Steiner trees for N have some Steiner point not in GG i (N). In other words, they conjectured that the bound n − 2 in Theorem 2.29 cannot be reduced to a constant. In 1995 Koh [235] and Lee et al. [245] independently proved that the theorem holds for λ = 4 by showing that it is always possible to perform zero-shifts such that some Steiner point is connected to two terminals using straight edges only. In 1996 Lee and Shen [244] generalised the result to any λ (or uniform orientation metric) using the same proof technique. In 2001 Li et al. [257] showed that Theorem 2.29 holds for all unweighted fixed orientation metrics. Finally, in 2009 Brazil and Zachariasen [74] implicitly proved that the theorem also holds for the weighted case; this was first stated explicitly later that year by Zachariasen [431].
 
Literatur
3.
Zurück zum Zitat Agnihotri, A.R., Madden, P.H.: Congestion reduction in traditional and new routing architectures. In: Proceedings of the 13th ACM Great Lakes Symposium on VLSI (GLSVLSI), Washington, DC, pp. 211–214 (2003) Agnihotri, A.R., Madden, P.H.: Congestion reduction in traditional and new routing architectures. In: Proceedings of the 13th ACM Great Lakes Symposium on VLSI (GLSVLSI), Washington, DC, pp. 211–214 (2003)
26.
Zurück zum Zitat Berger, B., Brady, M.L., Brown, D.J., Leighton, T.: Nearly optimal algorithms and bounds for multilayer channel routing. J. ACM 42, 500–542 (1995)CrossRefMATHMathSciNet Berger, B., Brady, M.L., Brown, D.J., Leighton, T.: Nearly optimal algorithms and bounds for multilayer channel routing. J. ACM 42, 500–542 (1995)CrossRefMATHMathSciNet
41.
Zurück zum Zitat Bozorgzadeh, E., Kastner, R., Sarrafzadeh, M.: Creating and exploiting flexibility in Steiner trees. In: Proceedings of the ACM Design Automation Conference (DAC), Las Vegas, pp. 195–198 (2001) Bozorgzadeh, E., Kastner, R., Sarrafzadeh, M.: Creating and exploiting flexibility in Steiner trees. In: Proceedings of the ACM Design Automation Conference (DAC), Las Vegas, pp. 195–198 (2001)
42.
Zurück zum Zitat Bozorgzadeh, E., Kastner, R., Sarrafzadeh, M.: Creating and exploiting flexibility in rectilinear Steiner trees. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 22(5), 605–615 (2003)CrossRef Bozorgzadeh, E., Kastner, R., Sarrafzadeh, M.: Creating and exploiting flexibility in rectilinear Steiner trees. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 22(5), 605–615 (2003)CrossRef
43.
Zurück zum Zitat Brady, M.L., Brown, D.J., Powers, K.: Channel routing on a 60∘ grid. In: Proceedings of the Conference on Information Science and Systems, Princeton, New Jersey, pp. 926–931 (1990) Brady, M.L., Brown, D.J., Powers, K.: Channel routing on a 60 grid. In: Proceedings of the Conference on Information Science and Systems, Princeton, New Jersey, pp. 926–931 (1990)
45.
Zurück zum Zitat Brazil, M.: Steiner minimum trees in uniform orientation metrics. In: Du, D.-Z., Cheng, X. (eds.) Steiner Trees in Industries, pp. 1–27. Kluwer Academic, Boston (2001)CrossRef Brazil, M.: Steiner minimum trees in uniform orientation metrics. In: Du, D.-Z., Cheng, X. (eds.) Steiner Trees in Industries, pp. 1–27. Kluwer Academic, Boston (2001)CrossRef
65.
Zurück zum Zitat Brazil, M., Thomas, D.A., Weng, J.F.: Minimum networks in uniform orientation metrics. SIAM J. Comput. 30, 1579–1593 (2000)CrossRefMATHMathSciNet Brazil, M., Thomas, D.A., Weng, J.F.: Minimum networks in uniform orientation metrics. SIAM J. Comput. 30, 1579–1593 (2000)CrossRefMATHMathSciNet
70.
Zurück zum Zitat Brazil, M., Thomas, D.A., Weng, J.F., Zachariasen, M.: Canonical forms and algorithms for Steiner trees in uniform orientation metrics. Algorithmica 44, 281–300 (2006)CrossRefMATHMathSciNet Brazil, M., Thomas, D.A., Weng, J.F., Zachariasen, M.: Canonical forms and algorithms for Steiner trees in uniform orientation metrics. Algorithmica 44, 281–300 (2006)CrossRefMATHMathSciNet
72.
Zurück zum Zitat Brazil, M., Winter, P., Zachariasen, M.: Flexibility of Steiner trees in uniform orientation metrics. In: Proceedings of the International Symposium on Algorithms and Computation (ISAAC), Hong Kong. Lecture Notes in Computer Science, vol. 3341, pp. 196–208. Springer, Berlin/Heidelberg (2004) Brazil, M., Winter, P., Zachariasen, M.: Flexibility of Steiner trees in uniform orientation metrics. In: Proceedings of the International Symposium on Algorithms and Computation (ISAAC), Hong Kong. Lecture Notes in Computer Science, vol. 3341, pp. 196–208. Springer, Berlin/Heidelberg (2004)
73.
Zurück zum Zitat Brazil, M., Winter, P., Zachariasen, M.: Flexibility of Steiner trees in uniform orientation metrics. Networks 46, 142–153 (2005)CrossRefMATHMathSciNet Brazil, M., Winter, P., Zachariasen, M.: Flexibility of Steiner trees in uniform orientation metrics. Networks 46, 142–153 (2005)CrossRefMATHMathSciNet
76.
Zurück zum Zitat Brenner, U., Vygen, J.: Analytical methods in VLSI placement. In: Alpert, C.J., Mehta, D.P., Sapatnekar, S.S. (eds.) Handbook of Algorithms for VLSI Physical Design Automation, chapter 17, pp. 327–346. Taylor & Francis, Boca Raton (2009) Brenner, U., Vygen, J.: Analytical methods in VLSI placement. In: Alpert, C.J., Mehta, D.P., Sapatnekar, S.S. (eds.) Handbook of Algorithms for VLSI Physical Design Automation, chapter 17, pp. 327–346. Taylor & Francis, Boca Raton (2009)
77.
Zurück zum Zitat Burman, S., Chen, H., Sherwani, N.: Improved global routing using λ-geometry. In: Proceedings of the 29 Annual Allerton Conference on Communications, Computing and Controls, Urbana (1991) Burman, S., Chen, H., Sherwani, N.: Improved global routing using λ-geometry. In: Proceedings of the 29 Annual Allerton Conference on Communications, Computing and Controls, Urbana (1991)
81.
Zurück zum Zitat Chaudhary, K., Robinson, P.: Channel routing by sorting. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 10, 754–760 (1991)CrossRef Chaudhary, K., Robinson, P.: Channel routing by sorting. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 10, 754–760 (1991)CrossRef
82.
Zurück zum Zitat Chaudhuri, P.P.: An ecological approach to wire routing. In: IEEE International Symposium on Circuits and Systems, Tokyo, pp. 854–857 (1979) Chaudhuri, P.P.: An ecological approach to wire routing. In: IEEE International Symposium on Circuits and Systems, Tokyo, pp. 854–857 (1979)
83.
Zurück zum Zitat Chen, C.Y.R., Hou, C.Y., Singh, U.: Optimal algorithms for bubble sort based non-Manhattan channel routing. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 13, 603–609 (1994)CrossRef Chen, C.Y.R., Hou, C.Y., Singh, U.: Optimal algorithms for bubble sort based non-Manhattan channel routing. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 13, 603–609 (1994)CrossRef
85.
Zurück zum Zitat Chen, H., Cheng, C.K., Kahng, A.B., Mandoiu, I.I., Wang, Q.: Estimation of wirelength reduction for λ-geometry vs. Manhattan placement and routing. In: Proceedings ACM International Workshop on System Level Interconnect Prediction (SLIP), Monterey, pp. 71–76 (2003) Chen, H., Cheng, C.K., Kahng, A.B., Mandoiu, I.I., Wang, Q.: Estimation of wirelength reduction for λ-geometry vs. Manhattan placement and routing. In: Proceedings ACM International Workshop on System Level Interconnect Prediction (SLIP), Monterey, pp. 71–76 (2003)
87.
Zurück zum Zitat Chen, H., Cheng, C.K., Kahng, A.B., Mandoiu, I.I., Wang, Q., Yao, B.: The Y-architecture for on-chip interconnect: analysis and methodology. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 24, 588–599 (2005)CrossRef Chen, H., Cheng, C.K., Kahng, A.B., Mandoiu, I.I., Wang, Q., Yao, B.: The Y-architecture for on-chip interconnect: analysis and methodology. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 24, 588–599 (2005)CrossRef
88.
Zurück zum Zitat Chen, H., Yao, B., Zhou, F., Cheng, C.K.: The Y-architecture: yet another on-chip interconnect solution. In: Proceedings Asia and South Pacific Design Automation Conference, Kitakyushu, pp. 840–846 (2003) Chen, H., Yao, B., Zhou, F., Cheng, C.K.: The Y-architecture: yet another on-chip interconnect solution. In: Proceedings Asia and South Pacific Design Automation Conference, Kitakyushu, pp. 840–846 (2003)
95.
Zurück zum Zitat Chiang, C., Sarrafzadeh, M.: Wirability of knock-knee layouts with 45-degree wires. IEEE Trans. Circuits Syst. 38, 613–624 (1991)CrossRefMATH Chiang, C., Sarrafzadeh, M.: Wirability of knock-knee layouts with 45-degree wires. IEEE Trans. Circuits Syst. 38, 613–624 (1991)CrossRefMATH
97.
Zurück zum Zitat Choi, B., Chiang, C., Kawa, J., Sarrafzadeh, M.: Routing resources consumption on M-arch and X-arch. In: Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS), Vancouver, vol. 5, pp. V-73–V-76 (2004) Choi, B., Chiang, C., Kawa, J., Sarrafzadeh, M.: Routing resources consumption on M-arch and X-arch. In: Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS), Vancouver, vol. 5, pp. V-73–V-76 (2004)
109.
Zurück zum Zitat Cieslik, D.: The Steiner ratio of Banach-Minkowski spaces – a survey. In: Du, D.Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, Supplement Volume B, pp. 55–81. Springer, New York (2005)CrossRef Cieslik, D.: The Steiner ratio of Banach-Minkowski spaces – a survey. In: Du, D.Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, Supplement Volume B, pp. 55–81. Springer, New York (2005)CrossRef
122.
Zurück zum Zitat Coulston, C.S.: Constructing exact octagonal Steiner minimal trees. In: Proceedings of the 13th ACM Great Lakes Symposium on VLSI (GLSVLSI), Washington, DC, pp. 1–6 (2003) Coulston, C.S.: Constructing exact octagonal Steiner minimal trees. In: Proceedings of the 13th ACM Great Lakes Symposium on VLSI (GLSVLSI), Washington, DC, pp. 1–6 (2003)
133.
Zurück zum Zitat Du, D.-Z., Gao, B., Graham, R.L., Liu, Z.-C., Wan, P.-J.: Minimum Steiner trees in normed planes. Discret. Comput. Geom. 9, 351–370 (1993)CrossRefMATHMathSciNet Du, D.-Z., Gao, B., Graham, R.L., Liu, Z.-C., Wan, P.-J.: Minimum Steiner trees in normed planes. Discret. Comput. Geom. 9, 351–370 (1993)CrossRefMATHMathSciNet
135.
136.
145.
Zurück zum Zitat Durier, R., Michelot, C.: Geometrical properties of the Fermat-Weber problem. Eur. J. Oper. Res. 20, 322–343 (1985)CrossRefMathSciNet Durier, R., Michelot, C.: Geometrical properties of the Fermat-Weber problem. Eur. J. Oper. Res. 20, 322–343 (1985)CrossRefMathSciNet
167.
Zurück zum Zitat Gao, B., Du, D.-Z., Graham, R.L.: The tight lower bound for the Steiner ratio in Minkowski planes. In: Proceedings of the Tenth Annual Symposium on Computational Geometry, Stony Brook, New York, pp. 183–191 (1994) Gao, B., Du, D.-Z., Graham, R.L.: The tight lower bound for the Steiner ratio in Minkowski planes. In: Proceedings of the Tenth Annual Symposium on Computational Geometry, Stony Brook, New York, pp. 183–191 (1994)
169.
189.
Zurück zum Zitat Hayase, M.: Exact location of the Steiner point in the three-point Steiner minimum tree for λ-geometry. Electron. Commun. Jpn. 84, 84–94 (2001)CrossRef Hayase, M.: Exact location of the Steiner point in the three-point Steiner minimum tree for λ-geometry. Electron. Commun. Jpn. 84, 84–94 (2001)CrossRef
191.
Zurück zum Zitat Heiss, S.: A path connection algorithm for multi-layer boards. In: ACM Proceedings of the 5th Annual Design Automation Workshop (DAC), New York, pp. 6.1–6.14 (1968) Heiss, S.: A path connection algorithm for multi-layer boards. In: ACM Proceedings of the 5th Annual Design Automation Workshop (DAC), New York, pp. 6.1–6.14 (1968)
198.
Zurück zum Zitat Ho, T.-Y., Chang, C.-F., Chang, Y.-W., Chen, S.-J.: Multilevel full-chip routing for the X-based architecture. In: Proceedings of the ACM Design Automation Conference (DAC), Anaheim, pp. 597–602 (2005) Ho, T.-Y., Chang, C.-F., Chang, Y.-W., Chen, S.-J.: Multilevel full-chip routing for the X-based architecture. In: Proceedings of the ACM Design Automation Conference (DAC), Anaheim, pp. 597–602 (2005)
214.
Zurück zum Zitat Igarashi, M., Mitsuhashi, T., Le, A., Kazi, S., Lin, Y.-T., Fujimura, A., Teig, S.: A diagonal interconnect architecture and its application to RISC core design. In: IEEE Proceedings of the International Solid-State Circuits Conference, San Francisco pp. 460–461 (2002) Igarashi, M., Mitsuhashi, T., Le, A., Kazi, S., Lin, Y.-T., Fujimura, A., Teig, S.: A diagonal interconnect architecture and its application to RISC core design. In: IEEE Proceedings of the International Solid-State Circuits Conference, San Francisco pp. 460–461 (2002)
235.
Zurück zum Zitat Koh, C.-K.: Steiner problem in octilinear routing model. Master’s thesis, National University of Singapore (1995) Koh, C.-K.: Steiner problem in octilinear routing model. Master’s thesis, National University of Singapore (1995)
236.
Zurück zum Zitat Koh, C.-K., Madden, P.H.: Manhattan or non-Manhattan? A study of alternative VLSI routing architectures. In: Proceedings of the 10th ACM Great Lakes Symposium on VLSI (GLSVLSI), Evanston, pp. 47–52 (2000) Koh, C.-K., Madden, P.H.: Manhattan or non-Manhattan? A study of alternative VLSI routing architectures. In: Proceedings of the 10th ACM Great Lakes Symposium on VLSI (GLSVLSI), Evanston, pp. 47–52 (2000)
242.
Zurück zum Zitat Lee, C.Y.: An algorithm for path connections and its applications. IRE Trans. Electron. Comput. EC-10, 346–365 (1961)CrossRef Lee, C.Y.: An algorithm for path connections and its applications. IRE Trans. Electron. Comput. EC-10, 346–365 (1961)CrossRef
244.
Zurück zum Zitat Lee, D.T., Shen, C.F.: The Steiner minimal tree problem in the λ-geometry plane. In: Proceedings of the International Symposium on Algorithms and Computation (ISAAC), Osaka. Lecture Notes in Computer Science, vol. 1178, pp. 247–255. Springer, Berlin/Heidelberg (1996) Lee, D.T., Shen, C.F.: The Steiner minimal tree problem in the λ-geometry plane. In: Proceedings of the International Symposium on Algorithms and Computation (ISAAC), Osaka. Lecture Notes in Computer Science, vol. 1178, pp. 247–255. Springer, Berlin/Heidelberg (1996)
245.
Zurück zum Zitat Lee, D.T., Shen, C.F., Ding, C.L.: On Steiner tree problem with 45 degree routing. In: Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS), Seattle, pp. 1680–1683 (1995) Lee, D.T., Shen, C.F., Ding, C.L.: On Steiner tree problem with 45 degree routing. In: Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS), Seattle, pp. 1680–1683 (1995)
248.
Zurück zum Zitat Lee, K.K., Leong, H.W.: SOAR: a channel router for octilinear routing model. In: Proceedings of the IEEE Asia-Pacific Conference on Circuits and Systems, Sydney, pp. 346–351 (1992) Lee, K.K., Leong, H.W.: SOAR: a channel router for octilinear routing model. In: Proceedings of the IEEE Asia-Pacific Conference on Circuits and Systems, Sydney, pp. 346–351 (1992)
249.
Zurück zum Zitat Lengauer, T.: Combinatorial Algorithms for Integrated Circuit Layout. Wiley, Chichester (1990)MATH Lengauer, T.: Combinatorial Algorithms for Integrated Circuit Layout. Wiley, Chichester (1990)MATH
255.
Zurück zum Zitat Li, Y.Y., Cheung, S.K., Leung, K.S., Wong, C.K.: Steiner tree constructions in λ 3-metric. IEEE Trans. Circuits Syst. II Analog Digit. Signal Process. 45(5), 563–574 (1998)CrossRef Li, Y.Y., Cheung, S.K., Leung, K.S., Wong, C.K.: Steiner tree constructions in λ 3-metric. IEEE Trans. Circuits Syst. II Analog Digit. Signal Process. 45(5), 563–574 (1998)CrossRef
256.
Zurück zum Zitat Li, Y.Y., Leung, K.S., Wong, C.K.: Efficient heuristics for orientation metric and Euclidean Steiner tree problems. J. Comb. Optim. 4, 79–98 (2000)CrossRefMATHMathSciNet Li, Y.Y., Leung, K.S., Wong, C.K.: Efficient heuristics for orientation metric and Euclidean Steiner tree problems. J. Comb. Optim. 4, 79–98 (2000)CrossRefMATHMathSciNet
257.
259.
Zurück zum Zitat Lin, G.-H., Xue, G.: The Steiner tree problem in λ 4-geometry plane. In: Proceedings of the International Symposium on Algorithms and Computation (ISAAC), Taejon. Lecture Notes in Computer Science, vol. 1533, pp. 327–337. Springer, Berlin/Heidelberg (1998) Lin, G.-H., Xue, G.: The Steiner tree problem in λ 4-geometry plane. In: Proceedings of the International Symposium on Algorithms and Computation (ISAAC), Taejon. Lecture Notes in Computer Science, vol. 1533, pp. 327–337. Springer, Berlin/Heidelberg (1998)
263.
Zurück zum Zitat Lodi, E.: Routing multiterminal nets in a diagonal model. In: Proceedings of the 1988 Conference on Information Sciences and Systems, Princeton, pp. 899–902 (1988) Lodi, E.: Routing multiterminal nets in a diagonal model. In: Proceedings of the 1988 Conference on Information Sciences and Systems, Princeton, pp. 899–902 (1988)
264.
266.
Zurück zum Zitat Lodi, E., Luccio, F., Song, X.: A 2D channel router for the diagonal model. Integr. VLSI J. 11, 111–125 (1991)CrossRef Lodi, E., Luccio, F., Song, X.: A 2D channel router for the diagonal model. Integr. VLSI J. 11, 111–125 (1991)CrossRef
274.
Zurück zum Zitat Martini, H., Swanepoel, K.J., Weiß, G.: The Fermat-Torricelli problem in normed planes and spaces. J. Optim. Theory Appl. 115, 283–314 (2002)CrossRefMATHMathSciNet Martini, H., Swanepoel, K.J., Weiß, G.: The Fermat-Torricelli problem in normed planes and spaces. J. Optim. Theory Appl. 115, 283–314 (2002)CrossRefMATHMathSciNet
288.
Zurück zum Zitat Müller-Hannemann, M., Schulze, A.: Hardness and approximation of octilinear Steiner trees. Int. J. Comput. Geom. Appl. 17, 231–260 (2007)CrossRefMATH Müller-Hannemann, M., Schulze, A.: Hardness and approximation of octilinear Steiner trees. Int. J. Comput. Geom. Appl. 17, 231–260 (2007)CrossRefMATH
291.
Zurück zum Zitat Natarajan, S., Sherwani, N., Holmes, N.D., Sarrafzadeh, M.: Over-the-cell channel routing for high performance circuits. In: Proceedings of the 29th ACM/IEEE Design Automation Conference (DAC), Los Alamitos, pp. 600–603 (1992) Natarajan, S., Sherwani, N., Holmes, N.D., Sarrafzadeh, M.: Over-the-cell channel routing for high performance circuits. In: Proceedings of the 29th ACM/IEEE Design Automation Conference (DAC), Los Alamitos, pp. 600–603 (1992)
294.
Zurück zum Zitat Nielsen, B.K., Winter, P., Zachariasen, M.: An exact algorithm for the uniformly-oriented Steiner tree problem. In: Proceedings of the 10th European Symposium on Algorithms, Rome. Lecture Notes in Computer Science, vol. 2461, pp. 760–772. Springer, Berlin/Heidelberg (2002) Nielsen, B.K., Winter, P., Zachariasen, M.: An exact algorithm for the uniformly-oriented Steiner tree problem. In: Proceedings of the 10th European Symposium on Algorithms, Rome. Lecture Notes in Computer Science, vol. 2461, pp. 760–772. Springer, Berlin/Heidelberg (2002)
298.
Zurück zum Zitat Pagh, M.H.: Steiner trees in weighted fixed orientation metrics. Master’s thesis, Department of Computer Science, University of Copenhagen (2005) Pagh, M.H.: Steiner trees in weighted fixed orientation metrics. Master’s thesis, Department of Computer Science, University of Copenhagen (2005)
299.
Zurück zum Zitat Paluszewski, M.: VLSI routing in uniform orientation metrics. Master’s thesis, Department of Computer Science, University of Copenhagen (2004) Paluszewski, M.: VLSI routing in uniform orientation metrics. Master’s thesis, Department of Computer Science, University of Copenhagen (2004)
300.
Zurück zum Zitat Paluszewski, M., Winter, P., Zachariasen, M.: A new paradigm for general architecture routing. In: Proceedings of the 14th ACM Great Lakes Symposium on VLSI (GLSVLSI), Boston, pp. 202–207 (2004) Paluszewski, M., Winter, P., Zachariasen, M.: A new paradigm for general architecture routing. In: Proceedings of the 14th ACM Great Lakes Symposium on VLSI (GLSVLSI), Boston, pp. 202–207 (2004)
304.
Zurück zum Zitat 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 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
312.
Zurück zum Zitat Powers, K., Brown, D., Brady, M.L.: The 60∘ grid: routing channels in width \(d/\sqrt{3}\). In: Proceedings of the 1st Great Lakes Symposium on VLSI, Kalamazoo, pp. 214–219 (1991) Powers, K., Brown, D., Brady, M.L.: The 60 grid: routing channels in width \(d/\sqrt{3}\). In: Proceedings of the 1st Great Lakes Symposium on VLSI, Kalamazoo, pp. 214–219 (1991)
333.
Zurück zum Zitat Samanta, R., Erzin, A., Raha, S.: Timing-driven Steiner tree construction on uniform λ-geometry. In: 18th International Symposium on VLSI Design and Test, Coimbatore, India, pp. 1–4. IEEE (2014) Samanta, R., Erzin, A., Raha, S.: Timing-driven Steiner tree construction on uniform λ-geometry. In: 18th International Symposium on VLSI Design and Test, Coimbatore, India, pp. 1–4. IEEE (2014)
335.
Zurück zum Zitat Sarrafzadeh, M.: Hierarchical approaches to VLSI circuit layout. PhD thesis, University of Illinois at Urbana-Champaign (1986) Sarrafzadeh, M.: Hierarchical approaches to VLSI circuit layout. PhD thesis, University of Illinois at Urbana-Champaign (1986)
337.
338.
Zurück zum Zitat Sarrafzadeh, M., Wong, C.K.: Hierarchical Steiner tree construction in uniform orientations. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 11, 1095–1103 (1992)CrossRef Sarrafzadeh, M., Wong, C.K.: Hierarchical Steiner tree construction in uniform orientations. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 11, 1095–1103 (1992)CrossRef
346.
Zurück zum Zitat Shen, C.F.: The λ-geometry Steiner minimal tree problem and visualization. PhD thesis, Northwestern University, Evanston (1997) Shen, C.F.: The λ-geometry Steiner minimal tree problem and visualization. PhD thesis, Northwestern University, Evanston (1997)
354.
Zurück zum Zitat Song, X., Tan, X.: An optimal channel-routing algorithm in the Times Square model. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 13, 891–998 (1994)CrossRef Song, X., Tan, X.: An optimal channel-routing algorithm in the Times Square model. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 13, 891–998 (1994)CrossRef
360.
Zurück zum Zitat Tan, X., Song, X.: Hexagonal 3-layer channel routing. Inf. Process. Lett. 55, 223–228 (1995)CrossRefMATH Tan, X., Song, X.: Hexagonal 3-layer channel routing. Inf. Process. Lett. 55, 223–228 (1995)CrossRefMATH
362.
Zurück zum Zitat Teig, S.: The X Architecture: Not your father’s diagonal wiring. In: International Workshop on System-Level Interconnect Prediction (SLIP), San Diego, pp. 33–37. ACM (2002) Teig, S.: The X Architecture: Not your father’s diagonal wiring. In: International Workshop on System-Level Interconnect Prediction (SLIP), San Diego, pp. 33–37. ACM (2002)
368.
Zurück zum Zitat Thurber, A.P., Xue, G.: Computing hexagonal Steiner trees using PCX. In: Proceedings of the 6th IEEE International Conference on Electronics, Circuits and Systems (ICECS), Pafos, pp. 381–384 (1999) Thurber, A.P., Xue, G.: Computing hexagonal Steiner trees using PCX. In: Proceedings of the 6th IEEE International Conference on Electronics, Circuits and Systems (ICECS), Pafos, pp. 381–384 (1999)
382.
Zurück zum Zitat Wang, D.C.: Novel schemes for IC layout, Part I: two-layer channel routing. In: Proceedings of the 28th ACM/IEEE Design Automation Conference, San Francisco, pp. 49–53 (1991) Wang, D.C.: Novel schemes for IC layout, Part I: two-layer channel routing. In: Proceedings of the 28th ACM/IEEE Design Automation Conference, San Francisco, pp. 49–53 (1991)
399.
Zurück zum Zitat Whitney, T., Mead, C.: An integer based hierarchical representation for VLSI. In: Advanced Research in VLSI (Proceedings of the 4th MIT Conference), Cambridge, pp. 241–257 (1986) Whitney, T., Mead, C.: An integer based hierarchical representation for VLSI. In: Advanced Research in VLSI (Proceedings of the 4th MIT Conference), Cambridge, pp. 241–257 (1986)
400.
Zurück zum Zitat Widmayer, P., Wu, Y.F., Wong, C.K.: Distance problems in computational geometry with fixed orientations. In: Proceedings of the Symposium on Computational Geometry, Baltimore, pp. 186–195 (1985) Widmayer, P., Wu, Y.F., Wong, C.K.: Distance problems in computational geometry with fixed orientations. In: Proceedings of the Symposium on Computational Geometry, Baltimore, pp. 186–195 (1985)
401.
408.
Zurück zum Zitat Witzgall, C.: Optimal location of a central facility: mathematical models and concept. Technical report, National Bureau of Standards, Washington, DC (1965) Witzgall, C.: Optimal location of a central facility: mathematical models and concept. Technical report, National Bureau of Standards, Washington, DC (1965)
417.
Zurück zum Zitat Xue, G., Thulasiraman, K.: Computing the shortest network under a fixed topology. IEEE Trans. Comput. 51, 1117–1120 (2002)MathSciNet Xue, G., Thulasiraman, K.: Computing the shortest network under a fixed topology. IEEE Trans. Comput. 51, 1117–1120 (2002)MathSciNet
418.
Zurück zum Zitat Yan, G.Y., Albrecht, A., Yound, G.H., Wong, C.K.: The Steiner tree problem in orientation metrics. J. Comput. Syst. Sci. 55, 529–546 (1997)CrossRefMATH Yan, G.Y., Albrecht, A., Yound, G.H., Wong, C.K.: The Steiner tree problem in orientation metrics. J. Comput. Syst. Sci. 55, 529–546 (1997)CrossRefMATH
419.
Zurück zum Zitat Yan, J.-T.: An improved optimal algorithm for bubble-sorting-based non-Manhattan channel routing. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 18, 163–171 (1999)CrossRef Yan, J.-T.: An improved optimal algorithm for bubble-sorting-based non-Manhattan channel routing. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 18, 163–171 (1999)CrossRef
420.
Zurück zum Zitat Yan, J.-T.: Timing-driven octilinear Steiner tree construction based on Steiner-point reassignment and path reconstruction. ACM Trans. Des. Autom. Electron. Syst. (TODAES) 13(2), 26 (2008) Yan, J.-T.: Timing-driven octilinear Steiner tree construction based on Steiner-point reassignment and path reconstruction. ACM Trans. Des. Autom. Electron. Syst. (TODAES) 13(2), 26 (2008)
424.
Zurück zum Zitat Yildiz, M.C., Madden, P.H.: Preferred direction Steiner trees. In: Proceedings of the 11th ACM Great Lakes Symposium on VLSI (GLSVLSI), West Lafayette, pp. 56–61 (2001) Yildiz, M.C., Madden, P.H.: Preferred direction Steiner trees. In: Proceedings of the 11th ACM Great Lakes Symposium on VLSI (GLSVLSI), West Lafayette, pp. 56–61 (2001)
425.
Zurück zum Zitat Yildiz, M.C., Madden, P.H.: Preferred direction Steiner trees. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 21, 1368–1372 (2002)CrossRef Yildiz, M.C., Madden, P.H.: Preferred direction Steiner trees. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 21, 1368–1372 (2002)CrossRef
430.
Zurück zum Zitat Zachariasen, M.: Comment on “Computing the shortest network under a fixed topology”. IEEE Trans. Comput. 55, 783–784 (2006)CrossRef Zachariasen, M.: Comment on “Computing the shortest network under a fixed topology”. IEEE Trans. Comput. 55, 783–784 (2006)CrossRef
431.
Zurück zum Zitat Zachariasen, M.: Fixed orientation interconnection problems: theory, algorithms and applications. Technical report, University of Copenhagen (Doctor of Science Dissertation) (2009) Zachariasen, M.: Fixed orientation interconnection problems: theory, algorithms and applications. Technical report, University of Copenhagen (Doctor of Science Dissertation) (2009)
Metadaten
Titel
Fixed Orientation Steiner Trees
verfasst von
Marcus Brazil
Martin Zachariasen
Copyright-Jahr
2015
DOI
https://doi.org/10.1007/978-3-319-13915-9_2