A structure theorem for maximum internal matchings in graphs

A counterpart of the Gallai-Edmonds Structure Theorem is proved for matchings that are not required to cover the external vertices of graphs. The appropriate counterpart of Tutte's Theorem is derived from this result for the existence of perfect internal matchings in graphs.     

Conditional matching preclusion for the arrangement graphs

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings. In this paper we find this number and classify all optimal sets for the arrangement graphs, one of the most popular interconnection networks.     

Partition-distance: A problem and class of perfect graphs arising in clustering

Partitioning of a set of elements into disjoint clusters is a fundamental problem that arises in many applications. Different methods produce different partitions, so it is useful to have a measure of the similarity, or distance, between two or more partitions. In this paper we examine one distance measure used in a clustering application in computational genetics. We show how to efficiently compute the distance, and how this defines a new class of perfect graphs.     

On the stability number of the edge intersection of two graphs

Let G be the graph obtained as the edge intersection of two graphs G₁, G₂ on the same vertex set V. We show that if at least one of G₁, G₂ is perfect, then α(G)?α(G₁)·α(G₂), where α() is the cardinality of the largest stable set. Moreover, for general G₁ and G₂, we show that α(G)?R(α(G₁)+1,α(G₂)+1)−1, where R(k,?) is the Ramsey number.     

A bound on the number of integrators needed to linearize a control system

This paper considers the problem of dynamic feedback linearization for nonlinear control systems. For a restricted class of dynamic compensators that correspond to adding chains of integrators to the inputs, we give an upper bound on the order of the compensator that needs to be considered. In the case of 2-input systems, we show that this bound is sharp.     

A modified genetic algorithm approach for scheduling of perfect maintenance in distributed production scheduling

Distributed Scheduling (DS) problems have attracted attention by researchers in recent years. DS problems in multi-factory production are much more complicated than classical scheduling problems because they involve not only the scheduling problems in a single factory, but also the problems in the higher level, which is: how to allocate the jobs to suitable factories. It mainly focuses on solving two issues simultaneously: (i) allocation of jobs to suitable factories and (ii) determination of the corresponding production schedules in each factory. Its objective is to maximize system efficiency by finding an optimal plan for a better collaboration among various processes. However, in many papers, machine maintenance has usually been ignored during the production scheduling. In reality, every machine requires maintenance, which will directly influence the machine's availability, and consequently the planned production schedule. The objective of this paper is to propose a modified genetic algorithm approach to deal with those DS models with maintenance consideration, aiming to minimize the makespan of the jobs. Its optimization performance has been compared with other existing approaches to demonstrate its reliability. This paper also tests the influence of the relationship between the maintenance repairing time and the machine age to the performance of scheduling of maintenance during DS in the studied models.     

A note on the Hadwiger number of circular arc graphs

The intention of this note is to motivate the researchers to study Hadwiger's conjecture for circular arc graphs. Let η(G) denote the largest clique minor of a graph G, and let χ(G) denote its chromatic number. Hadwiger's conjecture states that η(G)?χ(G) and is one of the most important and difficult open problems in graph theory. From the point of view of researchers who are sceptical of the validity of the conjecture, it is interesting to study the conjecture for graph classes where η(G) is guaranteed not to grow too fast with respect to χ(G), since such classes of graphs are indeed a reasonable place to look for possible counterexamples. We show that in any circular arc graph G, η(G)?2χ(G)−1, and there is a family with equality. So, it makes sense to study Hadwiger's conjecture for this family.     

A long trip in the charming world of graphs for Pattern Recognition

This paper is a historical overview of graph-based methodologies in Pattern Recognition in the last 40 years; history is interpreted with the aim of recognizing the rationale inspiring the papers published in these years, so as to roughly classify them. Despite the extent of scientific production in this field, it is possible to identify three historical periods, each having its own connotation common to most of the corresponding papers, which are called here as the pure, the impure and extreme periods.     

Bounds for the 2-domination number of toroidal grid graphs

A k-dominating set for a graph G(V, E) is a set of vertices D? V such that every vertex v∈V\ D is adjacent to at least k vertices in D. The k-domination number of G, denoted by γ _k (G), is the cardinality of a smallest k-dominating set of G. Here we establish lower and upper bounds of γ _k (C _m ×C _n ) for k=2. In some cases, these bounds agree so that the exact 2-domination number is obtained.     

A fast heuristic based on spacefilling curves for minimum-weight matching in the plane

We present a heuristic to find a good matching on n points in the plane. It is essentially sorting and so runs in O(n log n) worst-case time and linear expected time. Its performance is competitive with that of previously suggested methods. However, it has the advantages of being trivial to code and of being indifferent to the choice of metric or the probability distribution from which the points are drawn.     

A new algorithm for resolution of the quadratic programming problem with fuzzy relation inequality constraints

The minimization problem of a quadratic objective function with the max-product fuzzy relation inequality constraints is studied in this paper. In this problem, its objective function is not necessarily convex. Hence, its Hessian matrix is not necessarily positive semi-definite. Therefore, we cannot apply the modified simplex method to solve this problem, in a general case. In this paper, we firstly study the structure of its feasible domain. We then use some properties of n × n real symmetric indefinite matrices, Cholesky’s decomposition, and the least square technique, and convert the problem to a separable programming problem. Furthermore, a relation in terms of a closed form is presented to solve it. Finally, an algorithm is proposed to solve the original problem. An application example in the economic area is given to illustrate the problem. Of course, there are other application examples in the area of digital data service and reliability engineering.     

A graphical test for the interval stability of fractional-delay systems

This paper investigates the BIBO (bounded input and bounded output) interval stability testing of fractional-delay systems, a problem of justifying the BIBO stability of a polytopic family of functions involving fractional-order powers as well as exponential powers. It proves that the BIBO stability of the polytope is governed by the BIBO stability of the edges of the polytope, and the latter can be tested graphically via frequency response plots. The main results generalize some results in the literature.     

Determination of the optimal number of features for quadratic discriminant analysis via the normal approximation to the discriminant distribution

Given the joint feature-label distribution, increasing the number of features always results in decreased classification error; however, this is not the case when a classifier is designed via a classification rule from sample data. Typically, for fixed sample size, the error of a designed classifier decreases and then increases as the number of features grows. The problem is especially acute when sample sizes are very small and the potential number of features is very large. To obtain a general understanding of the kinds of feature-set sizes that provide good performance for a particular classification rule, performance must be evaluated based on accurate error estimation, and hence a model-based setting for optimizing the number of features is needed. This paper treats quadratic discriminant analysis (QDA) in the case of unequal covariance matrices. For two normal class-conditional distributions, the QDA classifier is determined according to a discriminant. The standard plug-in rule estimates the discriminant from a feature-label sample to obtain an estimate of the discriminant by replacing the means and covariance matrices by their respective sample means and sample covariance matrices. The unbiasedness of these estimators assures good estimation for large samples, but not for small samples.Our goal is to find an essentially analytic method to produce an error curve as a function of the number of features so that the curve can be minimized to determine an optimal number of features. We use a normal approximation to the distribution of the estimated discriminant. Since the mean and variance of the estimated discriminant will be exact, these provide insight into how the covariance matrices affect the optimal number of features. We derive the mean and variance of the estimated discriminant and compare feature-size optimization using the normal approximation to the estimated discriminant with optimization obtained by simulating the true distribution of the estimated discriminant. Optimization via the normal approximation to the estimated discriminant provides huge computational savings in comparison to optimization via simulation of the true distribution. Feature-size optimization via the normal approximation is very accurate when the covariance matrices differ modestly. The optimal number of features based on the normal approximation will exceed the actual optimal number when there is large disagreement between the covariance matrices; however, this difference is not important because the true misclassification error using the number of features obtained from the normal approximation and the number obtained from the true distribution differ only slightly, even for significantly different covariance matrices.     

A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs

We study a problem of lower bounds on straight line drawings of planar graphs. We show that at least 1.235·n points in the plane are required to draw each n-vertex planar graph with edges drawn as straight line segments (for sufficiently large n). This improves the previous best bound of 1.206·n (for sufficiently large n) due to Chrobak and Karloff [Sigact News 20 (4) (1989) 83-86]. Our contribution is twofold: we improve the lower bound itself and we give a significantly simpler and more straightforward proof.     

A cumulant based algorithm for the identification of input-output quadratic systems

The identification of a special class of polynomial models is pursued in this paper. In particular a parameter estimation algorithm is developed for the identification of an input-output quadratic model excited by a zero mean white Gaussian input and with the output corrupted by additive measurement noise. Input-output crosscumulants up to the fifth order are employed and the identification problem of the unknown model parameters is reduced to the solution of successive triangular linear systems of equations that are solved at each step of the algorithm. Simulation studies are carried out and the proposed methodology is compared with two least squares type identification algorithms, the output error method and a combination of the instrumental variables and the output error approach. The proposed cumulant based algorithm and the output error method are tested with real data produced by a robotic manipulator.     

A new approach for the voxelization of volumetric CSG graphs

This paper presents a new approach for the voxelization of volumetric scene graphs. The algorithm generates slices of each primitive intended to be voxelized using an FPGA based pixel processor. The Blist representation is used for the volume scene tree which reduces storage requirement for each voxel to the log(H+1) bits. The most important advantage of this voxelization algorithm is that any volume scene tree expression can be evaluated without using any computation or stack. Also the algorithm is not object specific, i.e. the same algorithm can be used for the voxelization of different types of objects (convex and concave objects, polygons, lines and surfaces).     

A simulation model for the fabrication of components made from multiphase perfect materials

A component, which has an optimized combination of different materials (including homogeneous materials and different types of heterogeneous materials) in its different portions for a specific application, is considered as the component made of a multiphase perfect material. To manufacture such components, a hybrid layered manufacturing technology was proposed. Since it would be risky and very expensive to make such a physical machine without further study and optimization, manufacturing simulation is adopted to do further research so as to provide the reliable foundation for future practical manufacturing. This paper describes its virtual manufacturing technologies and modeling of the component virtually manufactured. Such a model can be used to evaluate the errors of the virtual manufacturing. Finally, an example of simulating manufacturing process and generating the model of the component virtually manufactured is introduced in more detail.