Optimal number of annuli for maximizing the lifetime of sensor networks

The most effective way to maximize the lifetime of a wireless sensor network (WSN) is to allocate initial energy to sensors such that they exhaust their energy at the same time. The lifetime of a WSN as well as an optimal initial energy allocation are determined by a network design. The main contribution of the paper is to show that the lifetime of a WSN can be maximized by an optimal network design. We represent the network lifetime as a function of the number m$m$ of annuli and show that m$m$ has significant impact on network lifetime. We prove that if the energy consumed by data transmission is proportional to d^α+c$d^{\alpha }+c$, where d$d$ is the distance of data transmission and α$\alpha$ and c$c$ are some constants, then for a circular area of interest with radius R$R$, the optimal number of annuli that maximizes the network lifetime is m=R((α−1)/c)^1/α$m=R{((\alpha -1)/c)}^{1/\alpha }$ for an arbitrary sensor density function.     

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.     

Alternative proof of the Lyndon–Schützenberger Theorem

Some observations on products of primitive words are discussed. By these results, alternative proof is given for the Lyndon–Schützenberger Theorem, which says that every solution of the equation a^mbⁿ=c^k$a^m{b}^n=c^k$ over Σ^*${\Sigma }^{*}$ is trivial.     

Atomic routing games on maximum congestion

We study atomic routing games on networks in which players choose a path with the objective of minimizing the maximum congestion along the edges of their path. The social cost is the global maximum congestion over all edges in the network. We show that the price of stability is 1. The price of anarchy  , PoA$PoA$, is determined by topological properties of the network. In particular, PoA=O(?+logn)$PoA=O(?+logn)$, where ?$?$ is the length of the longest path in the player strategy sets, and n$n$ is the size of the network. Further, κ−1≤PoA≤c(κ²+log²n)$\kappa -1\le PoA\le c({\kappa }^2+{log}^{2}n)$, where κ$\kappa$ is the length of the longest cycle in the network, and c$c$ is a constant.     

Algorithms for near solutions to polynomial equations

Let F(x,y)$F(x,y)$ be a polynomial over a field K$K$ and m$m$ a nonnegative integer. We call a polynomial g$g$ over K$K$ an m$m$-near solution of F(x,y)$F(x,y)$ if there exists a c∈K$c\in K$ such that F(x,g)=cx^m$F(x,g)=c{x}^m$, and the number c$c$ is called an m$m$-value of F(x,y)$F(x,y)$ corresponding to g$g$. In particular, c$c$ can be 0. Hence, by viewing F(x,y)=0$F(x,y)=0$ as a polynomial equation over K[x]$K\left[x\right]$ with variable y$y$, every solution of the equation F(x,y)=0$F(x,y)=0$ in K[x]$K\left[x\right]$ is also an m$m$-near solution. We provide an algorithm that gives all m$m$-near solutions of a given polynomial F(x,y)$F(x,y)$ over K$K$, and this algorithm is polynomial time reducible to solving one variable equations over K$K$. We introduce approximate solutions to analyze the algorithm. We also give some interesting properties of approximate solutions.     

State-complexity hierarchies of uniform languages of alphabet-size length

We study the state complexity of certain simple languages. If A$A$ is an alphabet of k$k$ letters, then a k$k$-language   is a nonempty set of words of length k$k$, that is, a uniform language of length k$k$. We show that the minimal state complexity of a k$k$-language is k+2$k+2$, and the maximal, (k^k−1−1)/(k−1)+2^k+1$(k^{k-1}-1)/(k-1)+2^k+1$. We prove constructively that, for every i$i$ between the minimal and maximal bounds, there is a language of state complexity i$i$. We introduce a class of automata accepting sets of words that are permutations of A$A$; these languages define a complete hierarchy of complexities between k²−k+3$k^2-k+3$ and 2^k+1$2^k+1$. The languages of another class of automata, based on k$k$-ary trees, define a complete hierarchy of complexities between 2^k+1$2^k+1$ and (k^k−1−1)/(k−1)+2^k+1$(k^{k-1}-1)/(k-1)+2^k+1$. This provides new examples of uniform languages of maximal complexity.     

Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor

We consider a two-edge connected, undirected graph G=(V,E)$G=(V,E)$, with n$n$ nodes and m$m$ non-negatively real weighted edges, and a single source shortest paths tree (SPT) T$T$ of G$G$ rooted at an arbitrary node r$r$. If an edge in T$T$ is temporarily removed, it makes sense to reconnect the nodes disconnected from the root by adding a single non-tree edge, called a swap edge  , instead of rebuilding a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select a best possible swap edge. In this paper we focus on the most prominent one, that is the minimization of the average distance between the root and the disconnected nodes. To this respect, we present an O(mlog²n)$O\left(m{log}^{2}n\right)$ time and O(m)$O\left(m\right)$ space algorithm to find a best swap edge for every edge of T$T$, thus improving for m=o(n²/log²n)$m=o(n^2/{log}^{2}n)$ the previously known O(n²)$O\left(n^2\right)$ time and space complexity algorithm.     

Conjunctive query evaluation by search-tree revisited

The most natural and perhaps most frequently used method for testing membership of an individual tuple in a conjunctive query is based on searching trees of partial solutions, or search-trees. We investigate the question of evaluating conjunctive queries with a time-bound guarantee that is measured as a function of the size of the optimal search-tree. We provide an algorithm that, given a database D$D$, a conjunctive query Q$Q$, and a tuple a$a$, tests whether Q(a)$Q\left(a\right)$ holds in D$D$ in time bounded by a polynomial in (sn)^logk(sn)^loglogn${\left(sn\right)}^{logk}{\left(sn\right)}^{loglogn}$ and n^r$n^r$, where n$n$ is the size of the domain of the database, k$k$ is the number of bound variables of the conjunctive query, s$s$ is the size of the optimal search-tree, and r$r$ is the maximum arity of the relations. In many cases of interest, this bound is significantly smaller than the n^O(k)$n^{O\left(k\right)}$ bound provided by the naive search-tree method. Moreover, our algorithm has the advantage of guaranteeing the bound for any given conjunctive query. In particular, it guarantees the bound for queries that admit an equivalent form that is much easier to evaluate, even when finding such a form is an NP-hard task. Concrete examples include the conjunctive queries that can be non-trivially folded into a conjunctive query of bounded size or bounded treewidth. All our results translate to the context of constraint-satisfaction problems via the well-publicized correspondence between both frameworks.