Width-reduction for a linear time channel routing algorithm
M. A. Lengyel
Computing and Informatics, Tome 28 (2012) no. 1, / Harvested from Computing and Informatics
This paper presents a new upper bound for channel routing of multiterminal nets on two layers. The result, which is essentially the improving of Recski and Strzyzewski's algorithm [2], works in linear time and uses width at most 4l/3, where l is the length of the channel. (The aforementioned algorithm used width at most 3l/2.)In 1994, Gao and Kaufmann [1] presented a new algorithm for channel routing of multiterminal nets on two layers, which required 3d/2 + O (  ) tracks, where d was the density of the channel routing problem. The result of this paper is better than this, if d is very close to its upper bound, namely to l. In fact, this is rarely the case.
Publié le : 2012-01-26
Classification: 
@article{cai603,
     author = {M. A. Lengyel},
     title = {Width-reduction for a linear time channel routing algorithm},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai603}
}
M. A. Lengyel. Width-reduction for a linear time channel routing algorithm. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai603/