共查询到20条相似文献,搜索用时 46 毫秒
1.
Lutz Volkmann 《Information Processing Letters》2007,103(6):234-239
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 D1 such that D−V(D1) 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. 相似文献
2.
《国际计算机数学杂志》2012,89(4):584-588
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. 相似文献
3.
《国际计算机数学杂志》2012,89(12):2637-2647
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 Λ0 such that for all λ∈(0, Λ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. 相似文献
4.
5.
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. 相似文献
6.
Haijing Tian Min Xu Zaichun Zhu Di Liu Xiaoqin Wang 《International journal of remote sensing》2013,34(16):5984-6003
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(λ1) – R–1(λ2)](λ3), 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 (λ1 = 664.9 nm, λ2 = 706.54 nm, and λ3 = 737.33 nm) and three HJ-1A HSI spectral bands (λ1 = 637.725 nm, λ2 = 711.495 nm, and λ3 = 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 (R2 = 0.93, root mean square error (RMSE) = 0.48 mg m–3, coefficient of variation (CV) (RMSE/mean(chl-amea)) = 3.72%). Chl-a predicted by HJ-1A HSI data was also closely correlated with observed chl-a (R2 = 0.78, RMSE = 0.45 mg m–3, CV (RMSE/mean(chl-amea)) = 7.51%). These findings demonstrate that the HJ-1A HSI data are promising for quantitative monitoring of chl-a in coastal case-2 waters. 相似文献
7.
Sandi Klavžar 《国际计算机数学杂志》2015,92(4):694-699
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. 相似文献
8.
《国际计算机数学杂志》2012,89(5):905-915
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. 相似文献
9.
J. T. Marti 《Computing》1989,42(2-3):239-243
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 2|≤p 1,m k ?m +P 2,m k 2m ,k 2≥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. 相似文献
10.
A.S. Morse 《Automatica》1976,12(5):529-531
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 (An×n,Dn×m) is a controllable R[λ]-matrix pair if and only if for each set of polynomialsβ1,β2,…,β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. 相似文献
11.
Note on the connectivity of line graphs 总被引:1,自引:0,他引:1
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 λ2(G) is the minimum cardinality over all restricted edge-cuts. Clearly λ2(G)?λ(G)?κ(G).In 1969, Chartrand and Stewart have shown that
12.
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. 相似文献
13.
WILLIAM C. WATERHOUSE 《International journal of control》2013,86(5):1515-1516
If A and B are positive definite self-adjoint matrices, then all the matrices Pi, occurring in the expansion of an exterior power Λk(A+ λB) = P 0 + P 1λ + … + P kλk are positive definite. 相似文献
14.
Kernels for feedback arc set in tournaments 总被引:1,自引:0,他引:1
Stéphane Bessy Fedor V. Fomin Serge Gaspers Christophe Paul Anthony Perez Saket Saurabh Stéphan Thomassé 《Journal of Computer and System Sciences》2011,77(6):1071-1078
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(k2) 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. 相似文献
15.
《国际计算机数学杂志》2012,89(11):2259-2264
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 UBG(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. 相似文献
16.
Q.-H. Wu 《Systems & Control Letters》1998,35(1):592
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β−1Hγ, 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. 相似文献
17.
《国际计算机数学杂志》2012,89(3-4):123-132
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 n × 2 n . 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 n + 1 and NETREQ(S)≧4 n?1 + 2 n + 2. 相似文献
18.
H :[0, 1]×
3→
3, where H(t, r) for t=0 and t=1 are two given planar curves C
1(r) and C
2(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
1(r) and C
2(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. 相似文献
19.
Thomas Andreae Michael Nölle Gerald Schreiber 《Journal of Parallel and Distributed Computing》1997,46(2):531
Given a Cartesian productG=G1× … ×Gm(m≥ 2) of nontrivial connected graphsGiand then-dimensional baseBde Bruijn graphD=DB(n), it is investigated whether or notGis a spanning subgraph ofD. Special attention is given to graphsG1× … ×Gmwhich 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 factorsG1, …,Gmensure thatG1× … ×Gmis 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=G1× … ×Gmis a spanning subgraph ofD=DB(2) provided that |G| = |D|, and (ii) any torusG=G1× … ×Gmis a spanning subgraph ofD=DB(2) provided that |G| = |D| and that theGiare 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 graphsDB(n) with dilationn/2, where the baseBis a fixed integer ≥2, andnis big enough to ensure |G| ≤ |DB(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. 相似文献
20.
Paweł Wachel 《International journal of control》2017,90(11):2480-2489
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. 相似文献