Restricted arc-connectivity of digraphs

Since interconnection networks are often modeled by graphs or digraphs, the edge-connectivity of a graph or arc-connectivity of a digraph are important measurements for fault tolerance of networks.The restricted edge-connectivity λ^′(G) of a graph G is the minimum cardinality over all edge-cuts S in a graph G such that there are no isolated vertices in G−S. A connected graph G is called λ^′-connected, if λ^′(G) exists.In 1988, Esfahanian and Hakimi [A.H. Esfahanian, S.L. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27 (1988), 195-199] have shown that each connected graph G of order n?4, except a star, is λ^′-connected and satisfies λ^′(G)?ξ(G), where ξ(G) is the minimum edge-degree of G.If D is a strongly connected digraph, then we call in this paper an arc set S a restricted arc-cut of D if D−S has a non-trivial strong component D₁ such that D−V(D₁) contains an arc. The restricted arc-connectivity λ^′(D) is the minimum cardinality over all restricted arc-cuts S.We observe that the recognition problem, whether λ^′(D) exists for a strongly connected digraph D is solvable in polynomial time. Furthermore, we present some analogous results to the above mentioned theorem of Esfahanian and Hakimi for digraphs, and we show that this theorem follows easily from one of our results.     

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.     

Sufficient conditions for the existence and asymptotic behaviour of solution to a quasi-linear elliptic problem

In this article, we combine the existing regularity theory, perturbation method and the lower and upper solutions method to study the existence and asymptotic behaviour of positive solution to a boundary value problem for the p-Laplacian operator. More exactly, we study the existence and asymptotic behaviour of the positive solution to a quasi-linear elliptic problem of the form?Δ _p u=λ a(x)g(u) in D′(Ω), u>0 in Ω, lim _{x→? Ω} u(x)=0. Under some conditions on a and g, we show that there is a non-negative number Λ₀ such that for all λ∈(0, Λ₀], the problem has a solution u _λ in the sense of distribution, which is bounded from above by some positive numbers μ(λ). Such estimates and the asymptotic behaviour are important in computer programs when we know an algorithm for determining the solution.     

Constructive Dimension and Turing Degrees

This paper examines the constructive Hausdorff and packing dimensions of Turing degrees. The main result is that every infinite sequence S with constructive Hausdorff dimension dim _H(S) and constructive packing dimension dim _P(S) is Turing equivalent to a sequence R with dim _H(R)≥(dim _H(S)/dim _P(S))−ε, for arbitrary ε>0. Furthermore, if dim _P(S)>0, then dim _P(R)≥1−ε. The reduction thus serves as a randomness extractor that increases the algorithmic randomness of S, as measured by constructive dimension. A number of applications of this result shed new light on the constructive dimensions of Turing degrees. A lower bound of dim _H(S)/dim _P(S) is shown to hold for the Turing degree of any sequence S. A new proof is given of a previously-known zero-one law for the constructive packing dimension of Turing degrees. It is also shown that, for any regular sequence S (that is, dim _H(S)=dim _P(S)) such that dim _H(S)>0, the Turing degree of S has constructive Hausdorff and packing dimension equal to 1. Finally, it is shown that no single Turing reduction can be a universal constructive Hausdorff dimension extractor, and that bounded Turing reductions cannot extract constructive Hausdorff dimension. We also exhibit sequences on which weak truth-table and bounded Turing reductions differ in their ability to extract dimension. F. Stephan was supported in part by NUS research grants Nos. R252-000-212-112 and R252-000-308-112.     

Estimation of chlorophyll-a concentration in coastal waters with HJ-1A HSI data using a three-band bio-optical model and validation

Accurate assessment of phytoplankton chlorophyll-a (chl-a) concentration in turbid waters by means of remote sensing is challenging because of the optical complexity of case 2 waters. We applied a bio-optical model of the form [R^–1(λ₁) – R^–1(λ₂)](λ₃), where R(λ_i) is the remote-sensing reflectance at wavelength λ_i, to estimate chl-a concentration in coastal waters. The objectives of this article are (1) to validate the three-band bio-optical model using a data set collected in coastal waters, (2) to evaluate the extent to which the three-band bio-optical model could be applied to the spectral radiometer (SR) ISI921VF-512T data and the hyperspectral imager (HSI) data on board the Chinese HJ-1A satellite, (3) to evaluate the application prospects of HJ-1A HSI data in case 2 waters chl-a concentration mapping. The three-band model was calibrated using three SR spectral bands (λ₁ = 664.9 nm, λ₂ = 706.54 nm, and λ₃ = 737.33 nm) and three HJ-1A HSI spectral bands (λ₁ = 637.725 nm, λ₂ = 711.495 nm, and λ₃ = 753.750 nm). We assessed the accuracy of chl-a prediction with 21 in situ sample plots. Chl-a predicted by SR data was strongly correlated with observed chl-a (R² = 0.93, root mean square error (RMSE) = 0.48 mg m^–3, coefficient of variation (CV) (RMSE/mean(chl-a_mea)) = 3.72%). Chl-a predicted by HJ-1A HSI data was also closely correlated with observed chl-a (R² = 0.78, RMSE = 0.45 mg m^–3, CV (RMSE/mean(chl-a_mea)) = 7.51%). These findings demonstrate that the HJ-1A HSI data are promising for quantitative monitoring of chl-a in coastal case-2 waters.     

Local colourings of Cartesian product graphs

A local colouring of a graph G is a function c: V(G)→? such that for each S ? V(G), 2≤|S|≤3, there exist u, v∈S with |c(u)?c(v)| at least the number of edges in the subgraph induced by S. The maximum colour assigned by c is the value χ_?(c) of c, and the local chromatic number of G is χ_?(G)=min {χ_?(c): c is a local colouring of G}. In this note the local chromatic number is determined for Cartesian products G □ H, where G and GH are 3-colourable graphs. This result in part corrects an error from Omoomi and Pourmiri [On the local colourings of graphs, Ars Combin. 86 (2008), pp. 147–159]. It is also proved that if G and H are graphs such that χ(G)≤? χ_?(H)/2 ?, then χ_?(G □ H)≤χ_?(H)+1.     

Independence and k-domination in graphs

A subset S of vertices of a graph G is k-dominating if every vertex not in S has at least k neighbours in S. The k-domination number γ _k (G) is the minimum cardinality of a k-dominating set of G, and α(G) denotes the cardinality of a maximum independent set of G. Brook's well-known bound for the chromatic number χ and the inequality α(G)≥n(G)/χ(G) for a graph G imply that α(G)≥n(G)/Δ(G) when G is non-regular and α(G)≥n(G)/(Δ(G)+1) otherwise. In this paper, we present a new proof of this property and derive some bounds on γ _k (G). In particular, we show that, if G is connected with δ(G)≥k then γ _k (G)≤(Δ(G)?1)α(G) with the exception of G being a cycle of odd length or the complete graph of order k+1. Finally, we characterize the connected non-regular graphs G satisfying equality in these bounds and present a conjecture for the regular case.     

New upper and lower bounds for the eigenvalues of the Sturm-Liouville problem

We derive new inequalities for the eigenvaluesλ _k of the Sturm-Liouville problem?u″+qu=λu, u(0)=u(π)=0 under the usual hypothesis thatq has mean value zero. The estimates give upper and lower bounds of the form |λ _k ?k ²|≤p _1,m k ^?m +P _2,m k ^2m ,k ²≥3‖q‖ _m ,m=1, 2 where ‖q‖ _m is the norm ofq in a Sobolev spaceH ^m (0, π) and theP's are homogeneous polynomials of degree at most 3 in ‖q‖ _m . Such bounds are used in the analysis of the inverse Sturm-Liouville problem.     

Ring models for delay-differential systems

This paper studies the algebraic structure of linear systems defined over R[λ], the ring of polynomials in λ with real coefficients. Natural definitions of controllability and observability are introduced and properties of R[λ]-transfer matrix realizations are discussed. It is shown that (A_n×n,D_n×m) is a controllable R[λ]-matrix pair if and only if for each set of polynomialsβ₁,β₂,…,β_n, in R[λ] there exists an R[λ] feedback matrixF such that detsI?A?BF]=∏i=1n(s+β_i). By regarding λ as a suitably defined delay operator, it is explained how this result might be applied to delay-differential systems in order to control dynamic response.     

Note on the connectivity of line graphs

Let G be a connected graph with vertex set V(G), edge set E(G), vertex-connectivity κ(G) and edge-connectivity λ(G).A subset S of E(G) is called a restricted edge-cut if G−S is disconnected and each component contains at least two vertices. The restricted edge-connectivity λ₂(G) is the minimum cardinality over all restricted edge-cuts. Clearly λ₂(G)?λ(G)?κ(G).In 1969, Chartrand and Stewart have shown that

     

Fast projection methods for minimal design problems in linear system theory

The so-called minimal design problem (or MDP) of linear system theory is to find a proper minimal degree rational matrix solution of the equation H(z)D(z)=N(z), where {N(z),D(z)} are given p×r and m×r polynomial matrices with D(z) of full rank r≦m.We describe some solution algorithms that appear to be more efficient (in terms of number of computations and of potential numerical stability) than those presently known. The algorithms are based on the structure of a polynomial echelon form of the left minimal basis of the so-called generalized Sylvester resultant matrix of {N(z), D(z)}. Orthogonal projection algorithms that exploit the Toeplitz structure of this resultant matrix are used to reduce the number of computations needed for the solution.     

Positivity properties in pencils of matrices†

If A and B are positive definite self-adjoint matrices, then all the matrices P_i, occurring in the expansion of an exterior power Λ^k(A+ λB) = P ₀ + P ₁λ + … + P _kλ^k are positive definite.     

Kernels for feedback arc set in tournaments

A tournament T=(V,A) is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on n vertices and an integer parameter k, the Feedback Arc Set problem asks whether the given digraph has a set of k arcs whose removal results in an acyclic digraph. The Feedback Arc Set problem restricted to tournaments is known as the k-Feedback Arc Set in Tournaments (k-FAST) problem. In this paper we obtain a linear vertex kernel for k-FAST. That is, we give a polynomial time algorithm which given an input instance T to k-FAST obtains an equivalent instance T^′ on O(k) vertices. In fact, given any fixed ?>0, the kernelized instance has at most (2+?)k vertices. Our result improves the previous known bound of O(k²) on the kernel size for k-FAST. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for k-FAST.     

On m-restricted edge connectivity of undirected generalized De Bruijn graphs

An m-restricted edge cut is an edge cut of a connected graph whose removal results in components of order at least m, the minimum cardinality over all m-restricted edge cuts of a graph is its m-restricted edge connectivity. It is known that telecommunication networks with topology having larger m-restricted edge connectivity are locally more reliable for all m≤3. This work shows that if n≥7, then undirected generalized binary De Bruijn graph UB_G(2, n) is maximally m-restricted edge connected for all m≤3, where a graph G is maximally m-restricted edge connected if its m-restricted edge connectivity is equal to the minimum number of edges from any connected subgraphs S to G?S.     

Computation of the stability radius of a Hurwitz polynomial with diamond-like uncertainties

This paper considers the stability radius problem of Hurwitz polynomials whose coefficients have Hölder 1-norm-bounded uncertainties. We show that the solution to this problem demands the computation of the minimum of a piece-wise real-rational function ρ(λ), called the stability radius function. It is then shown that the calculations of ρ(λ) at the intersection points where ρ(λ) changes its representation and at the stationary points where ρ′(λ)=0 can be reduced to two sets of eigenvalue problems of matrices of the form H_β⁻¹H_γ, where both H_β and H_γ are frequency-independent Hurwitz matrices. Using root locus technique, we analyze this function further and prove that, in some special cases, the minimum of this function can be achieved only at the intersection points. Extensions of the eigenvalue approach to cover other robust stability problems are also discussed.     

Worst case performance analysis of the two dimensional binary buddy system ∗

The worst case performance of the two dimensional binary buddy system is investigated. Tight lower bounds are given for two system performance measures, namely NETREQ and NETALLOC. Let the system size be 2 ⁿ × 2 ⁿ . It is shown that for any unrestricted saturating sequence S, we have NETREQ(S)≧4^[n/2] + 4^{[n/2] ? 1}+2^[n/2]+l and NETALLOC(S)≧4^[n/2] + 4^[n/2]; for any allocation-only saturating sequence S, we have NETALLOC(S)≧4 ⁿ + 1 and NETREQ(S)≧4 ^n?1 + 2 ⁿ + 2.     

Self-intersection elimination in metamorphosis of two-dimensional curves

H :[0, 1]× ³→ ³, where H(t, r) for t=0 and t=1 are two given planar curves C ₁(r) and C ₂(r). The first t parameter defines the time of fixing the intermediate metamorphosis curve. The locus of H(t, r) coincides with the ruled surface between C ₁(r) and C ₂(r), but each isoparametric curve of H(t, r) is self-intersection free. The second algorithm suits morphing operations of planar curves. First, it constructs the best correspondence of the relative parameterizations of the initial and final curves. Then it eliminates the remaining self-intersections and flips back the domains that self-intersect.     

Embedding Cartesian Products of Graphs into de Bruijn Graphs

Given a Cartesian productG=G₁× … ×G_m(m≥ 2) of nontrivial connected graphsG_iand then-dimensional baseBde Bruijn graphD=D_B(n), it is investigated whether or notGis a spanning subgraph ofD. Special attention is given to graphsG₁× … ×G_mwhich are relevant for parallel computing, namely, to Cartesian products of paths (grids) or cycles (tori). For 2-dimensional de Bruijn graphsD, we present a theorem stating that certain structural assumptions on the factorsG₁, …,G_mensure thatG₁× … ×G_mis a spanning subgraph ofD. As corollaries, we obtain results improving previous results of Heydemannet al.(J. Parallel Distrib. Comput.23 (1994), 104–111) on embedding grids and tori into de Bruijn graphs. Specifically, we obtain that (i) any gridG=G₁× … ×G_mis a spanning subgraph ofD=D_B(2) provided that |G| = |D|, and (ii) any torusG=G₁× … ×G_mis a spanning subgraph ofD=D_B(2) provided that |G| = |D| and that theG_iare cycles of even length ≥4. We show that these results have consequences for the casen> 2, too: for evenn, we apply our results to obtain embeddings of grids and toriGinto de Bruijn graphsD_B(n) with dilationn/2, where the baseBis a fixed integer ≥2, andnis big enough to ensure |G| ≤ |D_B(n)|. We also contrast our results forn= 2 with nonexistence results forn≥ 3 and briefly describe experimental results in the area of parallel image processing.     

Wiener system modelling by exponentially weighted aggregation

In the paper the aggregation algorithm for Wiener system modelling is proposed. The method uses exponential weights to combine (aggregate) models from a given collection of D _λ linear dynamic and D _m nonlinear static models of the genuine system blocks (that can be a priori hypotheses, other system identification outcomes, etc.). The resulting model has a noteworthy property: it is almost as accurate as the best hypothetical Wiener model built from a given collection. This is caused by the fact that the error introduced by the aggregation routine decreases (in the mean squared sense) with growing number of measurements N as fast as CqN ^?1ln?(D _m D _λ ), where C and q are known constants. Simulations confirm theoretical findings and demonstrate applicability of the algorithm in engineering problems for small and moderate measurement data-sets.