Search

In this paper, we study the problem of gossiping with interference constraint in radio ring networks. Gossiping (or total exchange information) is a protocol where each node in the network has a message and is expected to distribute its own message to every other node in the network. The gossiping problem consists in finding the minimum running time (makespan) of a gossiping protocol and algorithms that attain this makespan. We focus on the case where the transmission network is a ring network. We consider synchronous protocols where it takes one unit of time (step) to transmit a unit-length message. During one step, a node receives at most one message only through one of its two neighbors. We also suppose that, during one step, a node cannot be both a sender and a receiver (half duplex model). Moreover communication is subject to interference constraints. We use a primary node interference model where, if a node receives a message from one of its neighbors, its other neighbor cannot send at the same time. With these assumptions we completely solve the problem for ring networks. We first show lower bounds and then give gossiping algorithms which meet these lower bounds and so are optimal. The number of rounds depends on the congruences of n modulo 12. [ABSTRACT FROM AUTHOR]

Mixed graphs have both directed and undirected edges. We consider mixed graphs that are regular in both directed and undirected degree and with given girth. Araujo-Pardo, Hern'andez-Cruz, andMontellano-Ballesteros recently established a lower bound for regular mixed graphs with directed degree one that generalizes the Moore bound. In this paper we show that, in at least one non-trivial case, their bound can be achieved. For a few other specific values of direct degree, undirected degree and girth we are able to identify graphs (mixed cages) of minimum possible order. We also obtain some fairly tight bounds for a few other cases. [ABSTRACT FROM AUTHOR]

We generalize the familiar notion of periodicity in sequences to a new kind of pseudoperiodicity, and we prove some basic results about it. We revisit the results of a 2012 paper of Shevelev and reprove his results in a simpler and more unified manner, and provide a complete answer to one of his previously unresolved questions. We consider finding words with specific pseudoperiod and having the smallest possible critical exponent. Finally, we consider the problem of determining whether a finite word is pseudoperiodic of a given size, and show that it is NP-complete. [ABSTRACT FROM AUTHOR]

The (bitwise) complement x of a binary word x is obtained by changing each 0 in x to 1 and vice versa. An antisquare is a nonempty word of the form x x. In this paper, we study infinite binary words that do not contain arbitrarily large antisquares. For example, we show that the repetition threshold for the language of infinite binary words containing exactly two distinct antisquares is (5 +√5)/2. We also study repetition thresholds for related classes, where "two" in the previous sentence is replaced by a larger number. We say a binary word is good if the only antisquares it contains are 01 and 10. We characterize the minimal antisquares, that is, those words that are antisquares but all proper factors are good. We determine the growth rate of the number of good words of length n and determine the repetition threshold between polynomial and exponential growth for the number of good words. [ABSTRACT FROM AUTHOR]