Mutually independent Hamiltonian cycles in alternating group graphs

The alternating group graph has been used as the underlying topology for many practical multicomputers, and has been extensively studied in the past. In this article, we will show that any alternating group graph AG _n , where n??3 is an integer, contains 2n?4 mutually independent Hamiltonian cycles. More specifically, let N=|V(AG _n )|, v _i ??V(AG _n ) for 1??i??N, and ??v ₁,v ₂,??,v _N ,v ₁?? be a Hamiltonian cycle of AG _n . We show that AG _n contains 2n?4 Hamiltonian cycles, denoted by $C_{l}=\langle v_{1},v_{2}^{l},\ldots,v_{N}^{l},v_{1}\rangle$ for 1??l??2n?4, such that $v_{i}^{l} \ne v_{i}^{l'}$ for all 2??i??N whenever l??l??. The result is optimal since each vertex of AG _n has exactly 2n?4 neighbors.     

Expansion of Self-Similar Functions in the Faber–Schauder System

Let Ω = A^N be a space of right-sided infinite sequences drawn from a finite alphabet A = {0,1}, N = {1,2,…}. Let ρ(x, y)Σ_k=1^∞|x _k ? y _k |2^?k be a metric on Ω = AN, and μ the Bernoulli measure on Ω with probabilities p₀, p₁ > 0, p₀ + p₁ = 1. Denote by B(x,ω) an open ball of radius r centered at ω. The main result of this paper \(\mu (B(\omega ,r))r + \sum\nolimits_{n = 0}^\infty {\sum\nolimits_{j = 0}^{{2^n} - 1} {{\mu _{n,j}}} } (\omega )\tau ({2^n}r - j)\), where τ(x) = 2min {x,1 ? x}, 0 ≤ x ≤ 1, (τ(x) = 0, if x < 0 or x > 1 ), \({\mu _{n,j}}(\omega ) = (1 - {p_{{\omega _{n + 1}}}})\prod _{k = 1}^n{p_{{\omega _k}}} \oplus {j_k}\), \(j = {j_1}{2^{n - 1}} + {j_2}{2^{n - 2}} + ... + {j_n}\). The family of functions 1, x, τ(2 ⁿ r ? j), j = 0,1,…, 2 ⁿ ? 1, n = 0,1,…, is the Faber–Schauder system for the space C([0,1]) of continuous functions on [0, 1]. We also obtain the Faber–Schauder expansion for Lebesgue’s singular function, Cezaro curves, and Koch–Peano curves. Article is published in the author’s wording.     

General Independence Sets in Random Strongly Sparse Hypergraphs

We analyze the asymptotic behavior of the j-independence number of a random k-uniform hypergraph H(n, k, p) in the binomial model. We prove that in the strongly sparse case, i.e., where \(p = c/\left( \begin{gathered} n - 1 \hfill \\ k - 1 \hfill \\ \end{gathered} \right)\) for a positive constant 0 < c ≤ 1/(k ? 1), there exists a constant γ(k, j, c) > 0 such that the j-independence number α _j (H(n, k, p)) obeys the law of large numbers \(\frac{{{\alpha _j}\left( {H\left( {n,k,p} \right)} \right)}}{n}\xrightarrow{P}\gamma \left( {k,j,c} \right)asn \to + \infty \) Moreover, we explicitly present γ(k, j, c) as a function of a solution of some transcendental equation.     

The identity problem of finitely generated bi-ideals

Finitely generated bi-ideals with letters from a selected alphabet A are considered. We solve the equivalence problem for generating systems of bi-ideals, i.e., look for an effective procedure which provides the means of determining if two generating systems \({\langle u_0, . . . , u_{m-1} \rangle}\) and \({\langle v_0, . . . , v_{n-1} \rangle}\) represent equal or different bi-ideals. We offer a method of constructing, for every generating system \({\langle u_0, . . . , u_{m-1} \rangle}\) , an equivalent generating system \({\langle u^{\prime}_{0}, . . . , u^{\prime}_{m-1} \rangle}\) with differing members. We also describe an algorithm for deciding if two generating systems \({\langle u_0, u_1 \rangle}\) and \({\langle v_0, v_1 \rangle}\) are equivalent or not. For a general case, the problem of existence of such an algorithm remains open.     

Linear Time Algorithms for Generalizations of the Longest Common Substring Problem

In its simplest form, the longest common substring problem is to find a longest substring common to two or multiple strings. Using (generalized) suffix trees, this problem can be solved in linear time and space. A first generalization is the k -common substring problem: Given m strings of total length n, for all k with 2≤k≤m simultaneously find a longest substring common to at least k of the strings. It is known that the k-common substring problem can also be solved in O(n) time (Hui in Proc. 3rd Annual Symposium on Combinatorial Pattern Matching, volume 644 of Lecture Notes in Computer Science, pp. 230–243, Springer, Berlin, 1992). A further generalization is the k -common repeated substring problem: Given m strings T ⁽¹⁾,T ⁽²⁾,…,T ^(m) of total length n and m positive integers x ₁,…,x _m , for all k with 1≤k≤m simultaneously find a longest string ω for which there are at least k strings \(T^{(i_{1})},T^{(i_{2})},\ldots,T^{(i_{k})}\) (1≤i ₁<i ₂<???<i _k ≤m) such that ω occurs at least \(x_{i_{j}}\) times in \(T^{(i_{j})}\) for each j with 1≤j≤k. (For x ₁=???=x _m =1, we have the k-common substring problem.) In this paper, we present the first O(n) time algorithm for the k-common repeated substring problem. Our solution is based on a new linear time algorithm for the k-common substring problem.     

Some properties of the disjunctive languages contained in <Emphasis Type="Italic">Q</Emphasis>

The set of all primitive words Q over an alphabet X was first defined and studied by Shyr and Thierrin (Proceedings of the 1977 Inter. FCT-Conference, Poznan, Poland, Lecture Notes in Computer Science 56. pp. 171–176 (1977)). It showed that for the case |X| ≥ 2, the set along with \({Q^{(i)} = \{f^i\,|\,f \in Q\}, i\geq 2}\) are all disjunctive. Since then these disjunctive sets are often be quoted. Following Shyr and Thierrin showed that the half sets \({Q_{ev} = \{f \in Q\,|\,|f| = {\rm even}\}}\) and Q _od = Q \ Q _ev of Q are disjunctive, Chien proved that each of the set \({Q_{p,r}= \{u\in Q\,|\,|u|\equiv r\,(mod\,p) \},\,0\leq r < p}\) is disjunctive, where p is a prime number. In this paper, we generalize this property to that all the languages \({Q_{n,r}= \{u\in Q\,|\,|u|\equiv r\,(mod\,n) \},\, 0\leq r < n}\) are disjunctive languages, where n is any positive integer. We proved that for any n ≥ 1, k ≥ 2, (Q _n,0) ^k are all regular languages. Some algebraic properties related to the family of languages {Q _n,r | n ≥ 2, 0 ≤ r < n } are investigated.     

Polylogarithms and the Asymptotic Formula for the Moments of Lebesgue’s Singular Function

Recall that Lebesgue’s singular function L(t) is defined as the unique solution to the equation L(t) = qL(2t) + pL(2t ? 1), where p, q > 0, q = 1 ? p, p ≠ q. The variables M _n = ∫₀¹t ⁿ dL(t), n = 0,1,… are called the moments of the function The principal result of this work is \({M_n} = {n^{{{\log }_2}p}}{e^{ - \tau (n)}}(1 + O({n^{ - 0.99}}))\), where the function τ(x) is periodic in log₂x with the period 1 and is given as \(\tau (x) = \frac{1}{2}1np + \Gamma '(1)lo{g_2}p + \frac{1}{{1n2}}\frac{\partial }{{\partial z}}L{i_z}( - \frac{q}{p}){|_{z = 1}} + \frac{1}{{1n2}}\sum\nolimits_{k \ne 0} {\Gamma ({z_k})L{i_{{z_k} + 1}}( - \frac{q}{p})} {x^{ - {z_k}}}\), \({z_k} = \frac{{2\pi ik}}{{1n2}}\), k ≠ 0. The proof is based on poissonization and the Mellin transform.     

Formule di quadratura di tipo gaussiano con valori delle derivate dell'integrando

The coefficientsA _hi (m,s) and the nodesx _i (m,s) for Gaussian-type quadrature formulae

$$\int\limits_{ - 1}^1 {f(x)dx = \mathop \sum \limits_{h = 0}^{2s} \mathop \sum \limits_{i = 1}^m } A_{hi} \cdot f^{(h)} (x_i )$$     

Star reduction among minimal length addition chains

An addition chain for a natural number n is a sequence \({1=a_0 < a_1 < \cdots < a_r=n}\) of numbers such that for each 0 < i ≤ r, a _i  = a _j  + a _k for some 0 ≤ k ≤ j < i. The minimal length of an addition chain for n is denoted by ?(n). If j = i ? 1, then step i is called a star step. We show that there is a minimal length addition chain for n such that the last four steps are stars. Then we conjecture that there is a minimal length addition chain for n such that the last \({\lfloor\frac{\ell(n)}{2}\rfloor}\)-steps are stars. We verify that the conjecture is true for all numbers up to 2¹⁸. An application of the result and the conjecture to generate a minimal length addition chain reduce the average CPU time by 23–29% and 38–58% respectively, and memory storage by 16–18% and 26–45% respectively for m-bit numbers with 14 ≤ m ≤ 22.     

Linear complexity problems of level sequences of Euler quotients and their related binary sequences欧拉商的权位序列及其二元序列的线性复杂度问题

The Euler quotient modulo an odd-prime power p^r (r > 1) can be uniquely decomposed as a p-adic number of the form \(\frac{{u^{(p - 1)p^{r - 1} } - 1}}{{p^r }} \equiv a_0 (u) + a_1 (u)p + \cdots + a_{r - 1} (u)p^{r - 1} (\bmod p^r ), \gcd (u,p) = 1,\) where 0 ? a_j (u) < p for 0 ? j ? r?1 and we set all a_j (u) = 0 if gcd(u, p) > 1. We firstly study certain arithmetic properties of the level sequences (a_j (u))_u?0 over \(\mathbb{F}_p \) via introducing a new quotient. Then we determine the exact values of linear complexity of (a_j (u))_u?0 and values of k-error linear complexity for binary sequences defined by (a_j (u))_u?0.     

Upper Bounds on Number of Steals in Rooted Trees

Inspired by applications in parallel computing, we analyze the setting of work stealing in multithreaded computations. We obtain tight upper bounds on the number of steals when the computation can be modeled by rooted trees. In particular, we show that if the computation with n processors starts with one processor having a complete k-ary tree of height h (and the remaining n ? 1 processors having nothing), the maximum possible number of steals is \({\sum }_{i=1}^{n}(k-1)^{i}\binom {h}{i}\).     

Quantum algorithm to solve function inversion with time–space trade-off

In general, it is a difficult problem to solve the inverse of any function. With the inverse implication operation, we present a quantum algorithm for solving the inversion of function via using time–space trade-off in this paper. The details are as follows. Let function \(f(x)=y\) have k solutions, where \(x\in \{0, 1\}^{n}, y\in \{0, 1\}^{m}\) for any integers n, m. We show that an iterative algorithm can be used to solve the inverse of function f(x) with successful probability \(1-\left( 1-\frac{k}{2^{n}}\right) ^{L}\) for \(L\in Z^{+}\). The space complexity of proposed quantum iterative algorithm is O(Ln), where L is the number of iterations. The paper concludes that, via using time–space trade-off strategy, we improve the successful probability of algorithm.     

The Outer-connected Domination Number of Sierpiński-like Graphs

An outer-connected dominating set in a graph G = (V, E) is a set of vertices D ? V satisfying the condition that, for each vertex v ? D, vertex v is adjacent to some vertex in D and the subgraph induced by V?D is connected. The outer-connected dominating set problem is to find an outer-connected dominating set with the minimum number of vertices which is denoted by \(\tilde {\gamma }_{c}(G)\). In this paper, we determine \(\tilde {\gamma }_{c}(S(n,k))\), \(\tilde {\gamma }_{c}(S^{+}(n,k))\), \(\tilde {\gamma }_{c}(S^{++}(n,k))\), and \(\tilde {\gamma }_{c}(S_{n})\), where S(n, k), S ⁺(n, k), S ⁺⁺(n, k), and S _n are Sierpi\(\acute {\mathrm {n}}\)ski-like graphs.     

Approximating the Metric TSP in Linear Time

Given a metric graph G=(V,E) of n vertices, i.e., a complete graph with a non-negative real edge cost function satisfying the triangle inequality, the metricity degree of G is defined as \(\beta=\max_{x,y,z\in V}\{\frac{c(x,y)}{c(x,z)+c(y,z)}\}\in[\frac{1}{2},1]\). This value is instrumental to establish the approximability of several NP-hard optimization problems definable on G, like for instance the prominent traveling salesman problem, which asks for finding a Hamiltonian cycle of G of minimum total cost. In fact, this problem can be approximated quite accurately depending on the metricity degree of G, namely by a ratio of either \(\frac{2-\beta}{3(1-\beta)}\) or \(\frac{3\beta^{2}}{3\beta^{2}-2\beta+1}\), for \(\beta<\frac{2}{3}\) or \(\beta\geq \frac{2}{3}\), respectively. Nevertheless, these approximation algorithms have O(n ³) and O(n ^2.5log?^1.5 n) running time, respectively, and therefore they are superlinear in the Θ(n ²) input size. Thus, since many real-world problems are modeled by graphs of huge size, their use might turn out to be unfeasible in practice, and alternative approaches requiring only O(n ²) time are sought. However, with this restriction, all the currently available approaches can only guarantee a 2-approximation ratio for the case β=1, which means a \(\frac{2\beta^{2}}{2\beta^{2}-2\beta+1}\)-approximation ratio for general β<1. In this paper, we show how to elaborate—without affecting the space and time complexity—one of these approaches, namely the classic double-MST heuristic, in order to obtain a 2β-approximate solution. This improvement is effective, since we show that the double-MST heuristic has in general a performance ratio strictly larger than 2β, and we further show that any alternative elaboration of it cannot lead to a performance ratio better than 2β?ε, for any ε>0. Our theoretical results are complemented with an extensive series of experiments, that show the practical appeal of our approach.     

Entanglement witness criteria of strong-<Emphasis Type="Italic">k</Emphasis>-separability for multipartite quantum states

Let \(H_{1}, H_{2},\ldots ,H_{n}\) be separable complex Hilbert spaces with \(\dim H_{i}\ge 2\) and \(n\ge 2\). Assume that \(\rho \) is a state in \(H=H_1\otimes H_2\otimes \cdots \otimes H_n\). \(\rho \) is called strong-k-separable \((2\le k\le n)\) if \(\rho \) is separable for any k-partite division of H. In this paper, an entanglement witnesses criterion of strong-k-separability is obtained, which says that \(\rho \) is not strong-k-separable if and only if there exist a k-division space \(H_{m_{1}}\otimes \cdots \otimes H_{m_{k}}\) of H, a finite-rank linear elementary operator positive on product states \(\Lambda :\mathcal {B}(H_{m_{2}}\otimes \cdots \otimes H_{m_{k}})\rightarrow \mathcal {B}(H_{m_{1}})\) and a state \(\rho _{0}\in \mathcal {S}(H_{m_{1}}\otimes H_{m_{1}})\), such that \(\mathrm {Tr}(W\rho )<0\), where \(W=(\mathrm{Id}\otimes \Lambda ^{\dagger })\rho _{0}\) is an entanglement witness. In addition, several different methods of constructing entanglement witnesses for multipartite states are also given.     

A linear-time algorithm for finding Hamiltonian (<Emphasis Type="Italic">s</Emphasis>, <Emphasis Type="Italic">t</Emphasis>)-paths in odd-sized rectangular grid graphs with a rectangular hole

A grid graph \(G_{\mathrm{g}}\) is a finite vertex-induced subgraph of the two-dimensional integer grid \(G^\infty \). A rectangular grid graph R(m, n) is a grid graph with horizontal size m and vertical size n. A rectangular grid graph with a rectangular hole is a rectangular grid graph R(m, n) such that a rectangular grid subgraph R(k, l) is removed from it. The Hamiltonian path problem for general grid graphs is NP-complete. In this paper, we give necessary conditions for the existence of a Hamiltonian path between two given vertices in an odd-sized rectangular grid graph with a rectangular hole. In addition, we show that how such paths can be computed in linear time.     

On Two Continuum Armed Bandit Problems in High Dimensions

We consider the problem of continuum armed bandits where the arms are indexed by a compact subset of \(\mathbb {R}^{d}\). For large d, it is well known that mere smoothness assumptions on the reward functions lead to regret bounds that suffer from the curse of dimensionality. A typical way to tackle this in the literature has been to make further assumptions on the structure of reward functions. In this work we assume the reward functions to be intrinsically of low dimension k ? d and consider two models: (i) The reward functions depend on only an unknown subset of k coordinate variables and, (ii) a generalization of (i) where the reward functions depend on an unknown k dimensional subspace of \(\mathbb {R}^{d}\). By placing suitable assumptions on the smoothness of the rewards we derive randomized algorithms for both problems that achieve nearly optimal regret bounds in terms of the number of rounds n.     

Tracking frequent items over distributed probabilistic data

Tracking frequent items (also called heavy hitters) is one of the most fundamental queries in real-time data due to its wide applications, such as logistics monitoring, association rule based analysis, etc. Recently, with the growing popularity of Internet of Things (IoT) and pervasive computing, a large amount of real-time data is usually collected from multiple sources in a distributed environment. Unfortunately, data collected from each source is often uncertain due to various factors: imprecise reading, data integration from multiple sources (or versions), transmission errors, etc. In addition, due to network delay and limited by the economic budget associated with large-scale data communication over a distributed network, an essential problem is to track the global frequent items from all distributed uncertain data sites with the minimum communication cost. In this paper, we focus on the problem of tracking distributed probabilistic frequent items (TDPF). Specifically, given k distributed sites S = {S ₁, … , S _k }, each of which is associated with an uncertain database \(\mathcal {D}_{i}\) of size n _i , a centralized server (or called a coordinator) H, a minimum support ratio r, and a probabilistic threshold t, we are required to find a set of items with minimum communication cost, each item X of which satisfies P r(s u p(X) ≥ r × N) > t, where s u p(X) is a random variable to describe the support of X and \(N={\sum }_{i=1}^{k}n_{i}\). In order to reduce the communication cost, we propose a local threshold-based deterministic algorithm and a sketch-based sampling approximate algorithm, respectively. The effectiveness and efficiency of the proposed algorithms are verified with extensive experiments on both real and synthetic uncertain datasets.     

Global Stability of a Discrete Population Dynamics Model with Two Delays

A population dynamics model \(x_n = \frac{{\alpha x_{n - m} }}{{1 + x_{n - m} + \beta x_{n - k} }}\) with two delays k and m and coefficients α > 1 and β ≥ 0 is studied. A sufficient condition, which is also necessary for certain delays, for the global asymptotic stability of the stationary solution \(x_n = \frac{{\alpha - 1}}{{\beta + 1}}\) is formulated.     

Faster Parameterized Algorithms for <Emphasis Type="SmallCaps">Minimum Fill-in</Emphasis>

We present two parameterized algorithms for the Minimum Fill-in problem, also known as Chordal Completion: given an arbitrary graph G and integer k, can we add at most k edges to G to obtain a chordal graph? Our first algorithm has running time \(\mathcal {O}(k^{2}nm+3.0793^{k})\), and requires polynomial space. This improves the base of the exponential part of the best known parameterized algorithm time for this problem so far. We are able to improve this running time even further, at the cost of more space. Our second algorithm has running time \(\mathcal {O}(k^{2}nm+2.35965^{k})\) and requires \(\mathcal {O}^{\ast}(1.7549^{k})\) space. To achieve these results, we present a new lemma describing the edges that can safely be added to achieve a chordal completion with the minimum number of edges, regardless of k.