Back to Search
Start Over
The minimum firing time of the generalized firing squad synchronization problem for squares.
- Source :
-
Theoretical Computer Science . Aug2014, p46-69. 24p. - Publication Year :
- 2014
-
Abstract
- For almost all variations of the firing squad synchronization problem for elementary geometric figures such as lines, rings, squares, rectangles, and cubes, minimal-time solutions are known. However, in 2012 Umeo and Kubo introduced a very simple variation of this type and pointed out that its minimal-time solutions are unknown. In that variation, a problem instance is a square array of n columns and n rows and the position of the general is arbitrary. For this variation they constructed a solution that fires at time 2n-2 for any position of the general and wrote that it is not known whether this solution is minimal-time or not. We determine the exact value of the minimum firing time of this variation. For some problem instances this value is smaller than 2n-2 and hence the 2n-2 time solution is not minimal-time. Our result does not solve the problem of existence or non-existence of minimal-time solutions of the variation. However the result gives one necessary condition for solutions to be minimal-time. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03043975
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 97295046
- Full Text :
- https://doi.org/10.1016/j.tcs.2014.06.016