For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Switch-Box Router BOX-PEELER" and Its Tractable Problems
Atsushi TAKAHASHI Yoji KAJITANI
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1989/12/25
Print ISSN: 0000-0000
Type of Manuscript: Special Section PAPER (Special Issue on the 2nd Karuizawa Workshop on Circuits and Systems)
Category: VLSI Design Technology
Full Text: PDF>>
Given a switch-box, let C be a connection requirement. If there is a polynomial time algorithm (router) to complete C, C is said to be tractable by the algorithm. There have been proposed a number of switch-box routers but none that makes clear its tractable problems. We propose a switch-box router, or rather a principle, BOX-PEELER with a simple characterization of a class of tractable problems. BOX-PEELER is developed to be an underlying concept in switch-box routing as LEFT-EDGE method has been in 2-side channel routing.