International Journal of Foundations of Computer Science

We consider the experimenter (e.g. the experimental physicist) as a Turing machine — the digital component — and the experiment of measurement — the analog component — as an oracle to the Turing machine. The algorithm running in the machine abstracts the experimental method of measurement (encoding the recursive structure of experimental actions) chosen by the experimenter. In this paper we prove that the central analogue-digital complexity classes $P$, $P/poly$ and $P/poly\cap REC$ can be characterized in terms of protocols to perform measurements controlled by standard Turing machines.

Directional Wireless Sensor Networks (DWSNs) have been a very active research topic as they have a wide range of applications in both military and civilian areas. In this paper, we study the Antenna Orientation (AO) and Antenna Orientation and Power Assignment (AOPA) problems, two important issues in DWSNs. In the AO problem, given a set $V$ of sensors equipped with directional antennas with beam-width $𝜃=\pi /3$, the objective is to determine an orientation of the antennas and a minimum transmission range $r=O(1)$ such that the induced symmetric communication graph is connected. We prove that the AO problem is NP-hard. We then extend our proof technique and show that the AOPA problem for DWSNs equipped with $\pi /3$ directional antennas is also NP-hard where we have to determine an orientation of the antennas as well as a power assignment $r$ to the nodes such that the resulting symmetric communication graph is connected, and (2) ${\mathrm{\Sigma }}_{u\in S}r{(u)}^{\beta }$ is minimized ($\beta$ is the distance-power gradient, $2\le \beta \le 6$). We propose an $O(n^2)$ heuristic algorithm and demonstrate by simulation that our method is better than the Ice-cream method.

In this paper, we introduce a new variant of domination called the outer-paired domination. For a graph $G=(V,E)$, an outer-paired dominating set $D\subseteq V$ is a dominating set of $G$ such that the induced subgraph of $V\setminus D$ contains a perfect matching. The outer-paired domination number of a graph $G$ is the cardinality of a minimum outer-paired dominating set of $G$. We show that finding the outer-paired domination number of a graph $G$ is NP-hard on bipartite graphs, chordal graphs, and planar graphs. We also propose a linear-time algorithm for solving the outer-paired domination problem on trees.

Given a simple undirected graph $G$, an orientation of $G$ is to assign every edge of $G$ a direction. Borradaile et al gave a greedy algorithm SC-Path-Reversal (in polynomial time) which finds a strongly connected orientation that minimizes the maximum indegree, and conjectured that SC-Path-Reversal is indeed optimal for the ”minimizing the lexicographic order” objective as well. In this note, we give a positive answer to the conjecture, which is that we show that the algorithm SC-PATH-REVERSAL finds a strongly connected orientation that minimizes the lexicographic order of indegrees.

The 2-dimensional torus networks, denoted by $T(m,n)$, is a special case of the famous $n$-dimensional torus network. The extra connectivity, structure connectivity and sub-structure connectivity are generalized connectivity to measure the fault-tolerance of the networks. In this paper, we show the 1-extra connectivity of $T(m,n)$ for $m\ge 3$ and $n\ge 4$ and 2-extra connectivity of $T(3,n)$ for $n\ge 4$. We also determine the $H$-structure connectivity and $H$-substructure connectivity of 2-dimensional torus network $T(m,n)$ ($m\ge 3$ and $n\ge 4$) when the structure subgraph $H\in \{K_{1,r},P_k\}$, where $2\le r\le 4$ and $4\le k\le 8$. These results are sharp since the connectivity of $T(m,n)$ ($m\ge 3,n\ge 3$) is 4.