Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874188 | Information Processing Letters | 2018 | 8 Pages |
Abstract
An identifying code in a graph is a subset of vertices having a nonempty and distinct intersection with the closed neighborhood of every vertex. We prove that the infimum density of any identifying code in Sk (an infinite strip of k rows in the square grid) can always be achieved by a periodic identifying code with pattern length at most 24k. Assisted by a compute program implementing Karp's algorithm for minimum cycle mean, we find a periodic identifying code in S4 with the minimum density 11/28, and a periodic identifying code in S5 with the minimum density 19/50.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Minghui Jiang,