Search results for "Time complexity"
showing 10 items of 99 documents
Entropic Profiles, Maximal Motifs and the Discovery of Significant Repetitions in Genomic Sequences
2014
The degree of predictability of a sequence can be measured by its entropy and it is closely related to its repetitiveness and compressibility. Entropic profiles are useful tools to study the under- and over-representation of subsequences, providing also information about the scale of each conserved DNA region. On the other hand, compact classes of repetitive motifs, such as maximal motifs, have been proved to be useful for the identification of significant repetitions and for the compression of biological sequences. In this paper we show that there is a relationship between entropic profiles and maximal motifs, and in particular we prove that the former are a subset of the latter. As a furt…
A Guaranteed performance of a green data center based on the contribution of vital nodes
2016
International audience; In order to satisfy the need for the critical computing resources, many data center architectures proposed to house a huge number of network devices. These devices are used to achieve the highest performance in case of full utilization of the network. However, the peak capacity of the network is rarely reached. Consequently, many devices are set into idle state and cause a huge energy waste leading to a non-proportionality between the network load and the energy consumed. In this paper, we propose a power-aware routing algorithm that saves energy consumption with a negligible trade-off on the performance of the network. The idea is to keep active only the source and …
On the Computational Complexity of Binary and Analog Symmetric Hopfield Nets
2000
We investigate the computational properties of finite binary- and analog-state discrete-time symmetric Hopfield nets. For binary networks, we obtain a simulation of convergent asymmetric networks by symmetric networks with only a linear increase in network size and computation time. Then we analyze the convergence time of Hopfield nets in terms of the length of their bit representations. Here we construct an analog symmetric network whose convergence time exceeds the convergence time of any binary Hopfield net with the same representation length. Further, we prove that the MIN ENERGY problem for analog Hopfield nets is NP-hard and provide a polynomial time approximation algorithm for this p…
Descriptive Complexity, Lower Bounds and Linear Time
1999
This paper surveys two related lines of research: Logical characterizations of (non-deterministic) linear time complexity classes, and non-expressibility results concerning sublogics of existential second-order logic. Starting from Fagin’s fundamental work there has been steady progress in both fields with the effect that the weakest logics that are used in characterizations of linear time complexity classes are closely related to the strongest logics for which inexpressibility proofs for concrete problems have been obtained. The paper sketches these developments and highlights their connections as well as the obstacles that prevent us from closing the remaining gap between both kinds of lo…
Attentional vs computational complexity measures in observing paintings
2009
Because of the great heterogeneity of subjects and styles, esthetic perception delineates a special and elusive field of research in vision, which represents an interesting challenge for cognitive science tools. With specific regard to the role of visual complexity, in this paper we present an experiment aimed to measure this dimension in a heterogeneous set of paintings. We compared perceived time complexity measures - based on a temporal estimation paradigm - with physical and statistical properties of the paintings, obtaining a strong correlation between psychological and computational results.
The absolute center of a unicyclic network
1989
Abstract A unicyclic network is one generalization of a tree network. In this paper we examine the problem of finding an absolute center of a unicyclic network. We show that this problem can be solved in linear time with respect to the number of vertices in the network.
Application of Statistical Process Control to Continuous Processes
2002
Control charts represent an efficient and easy tool to assure the state of statistical quality control in a manufacturing process. These tools are also implemented in continuous processes, where the critical parameters are often monitored by on line sensors measuring data with short time intervals. In this paper a continuous process is monitored by using control charts and its dynamic is modeled through linear time series that allow the effects of the autocorrelation to be eliminated. In this way, the control charts can operate on residuals that result identically and independently distributed. A statistical analysis on EWMA, CUSUM and control charts for individual measurements has been car…
Numerical experiments with a parallel fast direct elliptic solver on Cray T3E
1997
A parallel fast direct O(N log N) solver is shortly described for linear systems with separable block tridiagonal matrices. A good parallel scalability of the proposed method is demonstrated on a Cray T3E parallel computer using MPI in communication. Also, the sequential performance is compared with the well-known BLKTRI-implementation of the generalized. cyclic reduction method using a single processor of Cray T3E.
A PARALLEL ALGORITHM FOR ANALYZING CONNECTED COMPONENTS IN BINARY IMAGES
1992
In this paper, a parallel algorithm for analyzing connected components in binary images is described. It is based on the extension of the Cylindrical Algebraic Decomposition (CAD) to a two-dimensional (2D) discrete space. This extension allows us to find the number of connected components, to determine their connectivity degree, and to solve the visibility problem. The parallel implementation of the algorithm is outlined and its time/space complexity is given.
Longest Motifs with a Functionally Equivalent Central Block
2004
International audience; This paper presents a generalization of the notion of longest repeats with a block of k don't care symbols introduced by [Crochemore et al., LATIN 2004] (for k fixed) to longest motifs composed of three parts: a first and last that parameterize match (that is, match via some symbol renaming, initially unknown), and a functionally equivalent central block. Such three-part motifs are called longest block motifs. Different types of functional equivalence, and thus of matching criteria for the central block are considered, which include as a subcase the one treated in [Crochemore et al., LATIN 2004] and extend to the case of regular expressions with no Kleene closure or …