We introduce a game where players selfishly choose a resource and endure a cost depending on the number of players choosing nearby resources. We model the influences among resources by a weighted graph, directed or not. These games are generalizations of well-known games like Wardrop and congestion games. We study the conditions of equilibria existence and their efficiency if they exist. We conclude with studies of games whose influences among resources can be modelled by simple graphs.

A set C of vertices in a graph G = (V, E) is an identifying code if it is dominating and any two vertices of V are dominated by distinct sets of codewords. This paper presents a survey of Iiro Honkala’s contributions to the study of identifying codes with respect to several aspects: complexity of computing an identifying code, combinatorics in binary Hamming spaces, infinite grids, relationships between identifying codes and usual parameters in graphs, structural properties of graphs admitting identifying codes, and number of optimal identifying codes.

Let G=(V, A) be a directed, asymmetric graph and C a subset of vertices, and let B/sub r//sup -/(v) denote the set of all vertices x such that there exists a directed path from x to v with at most r arcs. If the sets B/sub r//sup -/(v) /spl cap/ C, v /spl isin/ V (respectively, v /spl isin/ V/spl bsol/C), are all nonempty and different, we call C an r-identifying code (respectively, an r-locating-dominating code) of G. In other words, if C is an r-identifying code, then one can uniquely identify a vertex v /spl isin/ V only by knowing which codewords belong to B/sub r//sup -/(v), and if C is r-locating-dominating, the same is true for the vertices v in V/spl bsol/C. We prove that, given a directed, asymmetric graph G and an integer k, the decision problem of the existence of an r-identifying code, or of an r-locating-dominating code, of size at most k in G, is NP-complete for any r/spl ges/1 and remains so even when restricted to strongly connected, directed, asymmetric, bipartite graphs or to directed, asymmetric, bipartite graphs without directed cycles.

Fault diagnosis of multiprocessor systems motivates the following graph-theoretic definition. A subset C of points in an undirected graph G=(V, E) is called an identifying code if the sets B(v)/spl cap/C consisting of all elements of C within distance one from the vertex v are different. We also require that the sets B(v)/spl cap/C are all nonempty. We take G to be the infinite square lattice with diagonals and show that the density of the smallest identifying code is at least 2/9 and at most 4/17.

We investigate the following problem: given two partitions of the Hamming space, their intersection matrix provides the cardinalities of the pairwise intersections of the subsets of these partitions. If we consider partitions by extended perfect codes, how many intersection matrices can we construct?.

In an undirected graph G=(V,E), a subset $C \subseteq V$ is called an identifying code if the sets $B_1(v) \cap C$ consisting of all elements of C within distance one from the vertex v are nonempty and different. We take G to be the infinite hexagonal grid and show that the density of any identifying code is at least 16/39 and that there is an identifying code of density 3/7.

The two problems subset sum and linear decoding (which have given birth to the knapsack and the McEliece public-key cryptosystems) are known to be NP-complete. For linear decoding, it has been proved that, even if one knows the linear code in advance and can preprocess it, the existence of a polynomial-time decoding algorithm would imply that the polynomial-time hierarchy collapses at an early stage. It is proved that the same holds for subset sum. Even if the knapsack is known in advance and can be preprocessed, there is no polynomial-time algorithm solving it, unless the polynomial hierarchy collapses. Also given is the sketch of a new, straightforward proof of this result for linear decoding.>

The authors extend to the q-ary case the notions of a normal code, a subnormal code, and the amalgamated direct sum construction, in order to investigate problems related to the covering radius of codes. For example, the authors prove that every nonbinary nontrivial perfect code is absubnormal. They also include some linear-programming lower bounds on ternary codes with covering radius 2 or 3.>

J. Astola (ibid., vol. IT-32, p.443-5, May 1986) constructed new binary perfect arithmetic codes considering the modular distance introduced by T.R.N. Rao and O.N. Garcia (1971). The commenter states that, if the modular distance defined by W.E. Clark and J.J. Liang (1973) is considered, these codes are no longer perfect.>

A number of upper and lower bounds are obtained forK(n, R), the minimal number of codewords in any binary code of lengthnand covering radiusR. Several new constructions are used to derive the upper bounds, including an amalgamated direct sum construction for nonlinear codes. This construction works best when applied to normal codes, and we give some new and stronger conditions which imply that a linear code is normal. An upper bound is given for the density of a covering code over any alphabet, and it is shown thatK(n + 2, R + 1) \leq K(n, R)holds for sufficiently largen.