共查询到20条相似文献,搜索用时 31 毫秒
1.
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. 相似文献
2.
We describe O(n) time algorithms for finding the minimum weighted dominating induced matching of chordal, dually chordal, biconvex, and claw-free graphs. For the first three classes, we prove tight O(n) bounds on the maximum number of edges that a graph having a dominating induced matching may contain. By applying these bounds, and employing existing O(n+m) time algorithms we show that they can be reduced to O(n) time. For claw-free graphs, we describe a variation of the existing algorithm for solving the unweighted version of the problem, which decreases its complexity from O(n2) to O(n), while additionally solving the weighted version. The same algorithm can be easily modified to count the number of DIM's of the given graph. 相似文献
3.
4.
The most efficient currently known algorithms for two-dimensional pattern matching with rotations have a worst case time complexity of O(n2m3), where the size of the text is n×n and the size of the pattern is m×m. In this paper we present a new algorithm for the problem whose running time is O(n2m2). 相似文献
5.
6.
A collection of T1,T2,…,Tk of unrooted, leaf labelled (phylogenetic) trees, all with different leaf sets, is said to be compatible if there exists a tree T such that each tree Ti can be obtained from T by deleting leaves and contracting edges. Determining compatibility is NP-hard, and the fastest algorithm to date has worst case complexity of around Ω(nk) time, n being the number of leaves. Here, we present an O(nf(k)) algorithm, proving that compatibility of unrooted phylogenetic trees is fixed parameter tractable (FPT) with respect to the number k of trees. 相似文献
7.
In this paper we study energy-aware scheduling that trades energy consumption against a traditional performance measure of delay. We use the power-rate function f(x)=c+xα for x>0 and f(0)=0 to model the power consumption, where c>0 represents the base power. We give a definition of a rate-adaptive version of the Weighted Fair Queueing scheduling algorithm, and prove its energy consumption is within a bounded factor of the best possible when the algorithm guarantees the classic end-to-end delay for every connection. 相似文献
8.
We aim at finding the best possible seed values when computing a1/p using the Newton–Raphson iteration in a given interval. A natural choice of the seed value would be the one that best approximates the expected result. It turns out that in most cases, the best seed value can be quite far from this natural choice. When we evaluate a monotone function f(a) in the interval [amin,amax], by building the sequence xn defined by the Newton–Raphson iteration, the natural choice consists in choosing x0 equal to the arithmetic mean of the endpoint values. This minimizes the maximum possible distance between x0 and f(a). And yet, if we perform n iterations, what matters is to minimize the maximum possible distance between xn and f(a). In several examples, the value of the best starting point varies rather significantly with the number of iterations. 相似文献
9.
10.
We introduce a general notion of miniaturization of a problem that comprises the different miniaturizations of concrete problems considered so far. We develop parts of the basic theory of miniaturizations. Using the appropriate logical formalism, we show that the miniaturization of a definable problem in W[t] lies in W[t], too. In particular, the miniaturization of the dominating set problem is in W[2]. Furthermore, we investigate the relation between f(k)·no(k) time and subexponential time algorithms for the dominating set problem and for the clique problem. 相似文献
11.
12.
Zhengnan Shi 《Information Processing Letters》2012,112(13):525-531
In self-stabilization, each node has a local view of the distributed network system, in a finite amount of time the system converges to a global setup with desired property, in this case establishing a 2-packing set. Using a graph G=(V,E) to represent the network, a subset S⊆V is a 2-packing if ∀i∈V:|N[i]∩S|?1. In this paper, we first propose an ID-based, constant space, self-stabilizing algorithm that stabilizes to a maximal 2-packing in an arbitrary graph. We show that the algorithm stabilizes in O(mn) moves under any scheduler (such as a distributed daemon). Secondly, we show that the algorithm stabilizes in O(n2) rounds under a synchronous daemon where every privileged node moves at each round. 相似文献
13.
Dimensional analysis yields a new scaling formula for the Linpack benchmark. The computational power r(p0,q0) on a set of processors decomposed into a (p0,q0) grid determines the computational power r(p,q) on a set of processors decomposed into a (p,q) grid by the formula r(p,q)=(p/p0)α(q/q0)βr(p0,q0). The two scaling parameters α and β measure interprocessor communication overhead required by the algorithm. A machine that scales perfectly corresponds to α=β=1; a machine that scales not at all corresponds to α=β=0. We have determined the two scaling parameters by imposing a fixed-time constraint on the problem size such that the execution time remains constant as the number of processors changes. Results for a collection of machines confirm that the formula suggested by dimensional analysis is correct. Machines with the same values for these parameters are self-similar. They scale the same way even though the details of their specific hardware and software may be quite different. 相似文献
14.
In this paper we show a new method for calculating the nucleolus by solving a unique minimization linear program with O(4n) constraints whose coefficients belong to {−1,0,1}. We discuss the need of having all these constraints and empirically prove that they can be reduced to O(kmax2n), where kmax is a positive integer comparable with the number of players. A computational experience shows the applicability of our method over (pseudo)random transferable utility cooperative games with up to 18 players. 相似文献
15.
16.
The twisted cube is an important variation of the hypercube. It possesses many desirable properties for interconnection networks. In this paper, we study fault-tolerant embedding of paths in twisted cubes. Let TQn(V,E) denote the n-dimensional twisted cube. We prove that a path of length l can be embedded between any two distinct nodes with dilation 1 for any faulty set F⊂V(TQn)∪E(TQn) with |F|?n-3 and any integer l with 2n-1-1?l?|V(TQn-F)|-1 (n?3). This result is optimal in the sense that the embedding has the smallest dilation 1. The result is also complete in the sense that the two bounds on path length l and faulty set size |F| for a successful embedding are tight. That is, the result does not hold if l?2n-1-2 or |F|?n-2. We also extend the result on (n-3)-Hamiltonian connectivity of TQn in the literature. 相似文献
17.
Consider sets S of hypercubes of side 2 in the discrete n-dimensional torus of side 4 with the property that every possible hypercube of side 2 has a nonempty intersection with some hypercube in S. The problem of minimizing the size of S is studied in two settings, depending on whether intersections between hypercubes in S are allowed or not. If intersections are not allowed, then one is asking for the smallest size of a non-extensible packing S ; this size is denoted by f(n). If intersections are allowed, then the structure S is called a blocking set. The smallest size of a blocking set S is denoted by h(n). By computer-aided techniques, it is shown that f(5)=12, f(6)=16, h(6)=15 and h(7)≤23. Also, non-extensible packings as well as blocking sets of certain small sizes are classified for n≤6. There is a direct connection between these problems and a covering problem originating from the football pools. 相似文献
18.
We study the problem of decomposing the vertex set V of a graph into two nonempty parts V1,V2 which induce subgraphs where each vertex v∈V1 has degree at least a(v) inside V1 and each v∈V2 has degree at least b(v) inside V2. We give a polynomial-time algorithm for graphs with bounded treewidth which decides if a graph admits a decomposition, and gives such a decomposition if it exists. This result and its variants are then applied to designing polynomial-time approximation schemes for planar graphs where a decomposition does not necessarily exist but the local degree conditions should be met for as many vertices as possible. 相似文献
19.
Damianos Gavalas Charalampos Konstantopoulos Konstantinos Mastakas Grammati Pantziou Nikolaos Vathis 《Information Processing Letters》2015
In this article we present approximation algorithms for the Arc Orienteering Problem (AOP). We propose a polylogarithmic approximation algorithm in directed graphs, while in undirected graphs we give a (6+?+o(1)) and a (4+?)-approximation algorithm for arbitrary instances and instances of unit profit, respectively. Also, an inapproximability result for the AOP is obtained as well as approximation algorithms for the Mixed Orienteering Problem. 相似文献
20.
A polygon P admits a sweep if two mobile guards can detect an unpredictable, moving target inside P , no matter how fast the target moves. Two guards move on the polygon boundary and are required to always be mutually visible. The objective of this study is to find an optimum sweep such that the sum of the distances travelled by the two guards in the sweep is minimized. We present an O(n2) time and O(n) space algorithm for optimizing this metric, where n is the number of vertices of the given polygon. Our result is obtained by reducing this problem to finding a shortest path between two nodes in a graph of size O(n). 相似文献