On upper and lower bounds of identifying code set for soccer ball graph with application to satellite deployment
Authors: 
Arunabha Sen, Victoria H. Goliber, Kaustav Basu, Chenyang Zhou, Sumitava GhoshAuthors Info & Claims
Pages 307 - 316
Abstract
We study a monitoring problem on the surface of the earth for significant environmental, social/political and extreme events using satellites as sensors. We assume that the surface of the earth is divided into a set of regions, where a region may be a continent, a country, or a set of neighboring countries. We also assume that, the impact of a significant event spills into neighboring regions and there will be corresponding indicators of such events. Careful deployment of sensors, utilizing Identifying Codes, can ensure that even though the number of deployed sensors is fewer than the number of regions, it may be possible to uniquely identify the region where the event has taken place. We assume that an event is confined to a region. As Earth is almost a sphere, we use a soccer ball (a sphere) as a model. From the model, we construct a Soccer Ball Graph (SBG), and show that the SBG has at least 26 sets of Identifying Codes of cardinality ten, implying that there are at least 26 different ways to deploy ten satellites to monitor the Earth. Finally, we also show that the size of the minimum Identifying Code for the SBG is at least nine.
References
[1]
Karpovsky, G. M., Chakraborty, K. Levitin, L. B. : On a New Class of Codes for Identifying Vertices in Graphs. IEEE Transactions on Information Theory. 44, 2 (1998)
[2]
Laifenfeld, M., Trachtenburg, A. : Identifying Codes and Covering Problems. IEEE Transactions on Information Theory. 54 (2008)
[3]
Laifenfeld, M., Trachtenburg, A., Cohen, R., Starobinski, D. : Joint Monitoring and Routing in Wireless Sensor Networks Using Robust Identifying Codes. Mobile Network Application. 14 (2009)
[4]
Ray, S., Starobinski, D., Trachtenburg, A., Ungrangsi, R. : Robust Location Detection in Emergency Sensor Networks. IEEE J. Selected Areas of Communication. (2004)
[5]
Charon, I., Hudry, O., Lobstein, A. : Identifying and Locating-Dominating Codes: NP-Completeness Results for Directed Graphs. IEEE Transactions on Information Theory. 48 (2002)
[6]
Charon, I., Hudry, O., Lobstein, A.: Minimizing The Size of an Identifying or Locating-Dominating Code in a Graph is NP-Hard. Theoretical Comp. Science. 290 (2003)
[7]
Xiao, Y., Hadjicostis, C., Thulasiraman, K. : The d-Identifying Codes for Problem for Vertex Identification in Graphs: Probabilistic Analysis and an Approximation Algorithm. Computing and Combinatorics. 4112 (2006).
[8]
Suomela, J. : Approximability of Identifying Codes and Locating-Dominating Codes. Inf. Process. Letters. 103 (2007)
[9]
Auger, D. : Minimal Identifying Codes in Trees and Planar Graphs with Large Girth. European Journal of Combinatorics. 31 (2010)
[10]
Kotschick, D. : The Topology and Combinatorics of Soccer Balls. American Scientist. Sigma XI Science Research Society. 94 (2006)
Recommendations
Analysis of satellite-induced factors affecting the accuracy of the BDS satellite differential code bias
Differential code bias (DCB) is one of the main error sources of the positioning, navigation and timing services and slant total electron content extraction. The DCB can usually be estimated together with ionospheric model coefficients from the data of ...
Revisiting and Improving Upper Bounds for Identifying Codes
An identifying code $C$ of a graph $G$ is a dominating set of $G$ such that any two distinct vertices of $G$ have distinct closed neighborhoods within $C$. These codes have been widely studied for over two decades. We give an improvement over all the best ...
The minimum identifying code graphs
Let G be a graph and B(u) be the set of u with all of its neighbors in G. A set S of vertices is called an identifying code of G if, for every pair of distinct vertices u and v, both B(u)@?S and B(v)@?S are nonempty and distinct. A minimum identifying ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
January 2019
535 pages
Copyright © 2019 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
- SIGOPS: ACM Special Interest Group on Operating Systems
- Indian Institute of Science: Indian Institute of Science
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 04 January 2019
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
ICDCN '19
Sponsor:
- SIGOPS
- Indian Institute of Science
ICDCN '19: International Conference on Distributed Computing and Networking
January 4 - 7, 2019
Bangalore, India
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 60Total Downloads
- Downloads (Last 12 months)4
- Downloads (Last 6 weeks)2
Reflects downloads up to 05 Mar 2025
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in