International Journal of Foundations of Computer Science

Inspired by a recent work of Mesnager, we present several infinite families of quadratic ternary bent, near-bent and 2-plateaued functions from some known quadratic ternary bent functions. Meanwhile, the distributions of the Walsh spectrum of two classes of 2-plateaued functions obtained in this paper are completely determined.

3D cipher is a new block cipher proposed by Nakahara at CANS 2008, which operates on 512-bit blocks and 512-bit keys. It has an SPN structure like AES, and employs a 3-dimensional state to enlarge block size and key size. In this paper, we extend the meet-in-the-middle distinguisher to 6 rounds by employing the differential enumeration technique and rebound-like idea, and mount the attack on 11-round 3D with 2⁴⁹⁷ chosen plaintexts, 2^487.5 computations and 2³⁶¹ memories. By trading some memory for data and time, we can achieve the attack with 2⁴⁷⁹ chosen plaintexts, 2^479.5 computations and 2³⁷⁹ memories.

The binding number of a graph G is defined to be the minimum of $|N(S)|/\left|S\right|$ taken over all nonempty $S\subseteq V(G)$ such that $N(S)\ne V(G)$. Binding number, one indicator to better understand graph, is an important characteristic quantity of a graph. In this paper, the relationships between the binding number and some other graph vulnerability parameters, namely the toughness, integrity, rupture degree and scattering number, are established. Exact values for the binding numbers of wheel related graphs namely gear, helm, sunflower and friendship graph are obtained.

Interval routing is a space efficient method to realize a distributed routing function. In this paper we show that every circular-arc graph allows a shortest path strict 2-interval routing scheme, i.e., by introducing a global order on the vertices and assigning at most two (strict) intervals in this order to the ends of every edge allows to depict a routing function that implies exclusively shortest paths. Since circular-arc graphs do not allow shortest path 1-interval routing schemes in general, the result implies that the class of circular-arc graphs has strict compactness 2, which was a hitherto open question. Additionally, we show that the constructed 2-interval routing scheme is a 1-interval routing scheme with at most one additional interval assigned at each vertex and we outline an algorithm to calculate the routing scheme for circular-arc graphs in 𝒪(n²) time, where n is the number of vertices.

The (s+t+1)-dimensional exchanged crossed cube, denoted by ECQ(s, t), proposed by Li et al., combines the advantages of the hypercube and the crossed cube. It has been proven that ECQ(s, t) has better properties than the fundamental hypercube in the aspects of the fewer edges, lower cost factor and smaller diameter. This paper studies the embedding of cycles in ECQ(s, t). It is proved that ECQ(s, t) contains an l-cycle of every length l from 4 to 2^s+t+1 except that ECQ(2, 3) and ECQ(3, 3) do not contain a cycle of length 9 where $s\ge 2$ and $t\ge 3$. This result reveals the fact that ECQ(s, t) nearly remains the cycle embedding capability, while it only has about half edges of crossed cube.

Two mobile agents, starting at arbitrary, possibly different times from arbitrary nodes of an unknown network, have to meet at some node. Agents move in synchronous rounds: in each round an agent can either stay at the current node or move to one of its neighbors. Agents have different labels which are positive integers. Each agent knows its own label, but not the label of the other agent. In traditional formulations of the rendezvous problem, meeting is accomplished when the agents get to the same node in the same round. We want to achieve a more demanding goal, called rendezvous with detection: agents must become aware that the meeting is accomplished, simultaneously declare this and stop. This awareness depends on how an agent can communicate to the other agent its presence at a node. We use two variations of the arguably weakest model of communication, called the beeping model, introduced in [8]. In each round an agent can either listen or beep. In the local beeping model, an agent hears a beep in a round if it listens in this round and if the other agent is at the same node and beeps. In the global beeping model, an agent hears a loud beep in a round if it listens in this round and if the other agent is at the same node and beeps, and it hears a soft beep in a round if it listens in this round and if the other agent is at some other node and beeps.

We first present a deterministic algorithm of rendezvous with detection working, even for the local beeping model, in an arbitrary unknown network in time polynomial in the size of the network and in the length of the smaller label (i.e., in the logarithm of this label). However, in this algorithm, agents spend a lot of energy: the number of moves that an agent must make, is proportional to the time of rendezvous. It is thus natural to ask if bounded-energy agents, i.e., agents that can make at most c moves, for some integer c, can always achieve rendezvous with detection as well. This is impossible for some networks of unbounded size. Hence we rephrase the question: Can bounded-energy agents always achieve rendezvous with detection in bounded-size networks? We prove that the answer to this question is positive, even in the local beeping model but, perhaps surprisingly, this ability comes at a steep price of time: the meeting time of bounded-energy agents is exponentially larger than that of unrestricted agents. By contrast, we show an algorithm for rendezvous with detection in the global beeping model that works for bounded-energy agents (in bounded-size networks) as fast as for unrestricted agents.