A Switch-Box Router BOX-PEELER" and Its Tractable Problems

Atsushi TAKAHASHI  Yoji KAJITANI  

Publication
IEICE TRANSACTIONS (1976-1990)   Vol.E72   No.12   pp.1367-1373
Publication Date: 1989/12/25
Online ISSN: 
DOI: 
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
Keyword: 


Full Text: PDF>>
Buy this Article




Summary: 
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.