Title :
A polynomial time algorithm for reconfiguring multiple-track models
Author :
Varvarigou, Theodora A. ; Roychowdhury, Vwani P. ; Kailth, T.
Author_Institution :
AT&T Bell Lab., Holmdel, NJ, USA
fDate :
4/1/1993 12:00:00 AM
Abstract :
A polynomial time algorithm for solving the combinatorial problem that underlies the reconfiguration issues in the m1/2-track-m-spare model, for any arbitrary m, is discussed. The following combinatorial problem is solved: Given a set of points in a two-dimensional grid, find a set of noninteracting straight lines such that every line starts at a point and connects to one of the boundaries of the grid, there are no more than m lines overlapping in any row or column of the grid, and there are no near-miss situations. The time complexity of the algorithm is shown to be O(m|F|2), where|F is the number of faulty processors
Keywords :
computational complexity; fault tolerant computing; parallel algorithms; parallel architectures; reconfigurable architectures; combinatorial problem; faulty processors; m1/2-track-m-spare model; noninteracting straight lines; polynomial time algorithm; reconfiguring multiple-track models; time complexity; two-dimensional grid; Algorithm design and analysis; Fault tolerance; Hardware; Joining processes; Laboratories; Logic arrays; Polynomials; Routing; Sufficient conditions; Switches;
Journal_Title :
Computers, IEEE Transactions on
