3-dimensional Channel Routing

Reiss, Attila and Szeszlér, Dávid (2005) 3-dimensional Channel Routing. In: 4th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2005.00.00, Budapest.

Preview

Text jh2005_reiss_szeszler.pdf Download (117kB) | Preview

Abstract

Consider two parallel planar grids of size w × n . The vertices of these grids are called terminals and pairwise disjoint subsets of termi nals are called nets. We aim at routing all nets in a cubic grid between the two layers h olding the terminals. However, to ensure solvability, it is allowed to introduce a n empty row/column be- tween every two consecutive rows/columns containing the te rminals (in both grids). Hence the routing is to be realized in a cubic grid of size 2 n × 2 w × h . The objective is to minimize the height h . In this paper we generalize previous results of Recski and Szeszl ́er [10] and show that every problem instance is so lvable in polynomial time with height h = O (max( n, w )). This linear bound is best possible (apart from a constant factor).

Actions (login required)

Edit Item