A polynomial time algorithm for reconfiguring multiple-track models

Theodora Varvarigou, Vwani Roychowdhury, T. KailthIEEE Trans. Computers 1993 · DOI

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 mod F mod /sup 2/), where mod F is the number of faulty processors.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>
BibTeX
@article{varvarigou1993polynomial,
  author = {Theodora Varvarigou and Vwani Roychowdhury and T. Kailth},
  title = {{A polynomial time algorithm for reconfiguring multiple-track models}},
  journal = {IEEE Transactions on Computers},
  year = {1993},
  doi = {10.1109/12.214686},
}

Loading related content...

Figure