The deformed consensus protocol

This paper studies a generalization of the standard continuous-time consensus protocol, obtained by replacing the Laplacian matrix of the communication graph with the so-called deformed Laplacian  . The deformed Laplacian is a second-degree matrix polynomial in the real variable s$s$ which reduces to the standard Laplacian for s$s$ equal to unity. The stability properties of the ensuing deformed consensus protocol   are studied in terms of parameter s$s$ for some special families of undirected and directed graphs, and for arbitrary graph topologies by leveraging the spectral theory of quadratic eigenvalue problems. Examples and simulation results are provided to illustrate our theoretical findings.     

The cell probe complexity of succinct data structures

We consider time-space tradeoffs for static data structure problems in the cell probe model with word size 1 (the bit probe model). In this model, the goal is to represent n$n$-bit data with s=n+r$s=n+r$ bits such that queries (of a certain type) about the data can be answered by reading at most t$t$ bits of the representation. Ideally, we would like to keep both s$s$ and t$t$ small, but there are tradeoffs between the values of s$s$ and t$t$ that limit the possibilities of keeping both parameters small.     

Operations preserving regular languages

Given a strictly increasing sequence s   of non-negative integers, filtering a word _a0a1?_an$a_0{a}_1?a_n$ by s   consists in deleting the letters _ai$a_i$ such that i   is not in the set {_s0,_s1,…}$\{s_0,s_1,\dots \}$. By a natural generalization, denote by L[s]$L[s]$, where L is a language, the set of all words of L filtered by s. The filtering problem is to characterize the filters s such that, for every regular language L  , L[s]$L[s]$ is regular. In this paper, the filtering problem is solved, and a unified approach is provided to solve similar questions, including the removal problem considered by Seiferas and McNaughton. Our approach relies on a detailed study of various residual notions, notably residually ultimately periodic sequences and residually rational transductions.     

Chordless paths through three vertices

Consider the following problem, which we call “Chordless path through three vertices” or CP3V, for short: Given a simple undirected graph G=(V,E)$G=(V,E)$, a positive integer k, and three distinct vertices s, t  , and v∈V$v\in V$, is there a chordless path of length at most k from s   via v$v$ to t in G? In a chordless path, no two vertices are connected by an edge that is not in the path. Alternatively, one could say that the subgraph induced by the vertex set of the path in G is the path itself. The problem has arisen in the context of service deployment in communication networks. We resolve the parametric complexity of CP3V by proving it W[1]$W[1]$-complete with respect to its natural parameter k  . Our reduction extends to a number of related problems about chordless paths and cycles. In particular, deciding on the existence of a single directed chordless (s,t)$(s,t)$-path in a digraph is also W[1]$W[1]$-complete with respect to the length of the path.     

A methodology for coupling fragments of XPath with structural indexes for XML documents

We introduce a new methodology for coupling language-induced partitions and index  -induced partitions on XML documents that is aimed for the benefit of efficient evaluation of XPath queries. In particular, we identify XPath fragments which are ideally coupled with the newly introduced P(k)$P(k)$-partition which has its definition grounded in the well-known A(k)$A(k)$ structural index and its associated partition. We then utilize these couplings to investigate fundamental questions about the use of structural indexes in XPath query evaluation.     

Analysis of a last come first served queueing system with customer abandonment

Motivated by manufacturing and service applications, we consider a single class multi-server queueing system working under the LCFS discipline of service. After entering the queue, a customer will wait a random length of time for service to begin. If service has not begun by this time she will abandon and be lost. For the GI/GI/s+M$\mathit{GI}/\mathit{GI}/s+M$ queue, we present some structural results to describe the relation between various performance measures and the scheduling policies. We next consider the LCFS M/M/s+M$M/M/s+M$ queue and focus on deriving new results for the virtual waiting time and the sojourn time in the queue (either before service or before abandonment). We provide an exact analysis using Laplace–Stieltjes transforms. We also conduct some numerical analysis to illustrate the impact of customer impatience and the discipline of service on performance.     

A memetic algorithm for the job-shop with time-lags

The job-shop with time-lags (JS|t)$(\text{<italic>JS</italic>}|t)$ is defined as a job-shop problem with minimal and maximal delays between starting times of operations. In this article, time-lags between successive operations of the same job (JS|_ti,si)$(\text{<italic>JS</italic>}|t_{i,s_i})$ are studied. This problem is a generalization of the job-shop problem (null minimal time-lags and infinite maximal time-lags) and the no-wait job-shop problem (null minimal and maximal time-lags). This article introduced a framework based on a disjunctive graph to modelize the problem and on a memetic algorithm for job sequence generation on machines.     

Large independent sets in random regular graphs

We present algorithmic lower bounds on the size _sd$s_d$ of the largest independent sets of vertices in random d$d$-regular graphs, for each fixed d≥3$d\ge 3$. For instance, for d=3$d=3$ we prove that, for graphs on n$n$ vertices, _sd≥0.43475n$s_d\ge 0.43475n$ with probability approaching one as n$n$ tends to infinity.     

Paths and trails in edge-colored graphs

This paper deals with the existence and search for properly edge-colored paths/trails between two, not necessarily distinct, vertices s$s$ and t$t$ in an edge-colored graph from an algorithmic perspective. First we show that several versions of the s−t$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$s$ and t$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$k$ pairwise vertex/edge disjoint properly edge-colored s−t$s-t$ paths/trails in a c$c$-edge-colored graph G^c$G^c$ is NP-complete even for k=2$k=2$ and c=Ω(n²)$c=\Omega \left(n^2\right)$, where n$n$ denotes the number of vertices in G^c$G^c$. Moreover, we prove that these problems remain NP-complete for c$c$-edge-colored graphs containing no properly edge-colored cycles and c=Ω(n)$c=\Omega \left(n\right)$. We obtain some approximation results for those maximization problems together with polynomial results for some particular classes of edge-colored graphs.     

Divergence bounded computable real numbers

A real x$x$ is called h$h$-bounded computable  , for some function h:N→N$h:\mathbb{N}\to \mathbb{N}$, if there is a computable sequence (_xs)$(x_s)$ of rational numbers which converges to x$x$ such that, for any n∈N$n\in \mathbb{N}$, at most h(n)$h(n)$ non-overlapping pairs of its members are separated by a distance larger than 2^-n$2^{-n}$. In this paper we discuss properties of h$h$-bounded computable reals for various functions h$h$. We will show a simple sufficient condition for a class of functions h$h$ such that the corresponding h$h$-bounded computable reals form an algebraic field. A hierarchy theorem for h$h$-bounded computable reals is also shown. Besides we compare semi-computability and weak computability with the h$h$-bounded computability for special functions h$h$.     

Collision dynamics of elliptically polarized solitons in Coupled Nonlinear Schrödinger Equations

We investigate numerically the collision dynamics of elliptically polarized solitons of the System of Coupled Nonlinear Schrödinger Equations (SCNLSE) for various different initial polarizations and phases. General initial elliptic polarizations (not sech$sech$-shape) include as particular cases the circular and linear polarizations. The elliptically polarized solitons are computed by a separate numerical algorithm. We find that, depending on the initial phases of the solitons, the polarizations of the system of solitons after the collision change, even for trivial cross-modulation. This sets the limits of practical validity of the celebrated Manakov solution. For general nontrivial cross-modulation, a jump in the polarization angles of the solitons takes place after the collision (‘polarization shock’). We study in detail the effect of the initial phases of the solitons and uncover different scenarios of the quasi-particle behavior of the solution. In majority of cases the solitons survive the interaction preserving approximately their phase speeds and the main effect is the change of polarization. However, in some intervals for the initial phase difference, the interaction is ostensibly inelastic: either one of the solitons virtually disappears, or additional solitons are born after the interaction. This outlines the role of the phase, which has not been extensively investigated in the literature until now.     

MinT—Architecture and applications of the (t, m, s)-net and OOA database

Many different constructions for (t,m,s)$(t\text{,}m\text{,}s)$-nets and (t,s)$(t\text{,}s)$-sequences are known today. Propagation rules as well as connections to other mathematical objects make it difficult to determine the best net available in a given setting.