International Journal of Foundations of Computer Science

In this paper, we study the conjecture that $n$-variable ($n$ odd) rotation symmetric Boolean functions with degree $n-2$ have no non-zero linear structures. We show that if this class of RSBFs have non-zero linear structures, then the linear structures are invariant linear structures and the homogeneous component of degree $n-3$ in the function’s algebraic normal form has only two possibilities. Moreover, it is checked that the conjecture is true for $n=9,15,21$, and then a more explicit conjecture is proposed.

Robustness of the network topology is a key aspect in the design of computer networks. Vertex residual closeness is a new graph-theoretic concept defined as a measure of network robustness. In this model, edges are perfectly reliable and the vertices fail independently of each other. In this paper, vertex residual closeness of paths and regular caterpillars are calculated by giving an insight of how to evaluate the vertex residual closeness of path-like graphs.

Cloud storage greatly facilitates both individuals and organizations to share data over the Internet. However, there are several security issues that impede to outsource their data. Among various approaches introduced to overcome these issues, attribute-based encryption (ABE) provides secure and flexible access control on shared data, and thus is rather promising. But the original ABE is not adaptable to some special circumstances, where attributes are organized in a hierarchical structure, such as enterprises and official institutions. On the other hand, although the wide use of mobile devices enables users to conveniently access shared data anywhere and anytime, this also increases the risk of key exposure, which will result into unwanted exposure of the shared data. In this paper, we extend the functionality of the original ABE and enhance its security by providing key generation delegation and forward security. Consequently, the enhanced ABE meets applications of large organizations with hierarchies and minimizes the damage in the case of unexpected key exposures. Specifically speaking, we present a forward-secure ciphertext-policy hierarchical attribute-based encryption scheme in prime order bilinear groups, as a core building of attribute-based data sharing scheme. The security of the proposed scheme is proven in the standard model. We conduct experiments to demonstrate its efficiency and practicability.

We introduce and study a new Steiner tree problem variation called the bursty Steiner tree problem where new nodes arrive into bursts. This is an online problem which becomes the well-known online Steiner tree problem if the number of nodes in each burst is exactly one and becomes the classic Steiner tree problem if all the nodes appear in a single burst. In undirected graphs, we provide a tight bound of $\mathrm{\Theta }(\mathrm{\text{min}}\{logk,m\})$ on the competitive ratio for this problem, where $k$ is the total number of nodes to be connected and $m$ is the total number of different bursts. In directed graphs of bounded edge asymmetry $\alpha$, we provide a competitive ratio for this problem with a gap of ${𝒪}(\mathrm{\text{min}}\{\alpha ,m\})$ factor between the lower bound and the upper bound. We also show that a tight bound of $\mathrm{\Theta }(\mathrm{\text{min}}\{logk,m\})$ on the competitive ratio can be obtained for a bursty variation of the terminal Steiner tree problem. These are the first results that provide clear performance trade-offs for a novel Steiner tree problem variation that subsumes both of its online and classic versions.

Let $S=s_1{s}_2...s_n$ be a string, with symbols from an alphabet. $S$ is said to be degenerate if for some positions, say $i$, $s_i$ can contain a subset of symbols from the symbol alphabet, rather than just one symbol. Given a text string $T$ and a pattern $P$, both with symbols from an alphabet $\mathrm{\Sigma }$, the degenerate string matching problem, is to find positions in $T$ where $P$ occured, such that $T$, $P$, or both are allowed to be degenerate. Though some algorithms have been proposed, their huge computational cost pose a significant challenge to their practical utilization. In this work, we propose IDPM, an improved degenerate pattern matching algorithm based on an extension of the Boyer–Moore algorithm. At the preprocessing phase, the algorithm defines an alphabet-independent compatibility rule, and computes the shift arrays using respective variants of the bad character and good suffix heuristics. At the search phase, IDPM improves the matching speed by using the compatibility rule. On average, the proposed IDPM algorithm has a linear time complexity with respect to the text size, and to the overall size of the pattern. IDPM demonstrates significance performance improvement over state-of-the-art approaches. It can be used in fast practical degenerate pattern matching with large data sizes, with important applications in flexible and scalable searching of huge biological sequences.

The generalized hypercube is a highly-connective network proposed by Bhuyan and Agrawal. In this paper, we study the restricted connectivity and fault-free unicast algorithm in the generalized hypercube. Firstly, we prove that the restricted connectivity of a $r$-dimensional generalized hypercube $G(m_r,m_{r-1},\dots ,m_1)$ is $2\kappa (G)-n$, where $\kappa (G)$ denotes the connectivity of $G(m_r,m_{r-1},\dots ,m_1)$ and $n=$ max $\{m_1,m_2,\dots ,m_r\}$, under the condition that each vertex has at least one fault-free neighbor. It is almost twice the traditional connectivity of $G(m_r,m_{r-1},\dots ,m_1)$. Furthermore, we present an $O(\kappa {(G)}^3)$ fault-free unicast algorithm in the generalized hypercube.

The Resource Allocation Problem with Time Dependent Penalties (RAPTP) is a variant of uncapacitated resource allocation problems generally referred as uncapacitated facility allocation problems or uncapacitated facility location problem (UFLP). Work done in this paper is motivated by the work of Du, Lu and Xu [7] in which authors considered facility location problems with submodular penalties and presented a 3-approximation primal dual algorithm. This paper considers that each unallocated demand point adds to penalty that increases as time passes and is thus represented by function $x(t_i,p_i)$ where $t_i$ and $p_i$ are elapse time and priority of demand point $d_i$. As this problem has been considered for emergency service allocation, all demand points should be allocated to some facility or resource within some stipulated time limit beyond which it may lose its purpose. Thus penalty incurred by a demand point is considered till that threshold value only. Thus it is assumed that penalty contribution by a demand point remains constant after a specified threshold value. By exploiting the properties of time dependent penalties, a 4-approximation primal-dual algorithm is proposed which is based on LP framework, and is the first constant-factor approximation algorithm for RAPTP.