Search

Circuits in a graph are interesting structures and identifying them is of an important relevance for many applications. However, enumerating circuits is known to be a difficult problem, since their number can grow exponentially. In this paper, we propose fast parallel approaches for enumerating elementary circuits of directed graphs based on graphics processing unit (GPU). Our algorithms are based on a massive exploration of the graph in a breadth-first search strategy. Algorithm V-FEC explores the graph starting from different vertices simultaneously. To further reduce the search space, we present T-FEC, another algorithm that uses triplets as an initial set to start exploring. To the best of our knowledge, those are the first parallel GPU-based algorithms for finding all circuits of a given graph. In addition, they find circuits of a given length and circuits with a specific vertex or edge. The evaluation results show that the proposed approaches achieve up to 190x speed-up over Johnson's algorithm, one of the most efficient sequential algorithms for finding circuits. [ABSTRACT FROM AUTHOR]

The problem of finding bipartite (Tanner) graphs with given degree sequences that have large girth and few short cycles is of great interest in many applications including construction of good low-density parity-check (LDPC) codes. In this paper, we prove that for given integers $\alpha $ , $\beta $ , and $\gamma $ , and degree sequences $\pi $ and $\pi '$ , the problem of determining whether there exists a simple bipartite graph with degree sequences $(\pi, \pi ')$ that has at most $\alpha $ ($\beta $ and $\gamma $) cycles of length four (six and eight, respectively) is NP-complete. This is proved by a two-step polynomial-time reduction from the 3-Partition Problem. On the other hand, using connections to linear hypergraphs, we prove that given the degree sequence $\pi $ , a polynomial time algorithm can be devised to determine whether there exists a bipartite graph whose degree sequence on one side of the bipartition is $\pi $ and has a girth of at least six. In addition to these complexity results, we devise a quasi-polynomial time algorithm that can construct a bipartite graph with given (irregular) degree sequences and a girth that increases logarithmically with the size of the graph. Compared to the well-known progressive-edge-growth (PEG) algorithm, the proposed method, in some cases, results in Tanner graphs with larger girth, particularly for scenarios where the degree sequences of the graph are strictly enforced. [ABSTRACT FROM AUTHOR]

In this paper, we present solution algorithms for the cycle hub location problem (CHLP), which seeks to locate p hub facilities that are connected by means of a cycle, and to assign non-hub nodes to hubs so as to minimize the total cost of routing flows through the network. This problem is useful in modeling applications in transportation and telecommunications systems, where large setup costs on the links and reliability requirements make cycle topologies a prominent network architecture. We present a branch-and-cut algorithm that uses a flow-based formulation and two families of mixed-dicut inequalities as a lower bounding procedure at nodes of the enumeration tree. We also introduce a metaheuristic based on greedy randomized adaptive search procedure to obtain initial upper bounds for the exact algorithm and to obtain feasible solutions for large-scale instances of the CHLP. Numerical results on a set of benchmark instances with up to 100 nodes and 8 hubs confirm the efficiency of the proposed solution algorithms. [ABSTRACT FROM AUTHOR]

Identification of rhythmic gene expression from metabolic cycles to circadian rhythms is crucial for understanding the gene regulatory networks and functions of these biological processes. Recently, two algorithms, JTK_CYCLE and ARSER, have been developed to estimate periodicity of rhythmic gene expression. JTK_CYCLE performs well for long or less noisy time series, while ARSER performs well for detecting a single rhythmic category. However, observing gene expression at high temporal resolution is not always feasible, and many scientists are interested in exploring both ultradian and circadian rhythmic categories simultaneously. In this paper, a new algorithm, named autoregressive Bayesian spectral regression (ABSR), is proposed. It estimates the period of time-course experimental data and classifies gene expression profiles into multiple rhythmic categories simultaneously. Through the simulation studies, it is shown that ABSR substantially improves the accuracy of periodicity estimation and clustering of rhythmic categories as compared to JTK_CYCLE and ARSER for the data with low temporal resolution. Moreover, ABSR is insensitive to rhythmic patterns. This new scheme is applied to existing time-course mouse liver data to estimate period of rhythms and classify the genes into ultradian, circadian, and arrhythmic categories. It is observed that 49.2% of the circadian profiles detected by JTK_CYCLE with 1-hour resolution are also detected by ABSR with only 4-hour resolution. [ABSTRACT FROM AUTHOR]

Due to the recent explosive growth of location-aware services based on mobile devices, predicting the next places of a user is of increasing importance to enable proactive information services. In this paper, we introduce a data-driven framework that aims to predict the user's next places using his/her past visiting patterns analyzed from mobile device logs. Specifically, the notion of the spatiotemporal-periodic (STP) pattern is proposed to capture the visits with spatiotemporal periodicity by focusing on a detail level of location for each individual. Subsequently, we present algorithms that extract the STP patterns from a user's past visiting behaviors and predict the next places based on the patterns. The experiment results obtained by using a real-world dataset show that the proposed methods are more effective in predicting the user's next places than the previous approaches considered in most cases. [ABSTRACT FROM AUTHOR]

In many applications requiring the study of the surface myoelectric signal (SMES) acquired in dynamic conditions, it is essential to have a quantitative evaluation of the quality of the collected signals. When the activation pattern of a muscle has to be obtained by means of single- or double-threshold statistical detectors, the background noise level enoise of the signal is a necessary input parameter. Moreover, the detection strategy of double-threshold detectors may be properly tuned when the SNR and the duty cycle (DC) of the signal are known. The aim of this paper is to present an algorithm for the estimation of e noise, SNR, and DC of an SMES collected during cyclic movements. The algorithm is validated on synthetic signals with statistical properties similar to those of SMES, as well as on more than 100 real signals. [ABSTRACT FROM PUBLISHER]

Glass models are frequently used to model gene regulatory networks. A distinct feature of the Glass model is that its dynamics can be formalized as paths through multi-dimensional binary hypercubes. In this paper, we report a broad range of results about Glass models that have been obtained by computing the binary codes that correspond to the hypercube paths. Specifically, we propose algorithmic methods for the synthesis of specific Glass networks based on these codes. In contrast to existing work, bi-periodic networks and networks possessing both stable equilibria and periodic trajectories are considered. The robustness of the attractor is also addressed, which gives rise to hypercube paths with nondominated nodes and double coils. These paths correspond to novel combinatorial problems, for which initial experimental results are presented. Finally, a classification of Glass networks with respect to their corresponding gene interaction graphs for three genes is presented. [ABSTRACT FROM AUTHOR]

This paper is focused on the derivation of some universal properties of capacity-approaching low-density parity-check (LDPC) code ensembles whose transmission takes place over memoryless binary-input output-symmetric (MBIOS) channels. Properties of the degree distributions, graphical complexity, and the number of fundamental cycles in the bipartite graphs are considered via the derivation of information-theoretic bounds. These bounds are expressed in terms of the target block/bit error probability and the gap (in rate) to capacity. Most of the bounds are general for any decoding algorithm, and some others are proved under belief propagation (BP) decoding. Proving these bounds under a certain decoding algorithm, validates them automatically also under any suboptimal decoding algorithm. A proper modification of these bounds makes them universal for the set of all MBIOS channels which exhibit a given capacity. Bounds on the degree distributions and graphical complexity apply to finite-length LDPC codes and to the asymptotic case of an infinite block length. The bounds are compared with capacity-approaching LDPC code ensembles under BP decoding, and they are shown to be informative and are easy to calculate. Finally, some interesting open problems are considered. [ABSTRACT FROM AUTHOR]

This paper presents several new properties of biorthogonal cosine modulated filter banks (CMFBs) and efficient algorithms for designing CMFBs with a very large number of subbands and very long filters. For a biorthogonal CMFB, we find the periodicity and symmetry of its overall transfer function and aliasing transfer functions which can be efficiently computed based on a decimated uniform discrete Fourier transform (DFT) analysis filter bank. By exploiting gradient information and 2Mth band conditions, efficient algorithms are proposed for designing both orthogonal and biorthogonal CMFBs. In addition, an efficient matrix inversion algorithm with O(N²) complexity is also presented. Several numerical examples and comparisons with many other existing methods are included to demonstrate the design performance and efficiency of the algorithms. [ABSTRACT FROM AUTHOR]

Abstract: An arc going out from a vertex x in a digraph is called an out-arc of x. Yao et al. [Discrete Appl. Math. 99 (2000) 245–249] proved that every strong tournament contains a vertex x such that all out-arcs of x are pancyclic. Recently, Yeo [J. Graph Theory 50 (2005) 212–219] proved that each 3-strong tournament contains two such vertices. In this paper, we confirm that Yeo''s result is also true for 2-strong tournaments. Our proof implies a polynomial algorithm to find two such vertices. [Copyright &y& Elsevier]

An adaptive oscillator is a system that can lock on to a time-varying input signal, synchronizing its output to both the frequency and phase of the input. A wavetable oscillator generates a periodic output by indexing into a lookup table that stores a single period of the waveform. An adaptive wavetable oscillator (AWO) combines these two ideas in a technique which separates the periodic output waveform from the parameters that control the adaptation of the frequency and phase of the waveform. This separation is advantageous because it decouples the state of the oscillator from the dynamics of the adaptation, allowing the process of synchronization to be interpreted as a simple gradient optimization on a cost function. The oscillations remain stable over a large and easily described range of parameter values, and analysis of the synchronization can proceed along lines familiar from standard adaptive systems. Key issues in the design of AWOs are: the class of admissible inputs, the shape of the wavetable, the parameters that will be controlled, and the adaptive algorithm that adjusts the parameters. This paper examines these issues through analysis and simulation, focusing on conditions that achieve the desired synchronization between output and input. [ABSTRACT FROM AUTHOR]

Abstract: In the last years, new variants of the minimum cycle basis (MCB) problem and new classes of cycle bases have been introduced, as motivated by several applications from disparate areas of scientific and technological inquiries. At present, the complexity status of the MCB problem has been settled only for undirected, directed, and strictly fundamental cycle bases. In this paper, we offer an unitary classification accommodating these three classes and further including the following four relevant classes: 2-bases (or planar bases), weakly fundamental cycle bases, totally unimodular cycle bases, and integral cycle bases. The classification is complete in that, for each ordered pair of classes considered, we either prove that holds for every graph or provide a counterexample graph for which . The seven notions of cycle bases are distinct (either or is exhibited for each pair ). All counterexamples proposed have been designed to be ultimately effective in separating the various algorithmic variants of the MCB problem naturally associated to each one of these seven classes. Furthermore, we provide a linear time algorithm for computing a minimum 2-basis of a graph. Finally, notice that the resolution of the complexity status of some of the remaining three classes would have an immediate impact on practical applications, as for instance in periodic railway timetabling, only integral cycle bases are of direct use. [Copyright &y& Elsevier]

Different versions of the notion of almost-periodicity are natural generalizations of the notion of periodicity. The notion of strict almost-periodicity appeared in symbolic dynamics, but later proved to be fruitful in mathematical logic and the theory of algorithms as well. In the paper, a class of essentially almost-periodic sequences (i.e., strictly almost-periodic sequences with an arbitrary prefix added at the beginning) is considered. It is proved that the property of essential almost-periodicity is preserved under finite-automaton transformations, as well as under the action of finite transducers. The class of essentially almost-periodic sequences is contained in the class of almost-periodic sequences. It is proved that this inclusion is strict. [ABSTRACT FROM AUTHOR]

This paper presents a new variant of the vehicle routing problem (VRP), the prize-collecting vehicle routing problem (PCVRP), which is derived from the hot rolling production of the iron and steel industry. One major characteristic of the PCVRP is that the customers need not be visited compulsorily but a prize can be collected from each customer when visited. Besides the capacity constraint, a task completion constraint is introduced and requires that the total demand of the visited customers should be no less than a predetermined amount. The main objective is a linear combination of three objectives: minimization of total distance traveled, minimization of vehicles used, and maximization of prizes collected. An iterated local search algorithm (ILS) based on very large-scale neighborhood (VLSN) using cyclic transfer is proposed for the PCVRP. Computational results of problem instances with up to 100 customers show the algorithm is efficient and effective. [ABSTRACT FROM AUTHOR]

The problem of finding all cycles in the exponentially growing state space of synchronous Boolean networks was studied in the paper by C. Farrow, J. Heidel, J. Maloney, and J. R. Scalar, "Equations for synchronous Boolean networks with biological applications," IEEE Trans. Neural Net- works, vol. 15, no. 2, pp. 348-354 Mar. 2004. No efficient algorithm was given to solve the problem. We show that even the determination of the number of fixed points (cycles of length 1) for monotone Boolean networks and the determination of the existence of fixed points for general Boolean networks are both strong NP-complete. [ABSTRACT FROM AUTHOR]