identifying code is a concept in information theory and can be applied to problems of fault detection and location detection. In this paper, by assigning cost to every code word, we propose an optimization problem to ...
详细信息
identifying code is a concept in information theory and can be applied to problems of fault detection and location detection. In this paper, by assigning cost to every code word, we propose an optimization problem to find an identifying code with minimum cost and formulate the problem by an integer program. We generalize the results to the robust identifying code problem, which is proposed for poor environments. A tailored genetic algorithm is provided to solve the problem, and the experimental result shows that it is competitive for large-scale problems.
We study geometric variations of the discriminating code problem. In the discrete version of the problem, a finite set of points P and a finite set of objects S are given in R-d. The objective is to choose a subset S*...
详细信息
We study geometric variations of the discriminating code problem. In the discrete version of the problem, a finite set of points P and a finite set of objects S are given in R-d. The objective is to choose a subset S*subset of S of minimum cardinality such that for each point pi E P, the subset Si*subset of S* covering pi satisfies Si*not equal 0, and each pair p(i), p(j) is an element of P, i not equal j, we have S-i* not equal S-j*. In the continuous version of the problem, the solution set S* can be chosen freely among a (potentially infinite) class of allowed geometric objects. In the 1-dimensional case (d = 1), the points in P are placed on a horizontal line L, and the objects in S are finite-length line segments aligned with L (called intervals). We show that the discrete version of this problem is NP-complete. This is somewhat surprising as the continuous version is known to be polynomial time solvable. This is also in contrast with most geometric covering problems, which are usually polynomial-time solvable in one dimension. Still for the 1-dimensional discrete version, we design a polynomial-time 2-approximation algorithm. We also design a PTAS for both discrete and continuous versions in one dimension, for the restriction where the intervals are all required to have the same length. We then study the 2-dimensional case (d = 2) for axis-parallel unit square objects. We show that both continuous and discrete versions are NP-complete, and design polynomial-time approximation algorithms that produce (16 center dot O PT +1)-approximate and (64 center dot O PT + 1)-approximate solutions respectively, using rounding of suitably defined integer linear programming problems. Finally, we apply our techniques to a related variant of the discrete problem, where instead of points and geometric objects we just have a set S of objects. The goal is to select a small subset S* of objects so that all objects of S are discriminated by their intersection with the objects of S*
For a graph, G, and a vertex v is an element of V (G), let N vertical bar v vertical bar be the set of vertices adjacent to and including v. A set D subset of V (G) is a (vertex) identifying code if for any two distin...
详细信息
For a graph, G, and a vertex v is an element of V (G), let N vertical bar v vertical bar be the set of vertices adjacent to and including v. A set D subset of V (G) is a (vertex) identifying code if for any two distinct vertices v(1), v(2) is an element of V (G), the vertex sets N vertical bar v(1)vertical bar boolean AND D and N vertical bar v(2)vertical bar boolean AND D are distinct and non-empty. We consider the minimum density of a vertex identifying code for the infinite hexagonal grid. In 2000, Cohen et al. constructed two codes with a density of 3/7 approximate to 0.428571, and this remains the best known upper bound. Until now, the best known lower bound was 12/29 approximate to 0.413793 and was proved by Cranston and Yu in 2009. We present three new codes with a density of 3/7, and we improve the lower bound to 5/1 approximate to 0.416667. (C) 2013 Elsevier B.V. All rights reserved.
An r-identifying code in a graph G = (V, E) is a subset C subset of V such that for each u is an element of V the intersection of C and the ball of radius r centered at u is nonempty and unique. Previously, r-identify...
详细信息
An r-identifying code in a graph G = (V, E) is a subset C subset of V such that for each u is an element of V the intersection of C and the ball of radius r centered at u is nonempty and unique. Previously, r-identifying codes have been studied in various grids. In particular, it has been shown that there exists a 2-identifying code in the square grid with density 5/29 approximate to 0.172 and that there are no 2-identifying codes with density smaller than 3/20 = 0.15. Recently, the lower bound has been improved to 6/37 approximate to 0.162 by Martin and Stanton (2010) [11]. In this paper, we further improve the lower bound by showing that there are no 2-identifying codes in the square grid with density smaller than 6/35 approximate to 0.171. (C) 2013 Elsevier B.V. All rights reserved.
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) boolean AND S and B(v) boolea...
详细信息
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) boolean AND S and B(v) boolean AND S are nonempty and distinct. A minimum identifying code of a graph G is an identifying code of G with minimum cardinality and M(C) is the cardinality of a minimum identifying code for G. A minimum identifying code graph G of order n is a graph with M(G) = inverted right perpendicularlog(2)(n + 1)inverted left perpendicular having the minimum number of edges. Moncel (2006) [5] constructed minimum identifying code graphs of order 2(m) - 1 for m >= 2 and left the same problem but for arbitrary order open. In this paper, we aimed at the construction of connected minimum identifying code graphs in order to solve this problem for integer order greater than or equal to 4. Furthermore, we discussed some related properties. (C) 2012 Elsevier B.V. All rights reserved.
The watching system, as a generalization of identifying code, has been defined by Auger in 2010. The identifying code has been used to wireless networks and it has been also applied to locate objects in the sensor net...
详细信息
The watching system, as a generalization of identifying code, has been defined by Auger in 2010. The identifying code has been used to wireless networks and it has been also applied to locate objects in the sensor networks. On the other hand, the graph product is employed in most of the mathematic branches such as network design to study the structure of network elements. In this paper, we give some upper bounds for the watching number of well-know product graphs. (C) 2020 Elsevier Inc. All rights reserved.
The problems of determining minimum identifying, locating-dominating, open locating-dominating or locating total-dominating codes in a graph G are variations of the classical minimum dominating set problem in G and ar...
详细信息
The problems of determining minimum identifying, locating-dominating, open locating-dominating or locating total-dominating codes in a graph G are variations of the classical minimum dominating set problem in G and are all known to be hard for general graphs. A typical line of attack is therefore to determine the cardinality of minimum such codes in special graphs. In this work we study the change of minimum such codes under three operations in graphs: adding a universal vertex, taking the generalized corona of a graph, and taking the square of a graph. We apply these operations to paths and cycles which allows us to provide minimum codes in most of the resulting graph classes.
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 o...
详细信息
ISBN:
(纸本)9781450360944
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.
The problems of determining minimum identifying, locating-dominating, open locating-dominating or locating total-dominating codes in a graph G are variations of the classical minimum dominating set problem in G and ar...
详细信息
The problems of determining minimum identifying, locating-dominating, open locating-dominating or locating total-dominating codes in a graph G are variations of the classical minimum dominating set problem in G and are all known to be hard for general graphs. A typical line of attack is therefore to determine the cardinality of minimum such codes in special graphs. In this work we study the change of minimum such codes under three operations in graphs: adding a universal vertex, taking the generalized corona of a graph, and taking the square of a graph. We apply these operations to paths and cycles which allows us to provide minimum codes in most of the resulting graph classes.
Assume that a graph G$$ G $$ models a detection system for a facility with a possible "intruder," or a multiprocessor network with a possible malfunctioning processor. We consider the problem of placing dete...
详细信息
Assume that a graph G$$ G $$ models a detection system for a facility with a possible "intruder," or a multiprocessor network with a possible malfunctioning processor. We consider the problem of placing detectors at a subset of vertices in G$$ G $$ to determine the location of an intruder if there is any. Many types of detection systems have been defined for different sensor capabilities;in particular, we focus on identifying codes, where each detector can determine whether there is an intruder within its closed neighborhood. In this research we explore a fault-tolerant variant of identifying codes applicable to real-world systems. Specifically, error-detecting identifying codes permit a false-negative transmission from any single detector. We investigate minimum-sized error-detecting identifying codes in several classes of graphs, including cubic graphs and infinite grids, and show that the problem of determining said minimum size in arbitrary graphs is NP-complete.
暂无评论