On strong consistency of the fuzzy generalized nearest neighbor rule

The k nearest neighbor rule (k-NNR) is a well-known nonparametric decision rule in pattern classification. Fuzzy set theory has been widely used to represent the uncertainty of class membership. Several researchers extended conventional k-NNR to fuzzy k-NNR, such as Bezdek et al. [Fuzzy Sets and Systems 18 (1986) 237–256], Keller et al. [IEEE Trans. Syst. Man, and Cybern. 15(4) (1985) 580–585], Béreau and Dubuisson [Fuzzy Sets and Systems 44 (1991) 17–32]. In this paper, we describe a fuzzy generalized k-NN algorithm. This algorithm is a unified approach to a variety of fuzzy k-NNR's. Then we create the strong consistency of posterior risk of the fuzzy generalized NNR.     

Lower bounds for the size in four families of minimum broadcast graphs

In this paper, we give a lower bound for the size B(n) of a minimum broadcast graph of order n = 2^k − 4, 2^k − 6, 2^k − 5 or 2^k − 3 which is shown to be accurate in the cases when k = 5 and k = 6. This result provides, together with an upper bound obtained by a construction given in Bermond et al. (1992), an estimation of the value B(n) for n = 2^k − 4.     

On approximation intractability of the path–distance–width problem

Path–distance–width of a graph G=(V,E), denoted by pdw(G), is the minimum integer k satisfying that there is a nonempty subset of SV such that the number of the nodes with distance i from S is at most k for any nonnegative integer i. It is known that given a positive integer k and a graph G, the decision problem pdw(G)k is NP-complete even if G is a tree (Yamazaki et al. Lecture Notes in Computer Science, vol. 1203, Springer, Berlin, 1997, pp. 276–287). In this paper, we show that it is NP-hard to approximate the path–distance–width of a graph within a ratio for any >0, even for trees.     

ContributionsFinitary bases and formal generating functions

Let k be a nonzero, commutative ring with 1, and let R be a k-algebra with a countably-infinite ordered free k-basis B = [p_n: n 0]. We characterize and analyze those bases from which one can construct a k-algebra of ‘formal B-series’ of the form f=∑c_n p_n, with c_n ε k, showing inter alia that many classical polynomial bases fail to have this property.     

On isometries of matrix spaces

Let A_kbe the group of isometries of the space of n-by-n matrices over reals (resp. complexes, quaternions) with respect to the Ky Fan k-norm (see the Introduction for the definitions). Let Γ⁰ be the group of transformations of this space consisting of all products of left and right multiplications by the elements of SO(n)(resp. U(n), Sp(n)). It is shown that, except for three particular casesA_k coincides with the normalizer of Γ in Δ group of isometries of the above matrix space with respect to the standard inner product. We also give an alternative treatment of the case D = Rn = 4k = 2 which was studied in detail by Johnson, Laffey, and Li [4].     

Multicolor Combination Lemma

We present an extension of the Combination Lemma of Guibas et al. (1983) that expresses the complexity of one or several faces in the overlay of many arrangements (as opposed to just two arrangements in (Guibas et al. 1989)), as a function of the number of arrangements, the number of faces, and the complexities of these faces in the separate arrangements. Several applications of the new Combination Lemma are presented. We first show that the complexity of a single face in an arrangement of k simple polygons with a total of n sides is Θ(n(k)), where (·) is the inverse of Ackermann's function. We also give a new and simpler proof of the bound on the total number of edges of m faces in an arrangement of n Jordan arcs, each pair of which intersect in at most s points, where λ_s(n) is the maximum length of a Davenport–Schinzel sequence of order s with n symbols. We extend this result, showing that the total number of edges of m faces in a sparse arrangement of n Jordan arcs is , where w is the total complexity of the arrangement. Several other related results are also obtained.     

Choosability of planar graphs

A graph G = G(V, E) with lists L(v), associated with its vertices v V, is called L-list colourable if there is a proper vertex colouring of G in which the colour assigned to a vertex v is chosen from L(v). We say G is k-choosable if there is at least one L-list colouring for every possible list assignment L with L(v) = k v V(G).

Now, let an arbitrary vertex v of G be coloured with an arbitrary colour f of L(v). We investigate whether the colouring of v can be continued to an L-list colouring of the whole graph. G is called free k-choosable if such an L-list colouring exists for every list assignment L (L(v) = k v V(G)), every vertex v and every colour f L(v). We prove the equivalence of the well-known conjecture of Erd s et al. (1979): “Every planar graph is 5-choosable” with the following conjecture: “Every planar graph is free 5-choosable”.     

Order shattering and Wilson''s theorem

The notion of order shattering was introduced in Anstee et al. (Graphs Combin. 18 (2002) 59–73). Here, we pursue further the algebraic interpretation that was established there. With this tool we give a new proof and a generalization for Wilson's theorem on the diagonal form for the incidence matrices of t-subsets vs. k-subsets (European J. Combin. 11 (1990) 609–615). This allows a generalization of the corresponding rank formula modulo p, where p is an arbitrary prime.     

3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects

We present a new data structure for a set of n convex simply-shaped fat objects in the plane, and use it to obtain efficient and rather simple solutions to several problems including (i) vertical ray shooting—preprocess a set of n non-intersecting convex simply-shaped flat objects in 3-space, whose xy-projections are fat, for efficient vertical ray shooting queries, (ii) point enclosure—preprocess a set C of n convex simply-shaped fat objects in the plane, so that the k objects containing a query point p can be reported efficiently, (iii) bounded-size range searching— preprocess a set C of n convex fat polygons, so that the k objects intersecting a “not-too-large” query polygon can be reported efficiently, and (iv) bounded-size segment shooting—preprocess a set C as in (iii), so that the first object (if exists) hit by a “not-too-long” oriented query segment can be found efficiently. For the first three problems we construct data structures of size O(λ_s(n)log³n), where s is the maximum number of intersections between the boundaries of the (xy-projections) of any pair of objects, and λ_s(n) is the maximum length of (n, s) Davenport-Schinzel sequences. The data structure for the fourth problem is of size O(λ_s(n)log²n). The query time in the first problem is O(log⁴n), the query time in the second and third problems is O(log³n + klog²n), and the query time in the fourth problem is O(log³n).

We also present a simple algorithm for computing a depth order for a set as in (i), that is based on the solution to the vertical ray shooting problem. (A depth order for , if exists, is a linear order of , such that, if K₁, K₂ and K₁ lies vertically above K₂, then K₁ precedes K₂.) Unlike the algorithm of Agarwal et al. (1995) that might output a false order when a depth order does not exist, the new algorithm is able to determine whether such an order exists, and it is often more efficient in practical situations than the former algorithm.     

Precoloring extension. I. Interval graphs

This paper is the first article in a series devoted to the study of the following general problem on vertex colorings of graphs. Suppose that some vertices of a graph G are assigned to some colors. Can this ‘precoloring’ be extended to a proper coloring of G with at most k colors (for some given k)? This question was motivated by practical problems in scheduling and VLSI theory. Here we investigate its complexity status for interval graphs and for graphs with a bounded treewidth.     

k-Subdomination in graphs

For a positive integer k, a k-subdominating function of a graph G=(V,E) is a function f : V→{−1,1} such that ∑_uNG[v]f(u)1 for at least k vertices v of G. The k-subdomination number of G, denoted by γ_ks(G), is the minimum of ∑_vVf(v) taken over all k-subdominating functions f of G. In this article, we prove a conjecture for k-subdomination on trees proposed by Cockayne and Mynhardt. We also give a lower bound for γ_ks(G) in terms of the degree sequence of G. This generalizes some known results on the k-subdomination number γ_ks(G), the signed domination number γ_s(G) and the majority domination number γ_maj(G).     

A special k-coloring for a connected k-chromatic graph

For each positive integer k we consider the smallest positive integer f(k) (dependent only on k) such that the following holds: Each connected graph G with chromatic number χ(G) = k can be properly vertex colored by k colors so that for each pair of vertices x_o and x_p in any color class there exist vertices x₁, x₂, …, x_p-1 of the same class with dist(x_i, x_i+1) f(k) for each i, 0 i p − 1. Thus, the graph is k-colorable with the vertices of each color class placed throughout the graph so that no subset of the class is at a distance > f(k) from the remainder of the class.

We prove that f(k) < 12k when the order of the graph is k(k − 2) + 1.     

Triangular range counting query in 2D and its application in finding k nearest neighbors of a line segment

We present an efficient algorithm for finding k nearest neighbors of a query line segment among a set of points distributed arbitrarily on a two dimensional plane. Along the way to finding this algorithm, we have obtained an improved triangular range searching technique in 2D. Given a set of n points, we preprocess them to create a data structure using O(n²) time and space, such that given a triangular query region Δ, the number of points inside Δ can be reported in O(logn) time. Finally, this triangular range counting technique is used for finding k nearest neighbors of a query straight line segment in O(log²n+k) time.     

A theorem on independence

Suppose we are given a family of sets , where S(j) = ∩^k_i=1 H_i(j), and suppose each collection of sets H_i(j₁),…,H_i(j_k+1) has a lower bound under the partial ordering defined by inclusion, then the maximal size of an independent subcollection of is k. For example, for a fixed collection of half-spaces H₁,…,H_k in , we define to be the collection of all sets of the form

where χ_i, I=1,…, k are points in . Then the maximal size of an independent collection of such sets us k. This leads to a proof of the bound of 2d due to Rényi et al. (1951) for the maximum size of an independent family of rectangles in with sides parallel to the coordinate axes, and to a bound of d+1 for the maximum size of an independent family of simplices in with sides parallel to given hyperplanes H₁,…,H_d+1.     

Between local and global logarithmic averages

We obtain an approximation for the logarithmic averages of I{k^1/2a(k) S(k) k^1/2b(k)}, where a(k) → 0, b(k) → 0 (k → ∞) and S(k) is partial sum of independent, identically distributed random variables.     

Acyclic coloring of graphs without bichromatic long path

Let G be a graph of maximum degree Δ. A proper vertex coloring of G is acyclic if there is no bichromatic cycle. It was proved by Alon et al. [Acyclic coloring of graphs. Random Structures Algorithms, 1991, 2(3): 277−288] that G admits an acyclic coloring with O(Δ^4/3) colors and a proper coloring with O(Δ^{(k−1)/(k−2)}) colors such that no path with k vertices is bichromatic for a fixed integer k≥5. In this paper, we combine above two colorings and show that if k≥5 and G does not contain cycles of length 4, then G admits an acyclic coloring with O(Δ^{(k−1)/(k−2)}) colors such that no path with k vertices is bichromatic.     

Security of a key agreement protocol based on chaotic maps

Kacorev et al. proposed new public key encryption scheme using chaotic maps. Subsequently, Bergamo et al. has broken Kacorev and Tasev’s encryption scheme and then applied the attack on a key agreement protocol based on Kacorev et al.’s system. In order to address Bergamo et al.’ attack, Xiao et al. proposed a novel key agreement protocol. In this paper, we will present two attacks on Xiao et al.’s key agreement protocol using chaotic maps. Our new attack method is different from the one that Bergamo et al. developed. The proposed attacks work in a way that an adversary can prevent the user and the server from establishing a shared session key even though the adversary cannot get any private information from the user and the server’s communications.     

Resolutions of Stanley-Reisner rings and Alexander duality

Associated to any simplicial complex Δ on n vertices is a square-free monomial ideal I_Δ in the polynomial ring A = k[x₁, …, x_n], and its quotient k[Δ] = A/I_Δ known as the Stanley-Reisner ring. This note considers a simplicial complex Δ^* which is in a sense a canonical Alexander dual to Δ, previously considered in [1, 5]. Using Alexander duality and a result of Hochster computing the Betti numbers dim_k Tor_i^A (k[Δ],k), it is shown (Proposition 1) that these Betti numbers are computable from the homology of links of faces in Δ^*. As corollaries, we prove that I_Δ has a linear resolution as A-module if and only if Δ^* is Cohen-Macaulay over k, and show how to compute the Betti numbers dim_k Tor_i^A (k[Δ],k) in some cases where Δ^* is wellbehaved (shellable, Cohen-Macaulay, or Buchsbaum). Some other applications of the notion of shellability are also discussed.     

Extending shelling orders and a hierarchy of functions of unimodal simple polytopes

Let P be a simplicial d-polytope with n facets ((d − 1)-dimensional faces) in R^d. A shelling of P is an ordering of the facets of P such that the intersection of each facet F with the union of all facets that precede it the ordering is a nonempty union of (d − 2)-faces of F. The following open question was raised by Tverberg and is recorded in [4]. Suppose for some k < n, there is an ordering of k of the facets of P so that the intersection of each of these facets with the union of all of the facets that precede it in the ordering is a nonempty union of (d − 2)-faces. Can this initial “segment” be extended to a shelling of all the facets? This question is open even in the case that P is the dual of the d-dimensional hypercube. The question in this case has resurfaced several times since G. Danaraj and V. Klee (1978) in a variety of forms. It is related to the hierarchies of completely unimodal pseudo-Boolean functions studied in P.L. Hammer et al. (1988), the author (1988) and D. Wiedemann (1986). (A pseudo-Boolean function is a function mapping the vertices of the d-dimensional hypercube into the reals). In this paper, the hierarchies are compared and combined. This hierarchy is then extended to general simple polytopes, and the relationship to the above open question is explained.     

A doubly cyclic channel assignment problem

A standard model for radio channel assignment involves a set V of sites, the set {0,1,2,…} of channels, and a constraint matrix (w(u, v)) specifying minimum channel separations. An assignment f:V→{0,1,2,…} is feasible if the distance f(u) − f(v)w(u, v) for each pair of sites u and v. The aim is to find the least k such that there is a feasible assignment using only the k channels 0, 1, …, k − 1, and to find a corresponding optimal assignment.

We consider here a related problem involving also two cycles. There is a given cyclic order τ on the sites, and feasible assignments f must also satisfy f(τv) f(v) for all except one site v. Further, the channels are taken to be evenly spaced around a circle, so that if the k channels 0, 1, …, k − 1 are available then the distance between channels i and j is the minimum of ¦i − j¦ and k − ¦i − j¦. We show how to find a corresponding optimal channel assignment in O(¦V¦³) steps.