International Journal of Foundations of Computer Science

In this paper, we show a polynomial-time algorithm for testing $c$-planarity of embedded flat clustered graphs with at most two vertices per cluster on each face.

Our result is based on a reduction to the planar set of spanning trees in topological multigraphs (pssttm) problem, which is defined as follows. Given a (non-planar) topological multigraph $A$ with $k$ connected components $A_1,\dots ,A_k$, do spanning trees of $A_1,\dots ,A_k$ exist such that no two edges in any two spanning trees cross? Kratochvíl et al. [SIAM Journal on Discrete Mathematics, 4(2): 223–244, 1991] proved that the problem is NP-hard even if $k=1$; on the other hand, Di Battista and Frati presented a linear-time algorithm to solve the pssttm problem for the case in which $A$ is a $1$-planar topological multigraph [Journal of Graph Algorithms and Applications, 13(3): 349–378, 2009].

For any embedded flat clustered graph $C$, an instance $A$ of the pssttm problem can be constructed in polynomial time such that $C$ is $c$-planar if and only if $A$ admits a solution. We show that, if $C$ has at most two vertices per cluster on each face, then it can be tested in polynomial time whether the corresponding instance $A$ of the pssttm problem is positive or negative. Our strategy for solving the pssttm problem on $A$ is to repeatedly perform a sequence of tests, which might let us conclude that $A$ is a negative instance, and simplifications, which might let us simplify $A$ by removing or contracting some edges. Most of these tests and simplifications are performed “locally”, by looking at the crossings involving a single edge or face of a connected component $A_i$ of $A$; however, some tests and simplifications have to consider certain global structures in $A$, which we call $\alpha$-donuts. If no test concludes that $A$ is a negative instance of the pssttm problem, then the simplifications eventually transform $A$ into an equivalent $1$-planar topological multigraph on which we can apply the cited linear-time algorithm by Di Battista and Frati.

Suppose that a circular fire spreads in the plane at unit speed. A single fire fighter can build a barrier at speed $v>1$. How large must $v$ be to ensure that the fire can be contained, and how should the fire fighter proceed? We contribute two results.

First, we analyze the natural curve ${\text{FF}}_v$ that develops when the fighter keeps building, at speed $v$, a barrier along the boundary of the expanding fire. We prove that the behavior of this spiralling curve is governed by a complex function ${(e^{wZ}-sZ)}^{-1}$, where $w$ and $s$ are real functions of $v$. For $v>v_c=2.6144\dots$ all zeroes are complex conjugate pairs. If $\varphi$ denotes the complex argument of the conjugate pair nearest to the origin then, by residue calculus, the fire fighter needs $\mathrm{\Theta }(1/\varphi )$ rounds before the fire is contained. As $v$ decreases towards $v_c$ these two zeroes merge into a real one, so that argument $\varphi$ goes to 0. Thus, curve ${\text{FF}}_v$ does not contain the fire if the fighter moves at speed $v=v_c$. (That speed $v>v_c$ is sufficient for containing the fire has been proposed before by Bressan et al. [6], who constructed a sequence of logarithmic spiral segments that stay strictly away from the fire.)

Second, we show that for any curve that visits the four coordinate half-axes in cyclic order, and in increasing distances from the origin the fire can not be contained if the speed $v$ is less than 1.618…, the golden ratio.

Super solution is a notion introduced to produce robust and stable solutions of combinatorial optimization and decision problems. We consider the $(1,0)$-super solutions of random instances of $k$-SAT, where a clause is satisfied if and only if there are at least two satisfied literals in this clause. By using an enhanced weighting scheme, we obtain better lower bounds that, if a random $k$-CNF formula $F_k(n,rn)$ is $(1,0)$-unsatisfiable with probability tending to 1 as $n\to \infty$, then $r_k\ge 1.88,4.31,8.83,17.11,32.5$ for $k=5,6,7,8,9$, respectively.

The idea of public key encryption with keyword search (PEKS), proposed by Boneh et al., enables one to send a trapdoor containing a encrypted keyword to query data without revealing the keyword. In Boneh et al.’s design, the trapdoor has to be transferred through a secure channel, which is both costly and inefficient. Baek et al. then proposed an efficient secure channel free public key encryption scheme with keyword search (SCF-PEKS). After that, vast amounts of research have focused on the protection against the off-line keyword guessing attack (OKGA) by enhancing the model. However, most of the PEKS/SCF-PEKS schemes developed so far are constructed by applying bilinear pairing and are susceptible to off-line keyword guessing attacks. In this paper, we propose a new SCF-PEKS scheme based on the ElGamal cryptosystem. The proposed scheme is not only secure against off-line keyword guessing attacks but also improves the efficiency.

Triple-cycle permutations over finite fields of characteristic two are studied, and some classes of triple-cycle permutations are proposed in this paper. In addition, new triple-cycle permutations can be constructed by switching construction from known ones.

We consider the problem of augmenting an $n$-vertex graph embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We present exact algorithms for the cases when (i) the input graph is a path, running in $O(n{log}^{3}n)$ time, and (ii) the input graph is a tree, running in $O(n^{2}logn)$ time. We also present an algorithm for paths that computes a $(1+𝜀)$-approximation in $O(n+1/{𝜀}^3)$ time.

In this paper, we investigate avenues for the exchange of information (explicit communication) among deaf and mute mobile robots scattered in the plane. We introduce the use of movement-signals (analogously to flight signals and bees waggle) as a mean to transfer messages, enabling the use of distributed algorithms among robots. We propose one-to-one deterministic movement protocols that implement explicit communication among semi-synchronous robots. We first show how the movements of robots can provide implicit acknowledgment in semi-synchronous systems. We use this result to design one-to-one communication among a pair of robots. Then, we propose two one-to-one communication protocols for any system of $n\ge 2$ robots. The former works for robots equipped with observable IDs that agree on a common direction (sense of direction). The latter enables one-to-one communication assuming robots devoid of any observable IDs or sense of direction. All protocols (for either two or any number of robots) assume that no robot remains inactive forever. However, they cannot avoid that the robots move either away or closer to each others, by the way requiring robots with an infinite visibility. In this paper, we also present how to overcome these two disadvantages (some activity of every robot and infinite visibility).

Our protocols enable the use of distributing algorithms based on message exchanges among swarms of stigmergic robots. They also allow robots to be equipped with the means of communication to tolerate faults in their communication devices.

We consider a lattice-based model in multiattribute decision making, where preferences are represented by global utility functions that evaluate alternatives in a lattice structure (which can account for situations of indifference as well as of incomparability). Essentially, this evaluation is obtained by first encoding each of the attributes (nominal, qualitative, numeric, etc.) of each alternative into a distributive lattice, and then aggregating such values by lattice functions. We formulate version spaces within this model (global preferences consistent with empirical data) as solutions of an interpolation problem and present their complete descriptions accordingly. Moreover, we consider the computational complexity of this interpolation problem, and show that up to 3 attributes it is solvable in polynomial time, whereas it is NP complete over more than 3 attributes. Our results are then illustrated with a concrete example.