Narrow Results

This paper introduces a novel nonlinear fractal fractional model to comprehensively analyze influenza epidemics. By integrating fractional calculus and considering nonlinear interactions among individuals, the model utilizes the Fractal-Fractional (FF) operator. This operator, combining fractal and fractional calculus, establishes a unique framework for investigating influenza virus propagation dynamics and potential vaccination strategies. Amid growing concerns over influenza outbreaks, fractional derivatives are employed to address intricate challenges. The proposed model sheds light on virus spread dynamics and countermeasures. The integration of the FF operator enriches analysis, while the application of the fixed point theory of Schauder and Banach demonstrates solution existence and uniqueness. Model validation employs numerical simulations with MATLAB12̂ and the Adams–Bashforth method, confirming its ability to capture influenza propagation dynamics accurately. Ulam–Hyers stability techniques ensure the model’s reliability. Beyond its scientific contributions, the model underscores the significance of studying influenza epidemics via mathematical modeling in understanding disease dynamics and guiding effective intervention strategies. Through a synergy of mathematical innovation and epidemiological insights, this study establishes a robust foundation for more effective strategies against influenza epidemics.

In this paper, we represent vector bundles over a regular algebraic curve as pairs of lattices over the maximal orders of its function field and we give polynomial time algorithms for several tasks: computing determinants of vector bundles, kernels and images of global homomorphisms, isomorphisms between vector bundles, cohomology groups, extensions, and splitting into a direct sum of indecomposables. Most algorithms are deterministic except for computing isomorphisms when the base field is infinite. Some algorithms are only polynomial time if we may compute Hermite forms of pseudo-matrices in polynomial time. All algorithms rely exclusively on algebraic operations in function fields. For applications, we give an algorithm enumerating isomorphism classes of vector bundles on an elliptic curve, and to construct algebraic geometry codes over vector bundles. We implement all our algorithms into a SageMath package.

In this paper, we develop four numerical methods for computing the singular value decomposition (SVD) of large sparse matrices on a shared-memory multiprocessor architecture. We particularly consider the SVD of unstructured sparse matrices in which the number of rows may be substantially larger or smaller than the number of columns. We emphasize Lanczos, block-Lanczos, subspace iteration and the trace minimization methods for determining a select number of smallest singular triplets (singular values and corresponding left- and right-singular vectors) for sparse matrices. The target architectures for implementations of such methods include the Alliant FX/80 and the Cray-2S/4–128. This algorithmic research is particularly motivated by recent information-retrieval techniques in which approximations to large sparse term-document matrices are needed, and by nonlinear inverse problems arising from seismic reflection tomography applications.

The diversity of application areas relying on tree-structured data results in wide interest in algorithms which determine differences or similarities among trees. One way of measuring the similarity between trees is to find the smallest common superstructure or supertree, where common elements are typically defined in terms of a mapping or embedding. In the simplest case, a supertree will contain exact copies of each input tree, so that for each input tree, each vertex of a tree can be mapped to a vertex in the supertree such that each edge maps to the corresponding edge. More general mappings allow for the extraction of more subtle common elements captured by looser definitions of similarity.

We consider supertrees under the general mapping of minor containment. Minor containment generalizes both subgraph isomorphism and topological embedding; as a consequence of this generality, however, it is NP-complete to determine whether or not G is a minor of H, even for genreal trees. By focusing on trees of bounded degree, we obtain an O(n³) algorithm which determines the smallest tree T such that both of the input trees are minors of T, even when the trees are assumed to be unrooted and unordered.

We present a novel extension to passbits providing significant reduction to unsuccessful search lengths for open addressing collision resolution hashing. Both the experimental and analytical results presented demonstrate the dramatic reductions possible. This method does not restrict the hashing table configuration parameters and utilizes very little additional storage space per bucket. The runtime performance for insertion is essentially the same as for ordinary open addressing with passbits; the successful search lengths remain the same as for open addressing without passbits. For any given loading factor, the unsuccessful search length can be made to be arbitrarily close to one bucket access.

A fundamental problem in music is to classify songs according to their rhythm. A rhythm is represented by a sequence of “Quick” (Q) and “Slow” (S) symbols, which correspond to the (relative) duration of notes, such that S = 2Q. In this paper, we present an efficient algorithm for locating the maximum-length substring of a music text t that can be covered by a given rhythm r.

We study the problem of scheduling independent unit-time parallel jobs on hypercubes. A parallel job has to be scheduled between its release time and deadline on a subcube of processors. The objective is to maximize the number of early jobs. Jobs' intervals of feasibility have to be nested. We provide a polynomial time algorithm for the problem.

The graph isomorphism problem is to check if two given graphs are isomorphic. Graph isomorphism is a well studied problem and numerous algorithms are available for its solution. In this paper we present algorithms for graph isomorphism that employ the spectra of graphs. An open problem that has fascinated many a scientist is if there exists a polynomial time algorithm for graph isomorphism. Though we do not solve this problem in this paper, the algorithms we present take polynomial time. These algorithms have been tested on a good collection of instances. However, we have not been able to prove that our algorithms will work on all possible instances. In this paper, we also give a new construction for cospectral graphs.

DNA microarray technology has proven to be an invaluable tool for molecular biologists. Microarrays are used extensively in SNP detection, genomic hybridization, alternative splicing and gene expression profiling. However the manufacturers of the microarrays are often stuck with the problem of minimizing the effects of unwanted illumination (border length minimization (BLM)) which is a hard combinatorial problem. In this paper we prove that the BLM problem on a rectangular grid is NP-hard – this however does not mean the BLM problem on a square grid is NP-hard.

We also give the first integer linear programming (ILP) formulation to solve BLM problem optimally. Experimental results indicate that our ILP method produces superior results (both in runtime and cost) compared to the current state of the art algorithms to solve the BLM problem optimally.

In this paper, we present techniques and algorithms for processing an offline sequence of update and query operations and for related problems. The update can be either all insertions or all deletions. The types of query include min-gap, max-gap, predecessor, and successor. Most problems we consider are solved optimally in linear time by our algorithms, which are based on new geometric modeling and interesting techniques. We also discuss some applications to which our algorithms and techniques can be applied to yield efficient solutions. These applications include an offline horizontal ray shooting problem and a shortest arc covering problem on a circle.

Algorithmic combinatorics on partial words, or sequences of symbols over a finite alphabet that may have some do-not-know symbols or holes, has been developing in the past few years. Applications can be found, for instance, in molecular biology for the sequencing and analysis of DNA, in bio-inspired computing where partial words have been considered for identifying good encodings for DNA computations, and in data compression. In this paper, we focus on two areas of algorithmic combinatorics on partial words, namely, pattern avoidance and subword complexity. We discuss recent contributions as well as a number of open problems. In relation to pattern avoidance, we classify all binary patterns with respect to partial word avoidability, we classify all unary patterns with respect to hole sparsity, and we discuss avoiding abelian powers in partial words. In relation to subword complexity, we generate and count minimal Sturmian partial words, we construct de Bruijn partial words, and we construct partial words with subword complexities not achievable by full words (those without holes).

Abelian periodicity of strings has been studied extensively over the last years. In 2006 Constantinescu and Ilie defined the abelian period of a string and several algorithms for the computation of all abelian periods of a string were given. In contrast to the classical period of a word, its abelian version is more flexible, factors of the word are considered the same under any internal permutation of their letters. We show two O(|y|²) algorithms for the computation of all abelian periods of a string y. The first one maps each letter to a suitable number such that each factor of the string can be identified by the unique sum of the numbers corresponding to its letters and hence abelian periods can be identified easily. The other one maps each letter to a prime number such that each factor of the string can be identified by the unique product of the numbers corresponding to its letters and so abelian periods can be identified easily. We also define weak abelian periods on strings and give an O(|y|log(|y|)) algorithm for their computation, together with some other algorithms for more basic problems.

The definition of bisimulation suggests a partition-refinement step, which we show to be suitable for a saturation-based implementation. We compare our fully symbolic saturation-based implementation with the fastest extant bisimulation algorithms over a set of benchmarks, and conclude that it appears to be the fastest algorithm capable of computing the largest bisimulation over very large quotient spaces.

This paper describes a random model for chemical graphs that captures the notion of valence along with algorithms to generate chemical graphs using this model. An approach for computing the probability that a particular chemical graph is generated under this model is provided. The model is also used to provide theoretical bounds on the accuracy of a class of canonical labeling algorithms for a class of hydrocarbons.

Two mobile agents, starting at arbitrary, possibly different times from arbitrary nodes of an unknown network, have to meet at some node. Agents move in synchronous rounds: in each round an agent can either stay at the current node or move to one of its neighbors. Agents have different labels which are positive integers. Each agent knows its own label, but not the label of the other agent. In traditional formulations of the rendezvous problem, meeting is accomplished when the agents get to the same node in the same round. We want to achieve a more demanding goal, called rendezvous with detection: agents must become aware that the meeting is accomplished, simultaneously declare this and stop. This awareness depends on how an agent can communicate to the other agent its presence at a node. We use two variations of the arguably weakest model of communication, called the beeping model, introduced in [8]. In each round an agent can either listen or beep. In the local beeping model, an agent hears a beep in a round if it listens in this round and if the other agent is at the same node and beeps. In the global beeping model, an agent hears a loud beep in a round if it listens in this round and if the other agent is at the same node and beeps, and it hears a soft beep in a round if it listens in this round and if the other agent is at some other node and beeps.

We first present a deterministic algorithm of rendezvous with detection working, even for the local beeping model, in an arbitrary unknown network in time polynomial in the size of the network and in the length of the smaller label (i.e., in the logarithm of this label). However, in this algorithm, agents spend a lot of energy: the number of moves that an agent must make, is proportional to the time of rendezvous. It is thus natural to ask if bounded-energy agents, i.e., agents that can make at most c moves, for some integer c, can always achieve rendezvous with detection as well. This is impossible for some networks of unbounded size. Hence we rephrase the question: Can bounded-energy agents always achieve rendezvous with detection in bounded-size networks? We prove that the answer to this question is positive, even in the local beeping model but, perhaps surprisingly, this ability comes at a steep price of time: the meeting time of bounded-energy agents is exponentially larger than that of unrestricted agents. By contrast, we show an algorithm for rendezvous with detection in the global beeping model that works for bounded-energy agents (in bounded-size networks) as fast as for unrestricted agents.

We are interested in regular expressions and transducers that represent word relations in an alphabet-invariant way — for example, the set of all word pairs $u,v$ where $v$ is a prefix of $u$ independently of what the alphabet is. Current software systems of formal language objects do not have a mechanism to define such objects. We define transducers in which transition labels involve what we call set specifications, some of which are alphabet invariant. In fact, we give a more broad definition of automata-type objects, called labelled graphs, where each transition label can be any string, as long as that string represents a subset of a certain monoid. Then, the behavior of the labelled graph is a subset of that monoid. We do the same for regular expressions. We obtain extensions of a few classic algorithmic constructions on ordinary regular expressions and transducers at the broad level of labelled graphs and in such a way that the computational efficiency of the extended constructions is not sacrificed. For transducers with set specs we obtain further algorithms that can be applied to questions about independent regular languages as well as a decision question about synchronous transducers.

We present a more efficient CREW PRAM algorithm for integer sorting. This algorithm sorts $n$ integers in $\{0,1,2,\dots ,n^{1/2}\}$ in $O({(logn)}^{3/2}/loglogn)$ time and $O(n(logn/loglogn{)}^{1/2})$ operations. It also sorts $n$ integers in $\{0,1,2,\dots ,n-1\}$ in $O({(logn)}^{3/2}/loglogn)$ time and $O(n{(logn/loglogn)}^{1/2}logloglogn)$ operations. Previous best algorithm [15] on both cases has time complexity $O(logn)$ but operation complexity $O(n{(logn)}^{1/2})$.

We consider the problem of evaluating a boolean function P(x₁,…,x_n), by asking queries of the form “x_i=?”, and receiving answers which may not always be truthful. Assuming that the total number of lies does not exceed E, we present an algorithm with cost O(n+s_PE+t_PE), where s_P is the maximal size of a minterm of P(x) and t_P ‘is the maximal size of a maxterm. We also prove that if P is monotone, then any algorithm for evaluating P must ask Ω(s_PE+t_PE) queries for some input.

In this paper we present a strategy to maintain a dynamic optimal binary search tree. The algorithms for insertion and deletion use swapping as the basic operation. Since in average situations the tree reorganization is limited to local changes, it can be favourably compared with the local balancing algorithms. The present algorithms dynamically maintain the optimal tree with an amortized time of O(log₂ n), where n is the total number of nodes in the tree. In the worst case situations, the algorithms take only O(n) time. This is significant when they are compared to the algorithms producing static optimal binary search trees.

In this paper we examine the edge searching problem on pseudo 3-sided solid orthoconvex grids. We define a similar problem which we call modified edge searching, and we derive a relation among the original edge searching problem and the modified one. Then, for the modified edge searching problem, we show that there are searching strategies that possess several properties regarding the way the grid is searched. These strategies allow us to obtain a closed formula that expresses the minimum number of searchers required to search a pseudo 3-sided solid orthoconvex grid. From that formula and a rather straight forward algorithm we can show that the problem is in P. We obtain a parallel version of that algorithm that places the problem in NC. For the case of sequential algorithms, we derive an optimal algorithm that solves the problem in O(m) time where m is the number of points necessary to describe the orthoconvex grid. Another important feature of our method is that it also suggests an optimal searching strategy that consists of O(n) steps, where n is the number of nodes of the grid.