共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
3.
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. 相似文献
4.
We study the state complexity of certain simple languages. If A is an alphabet of k letters, then a k-language is a nonempty set of words of length k, that is, a uniform language of length k. We show that the minimal state complexity of a k-language is k+2, and the maximal, (kk−1−1)/(k−1)+2k+1. We prove constructively that, for every i between the minimal and maximal bounds, there is a language of state complexity i. We introduce a class of automata accepting sets of words that are permutations of A; these languages define a complete hierarchy of complexities between k2−k+3 and 2k+1. The languages of another class of automata, based on k-ary trees, define a complete hierarchy of complexities between 2k+1 and (kk−1−1)/(k−1)+2k+1. This provides new examples of uniform languages of maximal complexity. 相似文献
5.
We show how to support efficient back traversal in a unidirectional list, using small memory and with essentially no slowdown in forward steps. Using O(lgn) memory for a list of size n, the i’th back-step from the farthest point reached so far takes O(lgi) time in the worst case, while the overhead per forward step is at most ? for arbitrary small constant ?>0. An arbitrary sequence of forward and back steps is allowed. A full trade-off between memory usage and time per back-step is presented: k vs. kn1/k and vice versa. Our algorithms are based on a novel pebbling technique which moves pebbles on a virtual binary, or n1/k-ary, tree that can only be traversed in a pre-order fashion. 相似文献
6.
7.
Matroid theory gives us powerful techniques for understanding combinatorial optimization problems and for designing polynomial-time algorithms. However, several natural matroid problems, such as 3-matroid intersection, are NP-hard. Here we investigate these problems from the parameterized complexity point of view: instead of the trivial nO(k) time brute force algorithm for finding a k-element solution, we try to give algorithms with uniformly polynomial (i.e., f(k)⋅nO(1)) running time. The main result is that if the ground set of a represented linear matroid is partitioned into blocks of size ?, then we can determine in randomized time f(k,?)⋅nO(1) whether there is an independent set that is the union of k blocks. As a consequence, algorithms with similar running time are obtained for other problems such as finding a k-element set in the intersection of ? matroids, or finding k terminals in a network such that each of them can be connected simultaneously to the source by ? disjoint paths. 相似文献
8.
We prove an explicit bound on the radius of a ball centered at the origin which is guaranteed to contain all bounded connected components of a semi-algebraic set S⊂Rk defined by a weak sign condition involving s polynomials in Z[X1,…,Xk] having degrees at most d, and whose coefficients have bitsizes at most τ. Our bound is an explicit function of s,d,k and τ, and does not contain any undetermined constants. We also prove a similar bound on the radius of a ball guaranteed to intersect every connected component of S (including the unbounded components). While asymptotic bounds of the form 2τdO(k) on these quantities were known before, some applications require bounds which are explicit and which hold for all values of s,d,k and τ. The bounds proved in this paper are of this nature. 相似文献
9.
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. 相似文献
10.
In this paper we focus on the minimal deterministic finite automaton Sk that recognizes the set of suffixes of a word w up to k errors. As first result we give a characterization of the Nerode’s right-invariant congruence that is associated with Sk. This result generalizes the classical characterization described in [A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. Chen, J. Seiferas, The smallest automaton recognizing the subwords of a text, Theoretical Computer Science, 40, 1985, 31–55]. As second result we present an algorithm that makes use of Sk to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r of a text, where r is the repetition index of w. Moreover, we give some experimental results on some well-known words, like prefixes of Fibonacci and Thue-Morse words. Finally, we state a conjecture and an open problem on the size and the construction of the suffix automaton with mismatches. 相似文献
11.
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. 相似文献
12.
The most natural and perhaps most frequently used method for testing membership of an individual tuple in a conjunctive query is based on searching trees of partial solutions, or search-trees. We investigate the question of evaluating conjunctive queries with a time-bound guarantee that is measured as a function of the size of the optimal search-tree. We provide an algorithm that, given a database D, a conjunctive query Q, and a tuple a, tests whether Q(a) holds in D in time bounded by a polynomial in (sn)logk(sn)loglogn and nr, where n is the size of the domain of the database, k is the number of bound variables of the conjunctive query, s is the size of the optimal search-tree, and r is the maximum arity of the relations. In many cases of interest, this bound is significantly smaller than the nO(k) bound provided by the naive search-tree method. Moreover, our algorithm has the advantage of guaranteeing the bound for any given conjunctive query. In particular, it guarantees the bound for queries that admit an equivalent form that is much easier to evaluate, even when finding such a form is an NP-hard task. Concrete examples include the conjunctive queries that can be non-trivially folded into a conjunctive query of bounded size or bounded treewidth. All our results translate to the context of constraint-satisfaction problems via the well-publicized correspondence between both frameworks. 相似文献
13.
Given a digraph D, the Minimum Leaf Out-Branching problem (MinLOB) is the problem of finding in D an out-branching with the minimum possible number of leaves, i.e., vertices of out-degree 0. We prove that MinLOB is polynomial-time solvable for acyclic digraphs. In general, MinLOB is NP-hard and we consider three parameterizations of MinLOB. We prove that two of them are NP-complete for every value of the parameter, but the third one is fixed-parameter tractable (FPT). The FPT parameterization is as follows: given a digraph D of order n and a positive integral parameter k, check whether D contains an out-branching with at most n−k leaves (and find such an out-branching if it exists). We find a problem kernel of order O(k2) and construct an algorithm of running time O(2O(klogk)+n6), which is an ‘additive’ FPT algorithm. We also consider transformations from two related problems, the minimum path covering and the maximum internal out-tree problems into MinLOB, which imply that some parameterizations of the two problems are FPT as well. 相似文献
14.
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. 相似文献
15.
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. 相似文献
16.
Given a simple polygon P of n vertices, the watchman route problem asks for a shortest (closed) route inside P such that each point in the interior of P can be seen from at least one point along the route. In this paper, we present a simple, linear-time algorithm for computing a watchman route of length at most two times that of the shortest watchman route. The best known algorithm for computing a shortest watchman route takes O(n4logn) time, which is too complicated to be suitable in practice. 相似文献
17.
The software package Qcompiler (Chen and Wang 2013) provides a general quantum compilation framework, which maps any given unitary operation into a quantum circuit consisting of a sequential set of elementary quantum gates. In this paper, we present an extended software OptQC , which finds permutation matrices P and Q for a given unitary matrix U such that the number of gates in the quantum circuit of U=QTPTU′PQ is significantly reduced, where U′ is equivalent to U up to a permutation and the quantum circuit implementation of each matrix component is considered separately. We extend further this software package to make use of high-performance computers with a multiprocessor architecture using MPI. We demonstrate its effectiveness in reducing the total number of quantum gates required for various unitary operators. 相似文献
19.
We consider a two-edge connected, undirected graph G=(V,E), with n nodes and m non-negatively real weighted edges, and a single source shortest paths tree (SPT) T of G rooted at an arbitrary node r. If an edge in T is temporarily removed, it makes sense to reconnect the nodes disconnected from the root by adding a single non-tree edge, called a swap edge , instead of rebuilding a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select a best possible swap edge. In this paper we focus on the most prominent one, that is the minimization of the average distance between the root and the disconnected nodes. To this respect, we present an O(mlog2n) time and O(m) space algorithm to find a best swap edge for every edge of T, thus improving for m=o(n2/log2n) the previously known O(n2) time and space complexity algorithm. 相似文献
20.
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. 相似文献