共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
We consider orthogonal drawings of a plane graph G with specified face areas. For a natural number k, a k-gonal drawing of G is an orthogonal drawing such that the boundary of G is drawn as a rectangle and each inner face is drawn as a polygon with at most k corners whose area is equal to the specified value. In this paper, we show that every slicing graph G with a slicing tree T and a set of specified face areas admits a 10-gonal drawing D such that the boundary of each slicing subgraph that appears in T is also drawn as a polygon with at most 10 corners. Such a drawing D can be found in linear time. 相似文献
3.
Solomonoff’s central result on induction is that the prediction of a universal semimeasure M converges rapidly and with probability 1 to the true sequence generating predictor μ, if the latter is computable. Hence, M is eligible as a universal sequence predictor in the case of unknown μ. Despite some nearby results and proofs in the literature, the stronger result of convergence for all (Martin-Löf) random sequences remained open. Such a convergence result would be particularly interesting and natural, since randomness can be defined in terms of M itself. We show that there are universal semimeasures M which do not converge to μ on all μ-random sequences, i.e. we give a partial negative answer to the open problem. We also provide a positive answer for some non-universal semimeasures. We define the incomputable measure D as a mixture over all computable measures and the enumerable semimeasure W as a mixture over all enumerable nearly measures. We show that W converges to D and D to μ on all random sequences. The Hellinger distance measuring closeness of two distributions plays a central role. 相似文献
4.
We present a new positive lower bound for the minimum value taken by a polynomial P with integer coefficients in k variables over the standard simplex of Rk, assuming that P is positive on the simplex. This bound depends only on the number of variables k, the degree d and the bitsize τ of the coefficients of P and improves all the previous bounds for arbitrary polynomials which are positive over the simplex. 相似文献
5.
A real x is called h-bounded computable , for some function h:N→N, if there is a computable sequence (xs) of rational numbers which converges to x such that, for any n∈N, at most h(n) non-overlapping pairs of its members are separated by a distance larger than 2-n. In this paper we discuss properties of h-bounded computable reals for various functions h. We will show a simple sufficient condition for a class of functions h such that the corresponding h-bounded computable reals form an algebraic field. A hierarchy theorem for h-bounded computable reals is also shown. Besides we compare semi-computability and weak computability with the h-bounded computability for special functions h. 相似文献
6.
Let F(x,y) be a polynomial over a field K and m a nonnegative integer. We call a polynomial g over K an m-near solution of F(x,y) if there exists a c∈K such that F(x,g)=cxm, and the number c is called an m-value of F(x,y) corresponding to g. In particular, c can be 0. Hence, by viewing F(x,y)=0 as a polynomial equation over K[x] with variable y, every solution of the equation F(x,y)=0 in K[x] is also an m-near solution. We provide an algorithm that gives all m-near solutions of a given polynomial F(x,y) over K, and this algorithm is polynomial time reducible to solving one variable equations over K. We introduce approximate solutions to analyze the algorithm. We also give some interesting properties of approximate solutions. 相似文献
7.
This paper considers two discrete time, finite state processes X and Y. In the usual hidden Markov model X modulates the values of Y. However, the values of Y are then i.i.d. given X. In this paper a new model is considered where the Markov chain X modulates the transition probabilities of the second, observed chain Y. This more realistically can represent problems arising in DNA sequencing. Algorithms for all related filters, smoothers and parameter estimations are derived. Versions of the Viterbi algorithms are obtained. 相似文献
8.
9.
10.
This paper deals with the multicriteria 0-1 knapsack problem (KP) with k-min objectives (MkMIN-KP) in which the first objective is of classical sum type and the remaining objectives are k-min objective functions. The k-min objectives are ordinal objectives, aiming at the maximization of the k th smallest objective coefficient in any feasible knapsack solution with at least k items in the knapsack. We develop efficient algorithms for the determination of the complete nondominated set of MkMIN-KP. 相似文献
11.
12.
A. Abouelaoualim K.Ch. Das L. Faria Y. Manoussakis C. Martinhon R. Saad 《Theoretical computer science》2008
This paper deals with the existence and search for properly edge-colored paths/trails between two, not necessarily distinct, vertices s and t in an edge-colored graph from an algorithmic perspective. First we show that several versions of the s−t path/trail problem have polynomial solutions including the shortest path/trail case. We give polynomial algorithms for finding a longest properly edge-colored path/trail between s and t for a particular class of graphs and characterize edge-colored graphs without properly edge-colored closed trails. Next, we prove that deciding whether there exist k pairwise vertex/edge disjoint properly edge-colored s−t paths/trails in a c-edge-colored graph Gc is NP-complete even for k=2 and c=Ω(n2), where n denotes the number of vertices in Gc. Moreover, we prove that these problems remain NP-complete for c-edge-colored graphs containing no properly edge-colored cycles and c=Ω(n). We obtain some approximation results for those maximization problems together with polynomial results for some particular classes of edge-colored graphs. 相似文献
13.
Let E be a nonsupersingular elliptic curve over the finite field with pn elements. We present a deterministic algorithm that computes the zeta function and hence the number of points of such a curve E in time quasi-quadratic in n. An older algorithm having the same time complexity uses the canonical lift of E, whereas our algorithm uses rigid cohomology combined with a deformation approach. An implementation in small odd characteristic turns out to give very good results. 相似文献
14.
Let G be the smallest Suzuki group Sz(8) and let F be an algebraically closed field of characteristic 2. The basic algebra of the group algebra of G over F is described by its Ext-quiver and a certain set of relations. 相似文献
15.
The present paper investigates two-parameter families of spheres in R3 and their corresponding two-dimensional surfaces Φ in R4. Considering a rational surface Φ in R4, the envelope surface Ψ of the corresponding family of spheres in R3 is typically non-rational. Using a classical sphere-geometric approach, we prove that the envelope surface Ψ and its offset surfaces admit rational parameterizations if and only if Φ is a rational sub-variety of a rational isotropic hyper-surface in R4. The close relation between the envelope surfaces Ψ and rational offset surfaces in R3 is elaborated in detail. This connection leads to explicit rational parameterizations for all rational surfaces Φ in R4 whose corresponding two-parameter families of spheres possess envelope surfaces admitting rational parameterizations. Finally we discuss several classes of surfaces sharing this property. 相似文献
16.
17.
We consider time-space tradeoffs for static data structure problems in the cell probe model with word size 1 (the bit probe model). In this model, the goal is to represent n-bit data with s=n+r bits such that queries (of a certain type) about the data can be answered by reading at most t bits of the representation. Ideally, we would like to keep both s and t small, but there are tradeoffs between the values of s and t that limit the possibilities of keeping both parameters small. 相似文献
18.
Andrej Muchnik Alexander Shen Mikhail Ustinov Nikolai Vereshchagin Michael Vyugin 《Theoretical computer science》2007
Assume that a program p on input a outputs b. We are looking for a shorter program q having the same property (q(a)=b). In addition, we want q to be simple conditional to p (this means that the conditional Kolmogorov complexity K(q|p) is negligible). In the present paper, we prove that sometimes there is no such program q, even in the case when the complexity of p is much bigger than K(b|a). We give three different constructions that use the game approach, probabilistic arguments and algebraic arguments, respectively. 相似文献
19.
We present a new algorithm for computing the topology of a real algebraic surface S in a ball B, even in singular cases. We use algorithms for 2D and 3D algebraic curves and show how one can compute a topological complex equivalent to S, and even a simplicial complex isotopic to S by exploiting properties of the contour curve of S. The correctness proof of the algorithm is based on results from stratification theory. We construct an explicit Whitney stratification of S, by resultant computation. Using Thom’s isotopy lemma, we show how to deduce the topology of S from a finite number of characteristic points on the surface. An analysis of the complexity of the algorithm and effectiveness issues conclude the paper. 相似文献
20.
The focus of the present paper is on providing a local deterministic algorithm for colouring the edges of Yao-like subgraphs of Unit Disk Graphs. These are geometric graphs such that for some positive integers l,k the following property holds at each node v: if we partition the unit circle centered at v into 2k equally sized wedges then each wedge can contain at most l points different from v. We assume that the nodes are location aware, i.e. they know their Cartesian coordinates in the plane. The algorithm presented is local in the sense that each node can receive information emanating only from nodes which are at most a constant (depending on k and l, but not on the size of the graph) number of hops (measured in the original underlying Unit Disk Graph) away from it, and hence the algorithm terminates in a constant number of steps. The number of colours used is 2kl+1 and this is optimal for local algorithms (since the maximal degree is 2kl and a colouring with 2kl colours can only be constructed by a global algorithm), thus showing that in this class of graphs the price for locality is only one additional colour. 相似文献