| Tartalom: |
http://real.mtak.hu/20801/ |
| Archívum: |
MTA Könyvtár |
| Gyűjtemény: |
Status = Published
Type = Conference or Workshop Item
|
| Cím: |
3-dimensional Channel Routing
|
| Létrehozó: |
Reiss, Attila
Szeszlér, Dávid
|
| Dátum: |
2005
|
| Téma: |
QA Mathematics / matematika
|
| Tartalmi leírás: |
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).
|
| Típus: |
Conference or Workshop Item
NonPeerReviewed
|
| Formátum: |
text
|
| Azonosító: |
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.
|
| Kapcsolat: |
|
