During the first year of the AlDyNet associated team between COATI and the Universidad Adolfo Ibáñez (Santiago, Chile), we have pursue ongoing research work on distributed computing through the coordination of mobile agents on graphs. We also have continued our work on particular graph decompositions (defined in a joint work in ICALP 2012), focussing on their algorithmic applications on planar graphs. Furthermore, we have started collaboration on new topics, namely the design of exact and heuristic algorithms for computing path-decompositions of graphs. We summarize below the main results we have obtained so far.
- Distributed computing through the coordination of mobile agents on graphs.
Consider a set of mobile robots with minimal capabilities placed over distinct nodes of a discrete anonymous ring (neither nodes nor edges are labeled). They operate on the basis of the so called Look-Compute-Move cycle. Asynchronously, each robot takes a snapshot of the ring, determining which nodes are either occupied by robots or empty. Based on the observed configuration, it decides whether to move to one of its adjacent nodes or to stay idle. In the first case, it performs the computed move, eventually. The computation also depends on the required task. We have proposed a unified approach to solve three important problems in the field: the exclusive perpetual exploration, the exclusive perpetual graph searching and the gathering problems. We investigate these tasks in the famous CORDA distributed computing model where the robots cannot communicate but can perceive the positions of other robots. Besides being a unified approach for the three different tasks, the given algorithms solve some open problems. Moreover, we provide some impossibility results for the perpetual graph searching problem. Then, we solved both the well-known Searching and Gathering tasks. In the literature, most contributions are restricted to a subset of initial configurations. Here, we design two different algorithms and provide a full characterization of the initial configurations that permit the resolution of the problems under minimal assumptions.
Our contributions have been validated by a joint publication in APDCM 2013 and has been followed by a publication in ICDCN 2014.
- Graph decompositions on planar graphs.
During the visit of Karol Suchan and Esteban Roman in France, we have mainly work on graph decompositions on planar graphs. We have investigated the application of the decomposition we defined in a joint paper published in ICALP 2012 for the computation of several properties in planar graphs. Unfortunately, we mainly got impossibility results (i.e., NP-hardness proofs). We will pursue our investigations during the visit of members of COATI in Santiago (November 2013) that will be partly dedicated to discovering new decompositions with better algorithmic power.
- Path-decomposition of graphs.
During this year, we have been actively working on the implementation of various algorithms for computing path-decompositions of graphs. Since this is a NP-hard problem, we have focussed on the design of an exact branch-and-bound algorithm and a set of heuristics. Our preliminary simulation results are very promising and have highlighted the need for better pre-processing rules (to reduce the size of the input graphs). The internship of Klaus Jaschan (from December 2013 till February 2014) will be on this topic.
- Graph searching games for the decompositions of directed graphs.
Graph searching games involve a team of searchers that aims at capturing a fugitive in a graph. These games have been widely studied for their relationships with tree- and path-decomposition of graphs. In order to define decompositions for directed graphs, similar games have been proposed in directed graphs. In this paper, we consider such a game that has been defined and studied in the context of routing reconfiguration problems in WDM networks. Namely, in the processing game, the fugitive is invisible, arbitrary fast, it moves in the opposite direction of the arcs of a digraph, but only as long as it has access to a strongly connected component free of searchers. We prove that the processing game is monotone which leads to its equivalence with a new digraph decomposition.
This work has been validated by a publication in LAGOS’13.
- Other outcome of the collaboration.
We have established new contacts with researchers from Universidad de Chile (Santiago). In particular, we plan to investigate new algorithms for computing the hyperbolicity of graphs with Mauricio Soto (postdoc in the Departamento de Ingeniería Matemática, Universidad de Chile).
- Gianlorenzo D’Angelo, Alfredo Navarra and Nicolas Nisse. Gathering and Exclusive Searching on Rings under Minimal Assumptions. In Proceedings of the 15th International Conference on Distributed Computing and Networking (ICDCN), LNCS, Springer, 2014, to appear.
- Gianlorenzo D’Angelo, Gabriele Di Stefano, Alfredo Navarra, Nicolas Nisse and Karol Suchan. A unified approach for different tasks on rings in robot-based computing systems. In Proceedings of the 15th Workshop on Advances in Parallel and Distributed Computational Models (APDCM), IEEE, 2013.
- Nicolas Nisse and Ronan Soares. On the monotonicity of Process Number. In Proceedings of 7th Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS), Elsevier, to appear in Electronic Note Discrete Maths, 2013.
- Ronan Pardo Soares, Pursuit-evasion, decompositions and convexity on graphs. Ph.D. thesis, Univ. Nice Sophia Antipolis, November 8th, 2013.
- AlDyNet Workshop on Algorithms and Randomness, UAI, Santiago, Chile — November 21, 2013.
- Chile to France
- France to Chile
- David Coudert: November 14th to November 30th, 2013.
- Nicolas Nisse: November 14th to November 30th, 2013.
- Bi Li: November 14th to December 12th, 2013.
- Fatima Moataz: November 14th to December 12th, 2013.
D. Coudert, B. Li, F-Z. Moataz and N. Nisse presented their work during the
AlDyNet Workshop on Algorithms and Randomness, UAI, Santiago, Chile — November 21, 2013.