Determining the number of internal stability of a graph

The number of internal stability or independence number of an undirected graph has many important applications. Computationally it belongs to the class of intractable problems known as NP-Hard. In this paper we develop a tree search algorithm to determine the ndependence number of an undirected graph. Extensive computational experience on 2400 randomly generated graphs ranging from 20% to 90% densities and from 50 to 200 vertice has shown that the proposed algorithm is very effective.     

New analytical lower bounds on the clique number of a graph

This paper proposes three new analytical lower bounds on the clique number of a graph and compares these bounds with those previously established in the literature. Two proposed bounds are derived from the well-known Motzkin–Straus quadratic programming formulation for the maximum clique problem. Theoretical results on the comparison of various bounds are established. Computational experiments are performed on random graph models such as the Erdös-Rényi model for uniform graphs and the generalized random graph model for power-law graphs that simulate graphs with different densities and assortativity coefficients. Computational results suggest that the proposed new analytical bounds improve the existing ones on many graph instances.     

On the stability of a weighted diamond of real polynomials

Recently, a subset of the robust stability literature concentrated on the so-called diamond of polynomials. In this paper, we study the weighted diamond Q_w defined as

, where the center q^*, the weights w₀, w₁, 3dot , w_n > 0 and the radius r > 0 are given. For this family, we show that an extreme point result holds if and only if a certain ‘interlacing condition’ on the weights is satisfied.     

Nonlinear discriminant mapping using the Laplacian of a graph

In this paper, an algorithm for nonlinear discriminant mapping (NDM) is presented, which elegantly integrates the ideas of both linear discriminant analysis (LDA) and Isomap by using the Laplacian of a graph. The objective of NDM is to find a linear subspace project of nonlinear data set, which preserves maximum difference between between-class scatter and within-class scatter.     

An output sensitive algorithm for computing a maximum independent set of a circle graph

We present an output sensitive algorithm for computing a maximum independent set of an unweighted circle graph. Our algorithm requires O(nmin{d,α}) time at worst, for an n vertex circle graph where α is the independence number of the circle graph and d is its density. Previous algorithms for this problem required Θ(nd) time at worst.     

New upper bounds for excited vibration systems with applications of the differential calculus of norms

In an earlier paper, the author introduced new upper bounds for free linear and nonlinear vibration systems; to compute the best upper bounds, the differential calculus of norms was applied. In the present paper, this work is continued for the corresponding excited systems. Some new techniques and ideas are involved. The results in the applications cannot be obtained by the methods used so far.     

Tight upper bound on the number of edges in a bipartite K3,3-free or K5-free graph with an application

We show that an n-vertex bipartite K_3,3-free graph with n?3 has at most 2n−4 edges and that an n-vertex bipartite K₅-free graph with n?5 has at most 3n−9 edges. These bounds are also tight. We then use the bound on the number of edges in a K_3,3-free graph to extend two known NC algorithms for planar graphs to K_3,3-free graphs.     

Search for the upper bound of Bayesian estimates of the parameter in an exponential failure model with two known quantiles of an a priori distribution function

A fast exact algorithm of searching for the upper bound of Bayesian estimates for the parameter of the exponential distribution under the condition that an a priori distribution belongs to the class of all distribution functions with two equal quantiles. This problem arises in analyzing the sensitivity of Bayesian estimates to the choice of an a priori distribution in an exponential failure model. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 90–102, January–February 2007.     

Development of a particle number and particle mass vehicle emissions inventory for an urban fleet

Motor vehicles are major emitters of gaseous and particulate matter pollution in urban areas, and exposure to particulate matter pollution can have serious health effects, ranging from respiratory and cardiovascular disease to mortality. Motor vehicle tailpipe particle emissions span a broad size range from 0.003 to 10 μm, and are measured as different subsets of particle mass concentrations or particle number count. However, no comprehensive inventories currently exist in the international published literature covering this wide size range. This paper presents the first published comprehensive inventory of motor vehicle tailpipe particle emissions covering the full size range of particles emitted. The inventory was developed for urban South-East Queensland by combining two techniques from distinctly different disciplines, from aerosol science and transport modelling. A comprehensive set of particle emission factors were combined with transport modelling, and tailpipe particle emissions were quantified for particle number (ultrafine particles), PM₁, PM_2.5 and PM₁₀ for light and heavy duty vehicles and buses. A second aim of the paper involved using the data derived in this inventory for scenario analyses, to model the particle emission implications of different proportions of passengers travelling in light duty vehicles and buses in the study region, and to derive an estimate of fleet particle emissions in 2026. It was found that heavy duty vehicles (HDVs) in the study region were major emitters of particulate matter pollution, and although they contributed only around 6% of total regional vehicle kilometres travelled, they contributed more than 50% of the region's particle number (ultrafine particles) and PM₁ emissions. With the freight task in the region predicted to double over the next 20 years, this suggests that HDVs need to be a major focus of mitigation efforts. HDVs dominated particle number (ultrafine particles) and PM₁ emissions; and LDV PM_2.5 and PM₁₀ emissions. Buses contributed approximately 1–2% of regional particle emissions.     

Minimality considerations for graph energy over a class of graphs

Let G be a graph on n vertices, and let CHP(G;λ) be the characteristic polynomial of its adjacency matrix A(G). All n roots of CHP(G;λ), denoted by , are called to be its eigenvalues. The energy E(G) of a graph G, is the sum of absolute values of all eigenvalues, namely, . Let be the set of n-vertex unicyclic graphs, the graphs with n vertices and n edges. A fully loaded unicyclic graph is a unicyclic graph taken from with the property that there exists no vertex with degree less than 3 in its unique cycle. Let be the set of fully loaded unicyclic graphs. In this article, the graphs in with minimal and second-minimal energies are uniquely determined, respectively.     

Exact upper bounds of the probability of failure in a time interval in the case of incomplete information on the distribution function

Exact upper bounds are obtained for the probability F() - F(u), 0 < u < < , on the set of distribution functions F(x) of nonnegative random variables with unimodal density with an arbitrary mode m 0 and one or two fixed first moments.Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 72–83, September–October 2004.     

On the connection between the exponential stability of C0-semigroups and the admissibility of a certain Sobolev space

Let T be a strongly continuous semigroup on a Banach space X and A its infinitesimal generator. We will prove that T is exponentially stable, if and only if, there exist p[1,∞) such that the space is admissible to the system Σ(A,I,I), defined below (i.e for all f belonging to the Sobolev space the convolution T*f lies in .     

Fuzzy measures for a correlation coefficient of fuzzy numbers under TW(the weakest t-norm)-based fuzzy arithmetic operations

Recently, the sup-min convolution based on Zadeh’s extension principle has been used by Liu and Kao [Fuzzy measures for correlation coefficient of fuzzy numbers, Fuzzy Sets and Systems 128 (2002) 267-275], to calculate a fuzzy correlation coefficient. They used a mathematical programming approach to derive fuzzy measures based on the classical definition of the correlation coefficient. It is well known that T_W (the weakest t-norm)-based addition and multiplication preserve the shape of L-R fuzzy numbers. In this paper, we consider the computational aspect of the T_W-based extension principle when the principle is applied to a correlation coefficient of L-R fuzzy numbers. We give the exact solution of a fuzzy correlation coefficient without programming or the aid of computer resources.     

Scheduling n jobs on one machine to minimize the maximum lateness with a minimum number of tardy jobs

This study considers the problem of scheduling n jobs, each job having an arrival time, a processing time and a due date, on a single machine with the dual objective of minimizing the maximum lateness subject to obtaining a minimum number of tardy jobs. A simple procedure is introduced to identify two critical jobs from which the maximum lateness is generated for a given sequence. The sequence of jobs between two critical jobs inclusive is called the critical path. On the basis of the critical path, Carlier's binary branching rule is adopted to minimize the maximum lateness. By fixing the position of these two critical jobs for maintaining the minimum maximum lateness, the sequence can further be reordered to reduce the number of tardy jobs. A branch and bound algorithm is presented for this purpose. The algorithm can solve problems with 50 jobs optimally within 5 seconds on a PC Pentium-100.     

A weighted H1 seminorm regularization method for Fredholm integral equations of the first kind

Many problems in mathematics and engineering lead to Fredholm integral equations of the first kind, e.g. signal and image processing. These kinds of equations are difficult to solve numerically since they are ill-posed. Therefore, regularization is required to obtain a reasonable approximate solution. This paper presents a new regularization method based on a weighted H¹ seminorm. Details of numerical implementation are given. Numerical examples, including one-dimensional and two-dimensional integral equations, are presented to illustrate the efficiency of the proposed approach. Numerical results show that the proposed regularization method can restore edges as well as details.     

On the surface area of the -star graph

We present an explicit formula for the surface area of the (n,k)-star graph, i.e., the number of nodes at a certain distance from the identity node in the graph, by identifying the unique cycle structures associated with the nodes in the graph, deriving a distance expression in terms of such structures between the identity node of the graph and any other node, and enumerating those cycle structures satisfying the distance restriction.The above surface area derivation process can also be applied to some of the other node symmetric interconnection structures defined on the symmetric group, when the aforementioned distance expression is available.