Volume 187, Issue 1


1. Gathering over Meeting Nodes in Infinite Grid

Subhash Bhagat ; Abhinav Chakraborty ; Bibhuti Das ; Krishnendu Mukhopadhyaya.
The gathering over meeting nodes problem asks the robots to gather at one ofthe pre-defined meeting nodes. The robots are deployed on the nodes of ananonymous two-dimensional infinite grid which has a subset of nodes marked asmeeting nodes. Robots are identical, autonomous, anonymous and oblivious. Theyoperate under an asynchronous scheduler. They do not have any agreement on aglobal coordinate system. All the initial configurations for which the problemis deterministically unsolvable have been characterized. A deterministicdistributed algorithm has been proposed to solve the problem for the remainingconfigurations. The efficiency of the proposed algorithm is studied in terms ofthe number of moves required for gathering. A lower bound concerning the totalnumber of moves required to solve the gathering problem has been derived.

2. Number Conservation via Particle Flow in One-dimensional Cellular Automata

Markus Redeker.
A number-conserving cellular automaton is a simplified model for a system ofinteracting particles. This paper contains two related constructions by whichone can find all one-dimensional number-conserving cellular automata with onekind of particle. The output of both methods is a "flow function", which describes the movementof the particles. In the first method, one puts increasingly strongerrestrictions on the particle flow until a single flow function is specified.There are no dead ends, every choice of restriction steps ends with a flow. The second method uses the fact that the flow functions can be ordered andthen form a lattice. This method consists of a recipe for the slowest flow thatenforces a given minimal particle speed in one given neighbourhood. All otherflow functions are then maxima of sets of these flows. Other questions, like that about the nature of non-deterministicnumber-conserving rules, are treated briefly at the end.

3. A note of generalization of fractional ID-factor-critical graphs

Sizhong Zhou.
In communication networks, the binding numbers of graphs (or networks) areoften used to measure the vulnerability and robustness of graphs (or networks).Furthermore, the fractional factors of graphs and the fractionalID-$[a,b]$-factor-critical covered graphs have a great deal of importantapplications in the data transmission networks. In this paper, we investigatethe relationship between the binding numbers of graphs and the fractionalID-$[a,b]$-factor-critical covered graphs, and derive a binding numbercondition for a graph to be fractional ID-$[a,b]$-factor-critical covered,which is an extension of Zhou's previous result [S. Zhou, Binding numbers forfractional ID-$k$-factor-critical graphs, Acta Mathematica Sinica, EnglishSeries 30(1)(2014)181--186].