共查询到20条相似文献,搜索用时 15 毫秒
1.
Let p1, … pt be polynomials in
n with a variety V of common zeros contained in a suitable open set U. Explicit formulas are provided to construct rational functions λ 1, … λ s such that Σ i=1spiλ i 1, and such that the singularities of the λ i are contained in U. This result is applied to compute rational functions-valued 1-inverses of matrices with polynomial coefficients, which do not have constant rank, while retaining control over the location of the singularities of the rational functions themselves. 相似文献
2.
It is pointed out in this brief paper that the l1 optimization problem min Q ε lqp1 | H − U * Q * V | 1, H ε lmn1, U ε lmq1, V ε lpn1 can be solved in one step rather than two. The solution of the dual problem is obviated by the direct solution of the primal problem via linear programming. The method here is applicable to finite-dimensional problems or approximating finite-dimensional problems, in the general case. 相似文献
3.
In this paper we consider equations defined by (1.3)–(1.2)–(1.4). We describe in detail three algorithms for the approximate determination of |λ nr|, for |λ 1| resp. for one of the λ j's. The single steps of the algorithms are the four fundamental operations and the positive value of kth roots of positive numbers and the main interest of them lies in the fact that (the algorithms themselves and so) their lengths depend only on n, r and the prescribed relative error and not on the entries of the matrices Aν. 相似文献
4.
Interval routing (IR) is a space-efficient routing method for computer networks. For longest routing path analysis, researchers have focused on lower bounds for many years. For any n-node graph G of diameter D, there exists an upper bound of 2 D for IR using one or more labels, and an upper bound of
for IR using
or more labels. We present two upper bounds in the first part of the paper. We show that for every integer i>0, every n-node graph of diameter D has a k-dominating set of size
for
. This result implies a new upper bound of
for IR using
or more labels, where i is any positive integer constant. We apply the result by Kutten and Peleg [ 8] to achieve an upper bound of (1+) D for IR using O( n/ D) or more labels, where is any constant in (0,1). The second part of the paper offers some lower bounds for planar graphs. For any M-label interval routing scheme ( M-IRS), where
, we derive a lower bound of [(2 M+1)/(2 M)] D−1 on the longest path for
, and a lower bound of [(2(1+δ) M+1)/(2(1+δ) M)] D, where δ(0,1], for
. The latter result implies a lower bound of
on the number of labels needed to achieve optimality. 相似文献
5.
The problem of determining the maximum matching in a convex bipartite graph, G = ( V1, V2, E), is considered. It is shown that by using the appropriate data structures, the maximum matching problem can be efficiently transformed into an off-line minimum problem. Since the off-line minimum problem has been shown to be linear, the maximum matching in a convex bipartite graph can be determined in O(| V1|) time. 相似文献
6.
This paper presents an efficient algorithm for enumerating all minimal a- b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = ( V, E), Our algorithm requires O( n3Rab) time, which improves the known result of O( n4Rab) time for solving this problem, where ¦ V¦= n and Rab is the number of minimal a- b separators. The algorithm can be generalized for enumerating all minimal A- B separators that separate non-adjacent vertex sets A, B < V, and it requires O( n2( n − nA − nb) RAB) time in this case, where na = ¦ A¦, nB = ¦ B¦ and rAB is the number of all minimal A− B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O( n3R+Σ + n4RΣ), which improves the known result of O( n6RΣ) time, where Rσ is the number of all minimal separators of G and RΣR+Σ = ∑ 1i, v j) ER vivj (n( n − 1)/2 − m) RΣ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O(( n/ log n) Rab) time and the second one runs in time O(( n/ log n) R+Σ+ n log nRΣ) on a CREW PRAM with O( n3) processors. 相似文献
7.
For an ordered set W = { w1, w2,…, wk} of vertices and a vertex v in a connected graph G, the (metric) representation of v with respect to W is the k-vector r( v | W) = ( d( v, w1), d( v, w2),…, d( v, wk)), where d( x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations. A new sharp lower bound for the dimension of a graph G in terms of its maximum degree is presented. A resolving set of minimum cardinality is a basis for G and the number of vertices in a basis is its (metric) dimension dim(G). A resolving set S of G is a minimal resolving set if no proper subset of S is a resolving set. The maximum cardinality of a minimal resolving set is the upper dimension dim+(G). The resolving number res(G) of a connected graph G is the minimum k such that every k-set W of vertices of G is also a resolving set of G. Then 1 ≤ dim(G) ≤ dim+(G) ≤ res(G) ≤ n − 1 for every nontrivial connected graph G of order n. It is shown that dim+(G) = res(G) = n − 1 if and only if G = Kn, while dim+(G) = res(G) = 2 if and only if G is a path of order at least 4 or an odd cycle. The resolving numbers and upper dimensions of some well-known graphs are determined. It is shown that for every pair a, b of integers with 2 ≤ a ≤ b, there exists a connected graph G with dim(G) = dim+(G) = a and res(G) = b. Also, for every positive integer N, there exists a connected graph G with res(G) − dim+(G) ≥ N and dim+(G) − dim(G) ≥ N. 相似文献
8.
To approach a simple game Δ 2 of P and E = {E1, E2} with no a priori evaders' role assignment and the payoff equal to the distance to one evader at an instant of catching another, we introduce a concept of casting and study the games Δ 1,2 and Δ 2,1 for preassigned and Δ p2 for open-loop casting procedures. Since Δ p2 is reduced to Δ 1,2 or Δ 2,1 which, in turn, are distinguished only by their notations, we focus attention mainly on Δ 1,2. According to the tenet of transition, Δ 1,2 is divided into a concatenation of Δ 1,2b (basic) and Δ 1,2a (auxiliary) games that model the problem before and after the first instant of E1 capture. The games Δ1,2a, Δ 1,2b, Δ 1,2 are studied one after another with use of the Isaacs' approach extended by Berkowitz, Breakwell, Bernhard et al. 相似文献
9.
Let X1,…, Xr+1 be independent random variables, XiGa ( ai, θ, δi), i = 1,…, r + 1. Define and Vi = Xi/ Xr+1, i = 1,…, r. Then, ( U1,…, Ur) and ( V1,…, Vr) follow noncentral Dirichlet Type 1 and Type 2 distributions, respectively. In this article several properties of these distributions and their connections with the uniform, the noncentral multivariate- F and the noncentral multivariate- t distributions are discussed. 相似文献
10.
The inflation GI of a graph G with n( G) vertices and m( G) edges is obtained from G by replacing every vertex of degree d of G by a clique Kd. A set S of vertices in a graph G is a paired dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired domination number γ p( G) is the minimum cardinality of a paired dominating set of G. In this paper, we show that if a graph G has a minimum degree δ( G)2, then n( G)γ p( GI)4 m( G)/[δ( G)+1], and the equality γ p( GI) = n( G) holds if and only if G has a perfect matching. In addition, we present a linear time algorithm to compute a minimum paired-dominating set for an inflation tree. 相似文献
12.
A tree t- spanner T in a graph G is a spanning tree of G such that the distance in T between every pair of vertices is at most t times their distance in G. The T
t-S
problem asks whether a graph admits a tree t-spanner, given t. We substantially strengthen the hardness result of Cai and Corneil (SIAM J. Discrete Math. 8 (1995) 359–387) by showing that, for any t4, T
t-S
is NP-complete even on chordal graphs of diameter at most t+1 (if t is even), respectively, at most t+2 (if t is odd). Then we point out that every chordal graph of diameter at most t−1 (respectively, t−2) admits a tree t-spanner whenever t2 is even (respectively, t3 is odd), and such a tree spanner can be constructed in linear time. The complexity status of T
3-S
still remains open for chordal graphs, even on the subclass of undirected path graphs that are strongly chordal as well. For other important subclasses of chordal graphs, such as very strongly chordal graphs (containing all interval graphs), 1-split graphs (containing all split graphs) and chordal graphs of diameter at most 2, we are able to decide T
3-S
efficiently. 相似文献
13.
In order to maintain consistency, analytical expressions for the free energy of mixing of phases should reproduce not only the phase diagrams but also the experimentally determined activities. Information on the partial molar free energies and the phase boundaries, in turn, can be used to estimate the free energy of formation of compounds. An examination of thermochemical data in the CaO-SiO2 system showed that ΔGδf values for -Ca2Si04, which are stable at temperatures above 1710°K, are limited a maximum of 1800°K. The free energy of formation in a temperature range from about 1700 to 2400°K was estimated from the phase boundary and the activity of silica to be as follows: 2Ca0(s) + Si02(cristo.) = Ca2Si04() ΔG°f = −86303.50 − 34.338 Tjoules An analytical expression for the free energy of mixing of the liquid phase was obtained for the entire composition range in the CaO-Si02 system. Confidence in the estimated G‡f for -Ca2Si04 was demonstrated by good agreement of the calculated phase diagram and the experimentally determined activity of silica. 相似文献
14.
In this paper we study the behavior of the beta-spline functions in the case the parameter β 2( i) is negative. We prove that a negative value
exists so that if
, the beta-spline functions Ni( u) are positive. Moreover, if the control vertices are such that x0 xm−1, we have proved that the design curve keeps the properties already proved in the case β 2( i) 0. 相似文献
15.
This paper studies some computability notions for abstract data types, and in particular compares cosemicomputable many-sorted algebras with a notion of finality to model minimal-state realizations of abstract (software) machines. Given a finite many-sorted signature Σ and a set of V of visible sorts, for every Σ-algebra A with co-r.e. behavior and nontrivial, computable V-behavior, there is a finite signature extension Σ' of Σ (without new sorts) and a finite set E of Σ'-equations such that A is isomorphic to a reduct of the final (Σ', E)-algebra relative to V. This uses a theorem due to Bergstra and Tucker [3]. If A is computable, then A is also isomorphic to the reduct of the initial (Σ′, E)-algebra. We also prove some results on congruences of finitely generated free algebras. We show that for every finite signature Σ, there are either countably many Σ-congruences on the free Σ-algebra or else there is a continuum of such congruences. There are several necessary and sufficient conditions which separate these two cases. We introduce the notion of the Turing degree of a minimal algebra. Using the results above, we prove that there is a fixed one-sorted signature such that for every r.e. degree d, there is a finite set E of Σ-equations such the initial (Σ, E)-algebra has degree d. There is a two-sorted signature Σ 0 and a single visible sort such that for every r.e. degree d there is a finite set E of Σ-equations such that the initial (Σ, E, V)-algebra is computable and the final (Σ, E, V)-algebra is cosemicomputable and has degree d. 相似文献
16.
Bidimensional wavelet bases are constructed by means of McClellan's transformation applied to a pair of one-dimensional biorthogonal wavelet filters. It is shown that under some conditions on the transfer function F(ω 1,ω 2) associated to the McClellan transformation and on the dilation matrix D, it is possible to construct symmetric compactly supported biorthogonal wavelet bases of L2(R 2). Finally, the construction method is illustrated by means of numerical examples. 相似文献
17.
In this paper we propose a limit characterization of the behaviour of classes of graphs with respect to their number of spanning trees. Let { Gn} be a sequence of graphs G0, G1, G2,… that belong to a particular class. We consider graphs of the form Kn− Gn that result from the complete graph Kn after removing a set of edges that span Gn. We study the spanning tree behaviour of the sequence { Kn− Gn} when n→∞ and the number of edges of Gn scales according to n. More specifically, we define the spanning tree indicator ({ Gn}), a quantity that characterizes the spanning tree behaviour of { Kn− Gn}. We derive closed formulas for the spanning tree indicators for certain well-known classes of graphs. Finally, we demonstrate that the indicator can be used to compare the spanning tree behaviour of different classes of graphs (even when their members never happen to have the same number of edges). 相似文献
18.
When executing processes on parallel computer systems a major bottle-neck
is interprocessor communication. One way to address this problem is to minimize the
communication between processes that are mapped to different processors. This
translates to the k-partitioning problem of the corresponding process graph,
where k is the number of processors. The classical spectral lower bound of
(| V|/2 k)\sum
k
i=1λ
i
for the k-section width of a graph is well
known. We show new relations between the structure and the eigenvalues of a graph
and present a new method to get tighter lower bounds on the k-section width.
This method makes use of the level structure defined by the k-section. We
define a global expansion property and prove that for graphs with the same
k-section width the spectral lower bound increases with this global expansion.
We also present examples of graphs for which our new bounds are tight up to a
constant factor. 相似文献
19.
An ordered binary decision diagram (OBDD) is a graph representation of a Boolean function. In this paper, the size of ordered binary decision diagrams representing threshold functions is discussed. We consider two cases: the case when a variable ordering is given and the case when it is adaptively chosen. We show 1) O(2 n/2) upper bound for both cases, 2) Ω(2 n/2) lower bound for the former case and 3) Ω( n2 √n/2) lower bound for the latter case. We also show some relations between the variable ordering and the size of OBDDs representing threshold functions. 相似文献
20.
A graph G was defined in [16] as P4-reducible, if no vertex in G belongs to more than one chordless path on four vertices or P4. A graph G is defined in [15] as P4-sparse if no set of five vertices induces more than one P4, in G. P4-sparse graphs generalize both P4-reducible and the well known class of p4-free graphs or cographs. In an extended abstract in [11] the first author introduced a method using the modular decomposition tree of a graph as the framework for the resolution of algorithmic problems. This method was applied to the study of P4-sparse and extended P4-sparse graphs. In this paper, we begin by presenting the complete information about the method used in [11]. We propose a unique tree representation of P4-sparse and a unique tree representation of P4-reducible graphs leading to a simple linear recognition algorithm for both classes of graphs. In this way we simplify and unify the solutions for these problems, presented in [16–19]. The tree representation of an n-vertex P4-sparse or a P4-reducible graph is the key for obtaining O(n) time algorithms for the weighted version of classical optimization problems solved in [20]. These problems are NP-complete on general graphs. Finally, by relaxing the restriction concerning the exclusion of the C5 cycles from P4-sparse and P4-reducible graphs, we introduce the class of the extended P4-sparse and the class of the extendedP4-reducible graphs. We then show that a minimal amount of additional work suffices for extending most of our algorithms to these new classes of graphs. 相似文献
|