International Journal of Foundations of Computer Science

A mobile agent starting at an arbitrary node of an m × k grid, for 1 < m ≤ k, has to explore the grid by visiting all its nodes and traversing all edges. The cost of an exploration algorithm is the number of edge traversals by the agent. Nodes of the grid are unlabeled and ports at each node v have distinct numbers in {0,…, d − 1}, where d = 2, 3, 4 is the degree of v. Port numbering is local, i.e., there is no relation between port numbers at different nodes. When visiting a node the agent sees its degree. It also sees the port number by which it enters a node and can choose the port number by which it leaves a visited node. We are interested in deterministic exploration algorithms working at low cost.

We consider the scenario in which the agent is equipped with a stationary token situated at its starting node. The agent sees the token whenever it visits this node. We give an exploration algorithm working at cost O(k²) for 2 × k grids, and at cost O(m²k), for m × k grids, when 2 < m ≤ k.

Generalized cubes are a subclass of hypercube-like networks that are employed by a number of parallel algorithms. Linear array is common topology of multicomputer system. So congestion is very useful to improve algorithm performance for implementing generalized cube communication pattern on linear array. This paper addresses the congestion of generalized cube communication patterns embedding into linear array topology. For this purpose, the maximum m-induced subgraph of generalized cube is determined firstly, which is very important for discussing the congestion. Then an embedding scheme is described, and the congestion is shown to attain the minimum, which guarantees the optimality of the proposed scheme.

In this paper we extend the framework of reaction systems by introducing (extended) zoom structures which formalize a depository of knowledge of a discipline of science. The integrating structure of such a depository (which is a well-founded partial order) allows one to deal with the hierarchical nature of biology. This leads to the notion of an exploration system which consists of (1) a static part which is a depository of knowledge given by an extended zoom structure , and (2) a dynamic part given by a family of reaction systems . In this setup the depository of knowledge is explored by computations/processes provided by reaction systems from , where this exploration can use/integrate knowledge present on different levels (e.g., atomic, cellular, organism, species, … levels).

In this paper, we investigate the problem of computing structural sensitive variations of an unordered tree edit distance. First, we focus on the variations tractable by the algorithms including the submodule of a network algorithm, either the minimum cost maximum flow algorithm or the maximum weighted bipartite matching algorithm. Then, we show that both network algorithms are replaceable, and hence the time complexity of computing these variations can be reduced to O(nmd) time, where n is the number of nodes in a tree, m is the number of nodes in another tree and d is the minimum degree of given two trees. Next, we show that the problem of computing the bottom-up distance is MAX SNP-hard. Note that the well-known linear-time algorithm for the bottom-up distance designed by Valiente (2001) computes just a bottom-up indel (insertion-deletion) distance allowing no substitutions.

Our work is to study the Minimum Latency Broadcast Scheduling problem in the geometric SINR model with power control. With power control, sensor nodes have the ability to adjust transmitting power. While existing works studied the problem assuming a uniform power assignment or allowing unlimited power levels, we investigate the problem with a more realistic power assignment model where the maximum power level is bounded. To the best of our knowledge, no existing work formally proved the NP-hardness, though many researchers have been assuming that this fact holds true. In this paper, we provide a solid proof for this result.

The Global Avalanche Characteristics (including the sum-of-squares indicator and the absolute indicator) measure the overall avalanche characteristics of a cryptographic Boolean function. Son et al. (1998) gave the lower bound on the sum-of-squares indicator for a balanced Boolean function. In this paper, we give a sufficient and necessary condition on a balanced Boolean function reaching the lower bound on the sum-of-squares indicator. We also analyze whether these balanced Boolean functions exist, and if they reach the lower bounds on the sum-of-squares indicator or not. Our result implies that there does not exist a balanced Boolean function with n-variable for odd n(n ≥ 5). We conclude that there does not exist a m(m ≥ 1)-resilient function reaching the lower bound on the sum-of-squares indicator with n-variable for n ≥ 7.

We present algorithms that construct a sparse spanning subgraph of a three-edge-connected graph that preserves three-edge connectivity or of a three-vertex-connected graph that preserves three-vertex connectivity. Our algorithms are conceptually simple and run in O(|E|) time. These simple algorithms can be used to improve the efficiency of the best-known algorithms for three-edge and three-vertex connectivity and their related problems, by preprocessing the input graph so as to trim it down to a sparse graph. Afterwards, the original algorithms run in O(|V|) instead of O(|E|) time. Our algorithms generate an adjacency-lists structure to represent the sparse spanning subgraph, so that when a depth-first search is performed over the subgraph based on this adjacency-lists structure it actually traverses the paths in an ear-decomposition of the subgraph. This is useful because many of the existing algorithms for three-edge- or three-vertex connectivity and their related problems are based on an ear-decomposition of the given graph. Using such an adjacency-lists structure to represent the input graph would greatly improve the run-time efficiency of these algorithms.