Polynomial time manhattan routing without doglegs - a generalization of gallai's algorithm
E. Boros ; A. Recski ; T. Szkaliczki ; F. Wettl
Computing and Informatics, Tome 28 (2012) no. 1, / Harvested from Computing and Informatics
Text on Computing and Informatics
Gallai's classical result on interval packing can be applied in VLSI routing to find, in linear time, a minimum/width dogleg/free routing in the Manhattan model, provided that all the terminals are on one side of a rectangular [1]. Should the terminals appear on two opposite sides of a rectangular, the corresponding "channel routing problem" is NP/complete [2,3]. We generalize Gallai's result for the case if the terminals appear on two adjacent sides of the rectangular.
Publié le : 2012-01-26
Classification:  
@article{cai593,
     author = {E. Boros and A. Recski and T. Szkaliczki and F. Wettl},
     title = {Polynomial time manhattan routing without doglegs - a generalization of gallai's algorithm},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai593}
}

E. Boros; A. Recski; T. Szkaliczki; F. Wettl. Polynomial time manhattan routing without doglegs - a generalization of gallai's algorithm. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai593/