共查询到20条相似文献,搜索用时 31 毫秒
1.
Given n points, called terminals, in the plane ℝ2 and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from ℝ2 and a spanning tree on the n+k points that minimizes its longest edge length. Edge length is measured by an underlying distance function on ℝ2, usually, the Euclidean or the L
1 metric. This problem is known to be NP-hard. In this paper, we study this problem in the L
p
metric for any 1≤p≤∞, and aim to find an exact algorithm which is efficient for small fixed k. We present the first fixed-parameter tractable algorithm running in f(k)⋅nlog 2
n time for the L
1 and the L
∞ metrics, and the first exact algorithm for the L
p
metric for any fixed rational p with 1<p<∞ whose time complexity is f(k)⋅(n
k
+nlog n), where f(k) is a function dependent only on k. Note that prior to this paper there was no known exact algorithm even for the L
2 metric. 相似文献
2.
L. B. Morales 《Theory of Computing Systems》1997,30(4):367-382
HereR andN denote the real numbers and the nonnegative integers, respectively. Alsos(x)=x
1+···+x
n whenx=(x
1, …,x
n) inR
n. A mapf:R
n →R is call adiagonal function of dimensionn iff|N
n is a bijection ontoN and, for allx, y inN
n, f(x)<f(y) whens(x)<s(y). Morales and Lew [6] constructed 2
n−2 inequivalent diagonal polynomial functions of dimensionn for eachn>1. Here we use new combinatorial ideas to show that numberd
n of such functions is much greater than 2
n−2 forn>3. These combinatorial ideas also give an inductive procedure to constructd
n+1
diagonal orderings of {1, …,n}. 相似文献
3.
We consider static, spherically symmetric solutions of general relativity with a non-linear sigma model (NSM) as a source,
i.e., a set of scalar fields Φ = (Φ1, …, Φ
n
) (so-called chiral fields) parametrizing a target space with a metric h
ab
(Φ). For NSM with zero potential V (Φ), it is shown that the space-time geometry is the same as with a single scalar field but depends on h
ab
. If the matrix h
ab
is positive-definite, we obtain the Fisher metric, originally found for a canonical scalar field with positive kinetic energy;
otherwise we obtain metrics corresponding to a phantom scalar field, including singular and nonsingular horizons (of infinite
area) and wormholes. In particular, the Schwarzschild metric can correspond to a nontrivial chiral field configuration, which
in this case has zero stress-energy. Some explicit examples of chiral field configurations are considered. Some qualitative
properties of NSM configurations with nonzero potentials are pointed out. 相似文献
4.
P. Filipponi 《Calcolo》1980,17(4):365-378
A computer determination of the numberT
n,k of transitive digraphs onn labeled vertices andk arcs is obtained for 2≤n≤6,0 ≤k≤n
2-n.
Furthermore some formulae are given for determiningT
n,k, ∇n for extremal values ofk (namely, 0≤k≤6 andn
2
-3n+4≤k≤n
2-n).
Work carried out at Fondazione Ugo Bordoni under the agreements between Fondazione Ugo Bordoni and the Istituto Superiore
P. T. 相似文献
5.
Vladimir Kovalevsky 《Journal of Mathematical Imaging and Vision》2006,26(1-2):41-58
The paper presents a new set of axioms of digital topology, which are easily understandable for application developers. They
define a class of locally finite (LF) topological spaces. An important property of LF spaces satisfying the axioms is that
the neighborhood relation is antisymmetric and transitive. Therefore any connected and non-trivial LF space is isomorphic
to an abstract cell complex. The paper demonstrates that in an n-dimensional digital space only those of the (a, b)-adjacencies commonly used in computer imagery have analogs among the LF spaces, in which a and b are different and one of the adjacencies is the “maximal” one, corresponding to 3
n
− 1 neighbors. Even these (a, b)-adjacencies have important limitations and drawbacks. The most important one is that they are applicable only to binary
images. The way of easily using LF spaces in computer imagery on standard orthogonal grids containing only pixels or voxels
and no cells of lower dimensions is suggested.
Vladimir Kovalevsky received his diploma in physics from the Kharkov University (Ukraine) in 1950, the first doctor degree in technical science
from the Central Institute of Metrology (Leningrad) in 1957, the second doctor degree in computer science from the Institute
of Cybernetics (Kiev) in 1968. Since 1961 he has been the head of Department of Pattern Recognition at that Institute. Lives
since 1980 in Germany. Currently he is professor of computer science at the University of Applied sciences Berlin. His research
interest include digital geometry, digital topology, computer vision, image processing and pattern recognition. 相似文献
6.
A symmetric zero-mass tensor of rank two is constructed using the superstring modes of excitation, which satisfies the physical
state constraints of a superstring. These states have a one to one correspondence with the quantized field operators and are
shown to be the absorption and emission quanta of the Minkowski space Lorentz tensor, using the quantum field theory method
of quantization. The principle of equivalence makes the tensor identical to the metric tensor at any arbitrary space-time
point. The propagator for the quantized field is deduced. The gravitational interaction is switched on by going over from
ordinary derivatives to co-derivatives. The Riemann-Christoffel affine connections are calculated, and the weak field Ricci
tensor R
μν
0 is shown to vanish. The interaction part R
μν
int is found, and the exact R
μν
of the theory of gravity is expressed in terms of the quantized metric. The quantum-mechanical self-energy of the gravitational
field in vacuum is shown to vanish. By the use of a projection operator, it is shown that gravitons are quanta of the general
relativity field which gives the Einstein equation G
μν
= 0. It is suggested that quantum gravity may be renormalizable by the use of the massless ground state of this superstring
theory for general relativity, and a tachyonic vacuum creates and annihilates quanta of quantized gravitational field. 相似文献
7.
The problem of scheduling resources for tasks with variable requirements over time can be stated as follows. We are given
two sequences of vectors A=A
1,…,A
n
and R=R
1,…,R
m
. Sequence A represents resource availability during n time intervals, where each vector A
i
has q elements. Sequence R represents resource requirements of a task during m intervals, where each vector R
i
has q elements. We wish to find the earliest time interval i, termed latency, such that for 1≤k≤m, 1≤j≤q: A
i+k−1
j
≥R
k
j
, where A
i+k−1
j
and R
k
j
are the jth elements of vectors A
i+k−1 and R
k
, respectively. One application of this problem is I/O scheduling for multimedia presentations.
The fastest known algorithm to compute the optimal solution of this problem has
computation time (Amir and Farach, in Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA), San Francisco,
CA, pp. 212–223, 1991; Inf. Comput. 118(1):1–11, 1995). We propose a technique that approximates the optimal solution in linear time:
.
We evaluated the performance of our algorithm when used for multimedia I/O scheduling. Our results show that 95% of the time,
our solution is within 5% of the optimal. 相似文献
8.
Matt Gibson Gaurav Kanade Erik Krohn Imran A. Pirwani Kasturi Varadarajan 《Algorithmica》2010,57(3):484-498
Given an n-point metric (P,d) and an integer k>0, we consider the problem of covering P by k balls so as to minimize the sum of the radii of the balls. We present a randomized algorithm that runs in n
O(log n⋅log Δ) time and returns with high probability the optimal solution. Here, Δ is the ratio between the maximum and minimum interpoint
distances in the metric space. We also show that the problem is NP-hard, even in metrics induced by weighted planar graphs
and in metrics of constant doubling dimension. 相似文献
9.
Lubomir V. Kolev 《Reliable Computing》2006,12(2):121-140
The paper addresses the problem of determining an outer interval solution of the parametric eigenvalue problem A(p)x = λx, A(p) ∈ ℝn×n for the general case where the matrix elements aij(p) are continuous nonlinear functions of the parameter vector p, p belonging to the interval vector p. A method for computing an interval enclosure of each eigenpair (λμ, x(μ)), μ = 1, ..., n, is suggested for the case where λμ is a simple eigenvalue. It is based on the use of an affine interval approximation of aij(p) in p and reduces, essentially, to setting up and solving a real system of n or 2n incomplete quadratic equations for each real
or complex eigenvalue, respectively. 相似文献
10.
We study the asymptotic behaviour of the eigenvalues of Hermitiann×n block Topelitz matricesT
n
, withk×k blocks, asn tends to infinity. No hypothesis is made concerning the structure of the blocks. Such matrices{T
n
} are generated by the Fourier coefficients of a Hermitian matrix valued functionf∈L
2, and we study the distribution of their eigenvalues for largen, relating their behaviour to some properties of the functionf. We also study the eigenvalues of the preconditioned matrices{P
n
−1
Tn}, where the sequence{P
n
} is generated by a positive definite matrix valued functionp. We show that the spectrum of anyP
n
−1
T
n
is contained in the interval [r, R], wherer is the smallest andR the largest eigenvalue ofp
−1
f. We also prove that the firstm eigenvalues ofP
n
−1
Tn tend tor and the lastm tend toR, for anym fixed. Finally, exact limit values for both the condition number and the conjugate gradient convergence factor for the preconditioned
matricesP
n
−1
Tn are computed. 相似文献
11.
In Valiant’s theory of arithmetic complexity, the classes VP and VNP are analogs of P and NP. A fundamental problem concerning
these classes is the Permanent and Determinant Problem: Given a field
\mathbbF{\mathbb{F}} of characteristic ≠ 2, and an integer n, what is the minimum m such that the permanent of an n × n matrix X = (xij) can be expressed as a determinant of an m × m matrix, where the entries of the determinant matrix are affine linear functions of xij ’s, and the equality is in
\mathbbF[X]{\mathbb{F}}[{\bf X}]. Mignon and Ressayre (2004) proved a quadratic lower bound m = W(n2)m = \Omega(n^{2}) for fields of characteristic 0. We extend the Mignon–Ressayre quadratic lower bound to all fields of characteristic ≠ 2. 相似文献
12.
We present an algorithm to compute the topology of a non-singular real algebraic surface S in RP3, that is the number of its connected components and a topological model for each of them. Our strategy consists in computing the Euler characteristic of each connected component by means of a Morse-type investigation of S or of a suitably constructed compact affine surface. This procedure can be used to determine the topological type of an arbitrary non-singular surface; in particular it extends an existing algorithm applicable only to surfaces disjoint from a line. 相似文献
13.
A Schur-type algorithm is presented for the simultaneous triangular factorization of a given (non-degenerate) structured matrix
and its inverse. The algorithm takes the displacement generator of a Hermitian, strongly regular matrixR as an input, and computes the displacement generator of the inverse matrixR
−1 as an output. From these generators we can directly deduce theLD
−1
L
* (lower-diagonal-upper) decomposition ofR, and theUD
−1
U
* (upper-diagonallower) decomposition ofR
−1. The computational complexity of the algorithm isO(rn
2) operations, wheren andr denote the size and the displacement rank ofR, respectively. Moreover, this method is especially suited for parallel (systolic array) implementations: usingn processors the algorithm can be carried out inO(n) steps. 相似文献
14.
The limit behaviors of computations have not been fully explored. It is necessary to consider such limit behaviors when we
consider the properties of infinite objects in computer science, such as infinite logic programs, the symbolic solutions of
infinite polynomial equations. Usually, we can use finite objects to approximate infinite objects, and we should know what
kinds of infinite objects are approximable and how to approximate them effectively. A sequence {R
k
: k ε ω} of term rewriting systems has the well limit behavior if under the condition that the sequence has the set-theoretic limit
or the distance-based limit, the sequence {Th(R
k
): k ε ω} of corresponding theoretic closures of R
k
has the set-theoretic or distance-based limit, and lim
k→∞
Th(R
k
) is equal to the theoretic closure of the limit of {R
k
: k ε ω}. Two kinds of limits of term rewriting systems are considered: one is based on the set-theoretic limit, the other is on
the distance-based limit. It is proved that given a sequence {R
k
: κ ε ω} of term rewriting systems R
k
, if there is a well-founded ordering ≺ on terms such that every R
k
is ≺-well-founded, and the set-theoretic limit of {R
k
: κ ε ω} exists, then {R
k
: κ ε ω} has the well limit behavior; and if (1) there is a well-founded ordering ≺ on terms such that every R
k
is ≺-well-founded, (2) there is a distance d on terms which is closed under substitutions and contexts and (3) {R
k
: k ε ω} is Cauchy under d then {R
κ: κ ε ω} has the well limit behavior. The results are used to approximate the least Herbrand models of infinite Horn logic programs
and real Horn logic programs, and the solutions and Gr?bner bases of (infinite) sets of real polynomials by sequences of (finite)
sets of rational polynomials. 相似文献
15.
The super spanning connectivity and super spanning laceability of the enhanced hypercubes 总被引:1,自引:1,他引:0
Chung-Hao Chang Cheng-Kuan Lin Jimmy J. M. Tan Hua-Min Huang Lih-Hsing Hsu 《The Journal of supercomputing》2009,48(1):66-87
A k
-container
C(u,v) of a graph G is a set of k disjoint paths between u and v. A k-container C(u,v) of G is a k
*
-container if it contains all vertices of G. A graph G is k
*
-connected if there exists a k
*-container between any two distinct vertices of G. Therefore, a graph is 1*-connected (respectively, 2*-connected) if and only if it is Hamiltonian connected (respectively, Hamiltonian). A graph G is super spanning connected if there exists a k
*-container between any two distinct vertices of G for every k with 1≤k≤κ(G) where κ(G) is the connectivity of G. A bipartite graph G is k
*
-laceable if there exists a k
*-container between any two vertices from different partite set of G. A bipartite graph G is super spanning laceable if there exists a k
*-container between any two vertices from different partite set of G for every k with 1≤k≤κ(G). In this paper, we prove that the enhanced hypercube Q
n,m
is super spanning laceable if m is an odd integer and super spanning connected if otherwise.
相似文献
Chung-Hao ChangEmail: |
16.
We show that several discrepancy-like problems can be solved in NC nearly achieving the discrepancies guaranteed by a probabilistic analysis and achievable sequentially. For example, we describe an NC algorithm that given
a set system (X, S) , where X is a ground set and S⊆2
X
, computes a set R⊆X so that for each S∈
S the discrepancy ||R
S|-|R-∩S|| is
. Whereas previous NC algorithms could only achieve discrepancies
with ɛ>0 , ours matches the probabilistic bound within a multiplicative factor 1+o(1) . Other problems whose NC solution we improve are lattice approximation, ɛ -approximations of range spaces with constant VC-exponent, sampling in geometric configuration spaces, approximation of integer
linear programs, and edge coloring of graphs.
Received June 26, 1998; revised February 18, 1999. 相似文献
17.
Nicolas Passat Michel Couprie Loïc Mazo Gilles Bertrand 《Journal of Mathematical Imaging and Vision》2010,37(1):27-39
Preserving topological properties of objects during thinning procedures is an important issue in the field of image analysis.
In the case of 2-D digital images (i.e. images defined on ℤ2) such procedures are usually based on the notion of simple point. In contrast to the situation in ℤ
n
, n≥3, it was proved in the 80s that the exclusive use of simple points in ℤ2 was indeed sufficient to develop thinning procedures providing an output that is minimal with respect to the topological
characteristics of the object. Based on the recently introduced notion of minimal simple set (generalising the notion of simple point), we establish new properties related to topology-preserving thinning in 2-D spaces
which extend, in particular, this classical result to cubical complexes in 2-D pseudomanifolds. 相似文献
18.
An axis-parallel k-dimensional box is a Cartesian product R 1×R 2×???×R k where R i (for 1≤i≤k) is a closed interval of the form [a i ,b i ] on the real line. For a graph G, its boxicity box?(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a $\lfloor 1+\frac{1}{c}\log n\rfloor^{d-1}An axis-parallel k-dimensional box is a Cartesian product R
1×R
2×⋅⋅⋅×R
k
where R
i
(for 1≤i≤k) is a closed interval of the form [a
i
,b
i
] on the real line. For a graph G, its boxicity box (G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc.
A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs.
For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set
problem for boxicity d graphs, given a box representation, has a
?1+\frac1clogn?d-1\lfloor 1+\frac{1}{c}\log n\rfloor^{d-1}
approximation ratio for any constant c≥1 when d≥2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether
the boxicity of a graph is at most 2 itself is NP-hard. 相似文献
19.
Conclusion In the optimization problem [f
0(x)│hi(x)<-0,i=1,…,l] relaxation of the functionf
0(x)+Nh+(x) does not produce, as we know [6, 7], αk=1 in Newton's method with the auxiliary problem (5), (6), whereF(x)=f
0′(x). For this reason, Newton type methods based on relaxation off
0(x)+Nh+(x) are not superlinearly convergent (so-called Maratos effect). The results of this article indicate that if (F(x)=f
0′(x), then replacement of the initial optimization problem with a larger equivalent problem (7) eliminates the Maratos effect
in the proposed quasi-Newton method. This result is mainly of theoretical interest, because Newton type optimization methods
in the space of the variablesx ∈R
n are less complex. However to the best of our knowledge, the difficulties with nonlocal convergence arising in these methods
(choice of parameters, etc.) have not been fully resolved [10, 11]. The discussion of these difficulties and comparison with
the proposed method fall outside the scope of the present article, which focuses on solution of variational inequalities (1),
(2) for the general caseF′(x)≠F′
T(x).
Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 78–91, November–December, 1994. 相似文献
20.
Jialu Zhang Guojun Wang Mingdi Hu 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2008,12(6):585-591
This paper introduces the concepts of R
0 valuation, R
0 semantic, countable R
0 category , R
0 fuzzy topological category , etc. It is established in a natural way that the fuzzy topology δ and its cut topology on the set Ω
M
consisting of all R
0 valuations of an R
0 algebra M, and some properties of fuzzy topology δ and its cut topology are investigated carefully. Moreover, the representation theorem
for R
0 algebras by means of fuzzy topology is given, that is to say the category is equivalent to the category . By studying the relation between valuations and filters, the Loomis–Sikorski theorem for R
0 algebras is obtained. As an application, K-compactness of the R
0 logic is discussed. 相似文献