Super restricted edge connected Cartesian product graphs

An edge-cut F of a connected graph G is called a restricted edge-cut if G−F contains no isolated vertices. The minimum cardinality of all restricted edge-cuts is called the restricted edge-connectivity λ^′(G) of G. A graph G is said to be λ^′-optimal if λ^′(G)=ξ(G), where ξ(G) is the minimum edge-degree of G. A graph is said to be super-λ^′ if every minimum restricted edge-cut isolates an edge. This article gives a sufficient condition for Cartesian product graphs to be super-λ^′. Using this result, certain classes of networks which are recursively defined by the Cartesian product can be simply shown to be super-λ^′.     

Super connectivity of line graphs

The super connectivity κ^′ and the super edge-connectivity λ^′ are more refined network reliability indices than connectivity κ and edge-connectivity λ. This paper shows that for a connected graph G with order at least four rather than a star and its line graph L(G), κ^′(L(G))=λ^′(G) if and only if G is not super-λ^′. As a consequence, we obtain the result of Hellwig et al. [Note on the connectivity of line graphs, Inform. Process. Lett. 91 (2004) 7] that κ(L(G))=λ^′(G). Furthermore, the authors show that the line graph of a super-λ^′ graph is super-λ if the minimum degree is at least three.     

Equitable and equitable list colorings of graphs

A proper k-vertex coloring of a graph is an equitable k-coloring if the sizes of the color classes differ by at most 1. A graph G is equitably k-choosable if, for any k-uniform list assignment L, G is L-colorable and each color appears on at most vertices. We prove in this paper that outerplane graphs are equitably k-choosable whenever k≥Δ, where Δ is the maximum degree. Moreover, we discuss equitable colorings of some d-degenerate graphs.     

On the hardness of finding near-optimal multicuts in directed acyclic graphs

Given an edge-weighted (di)graph and a list of source-sink pairs of vertices of this graph, the minimum multicut problem consists in selecting a minimum-weight set of edges (or arcs), whose removal leaves no path from each source to the corresponding sink. This is a well-known NP-hard problem, and improving several previous results, we show that it remains APX-hard in unweighted directed acyclic graphs (DAG), even with only two source-sink pairs. This is also true if we remove vertices instead of arcs.     

Threshold-based clustering with merging and regularization in application to network intrusion detection

Signature-based intrusion detection systems look for known, suspicious patterns in the input data. In this paper we explore compression of labeled empirical data using threshold-based clustering with regularization. The main target of clustering is to compress training dataset to the limited number of signatures, and to minimize the number of comparisons that are necessary to determine the status of the input event as a result. Essentially, the process of clustering includes merging of the clusters which are close enough. As a consequence, we will reduce original dataset to the limited number of labeled centroids. In a complex with k-nearest-neighbor (kNN) method, this set of centroids may be used as a multi-class classifier. The experiments on the KDD-99 intrusion detection dataset have confirmed effectiveness of the above procedure.     

Sharing secrets in stego images with authentication

Recently, Lin and Tsai and Yang et al. proposed secret image sharing schemes with steganography and authentication, which divide a secret image into the shadows and embed the produced shadows in the cover images to form the stego images so as to be transmitted to authorized recipients securely. In addition, these schemes also involve their authentication mechanisms to verify the integrity of the stego images such that the secret image can be restored correctly. Unfortunately, these schemes still have two shortcomings. One is that the weak authentication cannot well protect the integrity of the stego images, so the secret image cannot be recovered completely. The other shortcoming is that the visual quality of the stego images is not good enough. To overcome such drawbacks, in this paper, we propose a novel secret image sharing scheme combining steganography and authentication based on Chinese remainder theorem (CRT). The proposed scheme not only improves the authentication ability but also enhances the visual quality of the stego images. The experimental results show that the proposed scheme is superior to the previously existing methods.     

Small-sample comparisons of confidence intervals for the difference of two independent binomial proportions

This paper compares the exact small-sample achieved coverage and expected lengths of five methods for computing the confidence interval of the difference of two independent binomial proportions. We strongly recommend that one of these be used in practice. The first method we compare is an asymptotic method based on the score statistic (AS) as proposed by Miettinen and Nurminen [1985. Comparative analysis of two rates. Statist. Med. 4, 213-226.]. Newcombe [1998. Interval estimation for the difference between independent proportions: comparison of seven methods. Statist. Med. 17, 873-890.] has shown that under a certain asymptotic set-up, confidence intervals formed from the score statistic perform better than those formed from the Wald statistic (see also [Farrington, C.P., Manning, G., 1990. Test statistics and sample size formulae for comparative binomial trials with null hypothesis of non-zero risk difference or non-unity relative risk. Statist. Med. 9, 1447-1454.]). The remaining four methods compared are the exact methods of Agresti and Min (AM), Chan and Zhang (CZ), Coe and Tamhane (CT), and Santner and Yamagami (SY). We find that the CT has the best small-sample performance, followed by AM and CZ. Although AS is claimed to perform reasonably well, it performs the worst in this study; about 50% of the time it fails to achieve nominal coverage even with moderately large sample sizes from each binomial treatment.     

Computation, approximation and stability of explicit feedback min-max nonlinear model predictive control

This paper presents an approximate multi-parametric Nonlinear Programming (mp-NLP) approach to explicit solution of feedback min-max NMPC problems for constrained nonlinear systems in the presence of bounded disturbances and/or parameter uncertainties. It is based on an orthogonal search tree structure of the state space partition and consists in constructing a piecewise nonlinear (PWNL) approximation to the optimal sequence of feedback control policies. Conditions guaranteeing the robust stability of the closed-loop system in terms of a finite l₂-gain are derived.     

Channel assignment via fast zeta transform

We show an O^?(n(?+1))-time algorithm for the channel assignment problem, where ? is the maximum edge weight. This improves on the previous O^?(n(?+2))-time algorithm by Král (2005) [1], as well as algorithms for important special cases, like L(2,1)-labeling. For the latter problem, our algorithm works in O^?(n³) time. The progress is achieved by applying the fast zeta transform in combination with the inclusion-exclusion principle.     

Distinct squares in run-length encoded strings

Squares are strings of the form ww where w is any nonempty string. Two squares ww and w^′w^′ are of different types if and only if w≠w^′. Fraenkel and Simpson [Avieri S. Fraenkel, Jamie Simpson, How many squares can a string contain? Journal of Combinatorial Theory, Series A 82 (1998) 112-120] proved that the number of square types contained in a string of length n is bounded by O(n). The set of all different square types contained in a string is called the vocabulary of the string. If a square can be obtained by a series of successive right-rotations from another square, then we say the latter covers the former. A square is called a c-square if no square with a smaller index can cover it and it is not a trivial square. The set containing all c-squares is called the covering set. Note that every string has a unique covering set. Furthermore, the vocabulary of the covering set are called c-vocabulary. In this paper, we prove that the cardinality of c-vocabulary in a string is less than , where N is the number of runs in this string.     

Construction of marginally and conditionally restricted designs using multiplicative algorithms

The problem of constructing optimal designs when some of the factors are not under the control of the experimenters is considered. Their values can be known or unknown before the experiment is carried out. Several criteria are taken into consideration to find optimal conditional designs given some prior information on the factors. In order to determine these optimal conditional designs a class of multiplicative algorithms is provided. Optimal designs are computed for illustrative, but simplistic, examples. Two real life problems in production models and a physical test for predicting morbidity in lung cancer surgery motivate the procedures provided.     

Some new sequence spaces derived by the domain of the triple band matrix

Let λ denote any of the classical spaces ?_∞,c,c₀, and ?_p of bounded, convergent, null, and absolutely p-summable sequences, respectively, and let λ(B) also be the domain of the triple band matrix B(r,s,t) in the sequence space λ, where 1<p<∞. The present paper is devoted to studying the sequence space λ(B). Furthermore, the β- and γ-duals of the space λ(B) are determined, the Schauder bases for the spaces c(B), c₀(B), and ?_p(B) are given, and some topological properties of the spaces c₀(B), ?₁(B), and ?_p(B) are examined. Finally, the classes (λ₁(B):λ₂) and (λ₁(B):λ₂(B)) of infinite matrices are characterized, where λ₁∈{?_∞,c,c₀,?_p,?₁} and λ₂∈{?_∞,c,c₀,?₁}.     

Relationship between the eccentric connectivity index and Zagreb indices

For a (molecular) graph, the first Zagreb index M₁ is equal to the sum of the squares of the degrees of the vertices, and the second Zagreb index M₂ is equal to the sum of the products of the degrees of pairs of adjacent vertices. If G is a connected graph with vertex set V(G), then the eccentric connectivity index of G, ξ^C(G), is defined as, ∑_vi∈V(G)d_ie_i, where d_i is the degree of a vertex v_i and e_i is its eccentricity. In this report we compare the eccentric connectivity index (ξ^C) and the Zagreb indices (M₁ and M₂) for chemical trees. Moreover, we compare the eccentric connectivity index (ξ^C) and the first Zagreb index (M₁) for molecular graphs.     

A model reference approach to safe controller changes in iterative identification and control

A controller change from a current controller which stabilises the plant to a new controller, designed on the basis of an approximate model of the plant and with guaranteed bounds on the stability properties of the true closed loop, is called a safe controller change. In this paper, we present a model reference approach to the determination of safe controller changes on the basis of approximate closed loop models of the plant and robust stability results in the ν-gap.     

On relational possibilistic clustering

This paper initially describes the relational counterpart of possibilistic c-means (PCM) algorithm, called relational PCM (or RPCM). RPCM is then improved to better handle arbitrary dissimilarity data. First, a re-scaling of the PCM membership function is proposed in order to obtain zero membership values when the distance to prototype equals the maximum value allowed in bounded dissimilarity measures. Second, a heuristic method of reference distance initialisation is provided which diminishes the known PCM tendency of producing coincident clusters. Finally, RPCM improved with our initialisation strategy is tested on both synthetic and real data sets with satisfactory results.     

A necessary and sufficient condition for parameter insensitive disturbance-rejection problem with state feedback

In this paper a necessary and sufficient condition for a parameter insensitive disturbance-rejection problem with state feedback which was pointed out as an open problem by Bhattacharyya to be solvable is proved. A constructive algorithm of simultaneously (A,B)-invariant subspaces for a finite-number of linear systems and a relationship between simultaneously (A,B)-invariant subspaces and generalized (A,B)-invariant subspaces play an important role to prove the main result.     

A novel and quick SVM-based multi-class classifier

Use different real positive numbers p_i to represent all kinds of pattern categories, after mapping the inputted patterns into a special feature space by a non-linear mapping, a linear relation between the mapped patterns and numbers p_i is assumed, whose bias and coefficients are undetermined, and the hyper-plane corresponding to zero output of the linear relation is looked as the base hyper-plane. To determine the pending parameters, an objective function is founded aiming to minimize the difference between the outputs of the patterns belonging to a same type and the corresponding p_i, and to maximize the distance between any two different hyper-planes corresponding to different pattern types. The objective function is same to that of support vector regression in form, so the coefficients and bias of the linear relation are calculated by some known methods such as SVM^light approach. Simultaneously, three methods are also given to determine p_i, the best one is to determine them in training process, which has relatively high accuracy. Experiment results of the IRIS data set show that, the accuracy of this method is better than those of many SVM-based multi-class classifiers, and close to that of DAGSVM (decision-directed acyclic graph SVM), emphatically, the recognition speed is the highest.     

Cubic structures applied to ideals of BCI-algebras

The notions of cubic a-ideals and cubic p-ideals are introduced, and several related properties are investigated. Characterizations of a cubic a-ideal are established. Relations between cubic p-ideals, cubic a-ideals and cubic q-ideals are discussed. The cubic extension property of a cubic a-ideal is discussed.     

A comparison of design and model selection methods for supersaturated experiments

Various design and model selection methods are available for supersaturated designs having more factors than runs but little research is available on their comparison and evaluation. Simulated experiments are used to evaluate the use of E(s²)-optimal and Bayesian D-optimal designs and to compare three analysis strategies representing regression, shrinkage and a novel model-averaging procedure. Suggestions are made for choosing the values of the tuning constants for each approach. Findings include that (i) the preferred analysis is via shrinkage; (ii) designs with similar numbers of runs and factors can be effective for a considerable number of active effects of only moderate size; and (iii) unbalanced designs can perform well. Some comments are made on the performance of the design and analysis methods when effect sparsity does not hold.