AlDyNet
Algorithm for large and Dynamic Networks
Programme INRIA “Equipes Associées” 2013-2015, extended for three years 2016-2018
Team project INRIA : COATI | Foreign Partner: Universidad Adolfo Ibáñez, Santiago |
Centre de recherche INRIA Sophia Antipolis — Méditerranée
Thème INRIA : Com B |
Country: Chile |
French coordinator | Chilean coordinator | |
---|---|---|
Name, surname | Nicolas Nisse | Karol Suchan |
Title | Chargé de recherche Inria (Research officer) | Assistant professor |
Institution | team-project COATI, common team INRIA Sophia Antipolis – I3S (UMR 7271 of the CNRS and the University of Nice-Sophia Antipolis) |
Adolfo Ibáñez University Facultad de Ingeniería y Ciencias Santiago, Chile. |
Address |
Projet COATI, commun Inria, I3S(CNRS/UNSA)
INRIA Sophia-Antipolis 2004, route des Lucioles — B.P. 93 06902 Sophia-Antipolis Cedex France |
Universidad Adolfo Ibáñez
Av. Diagonal Las Torres 2640, Oficina 215-B Peñalolén 7941169, Santiago Chile |
URL | http://www-sop.inria.fr/members/Nicolas.Nisse/ | http://www.uai.cl/docentes/karol-suchan |
Phone | +33 4 97 15 53 28 | +56 2 331-1533 |
name dot surname arobase inria dot fr | name dot surname arobase uai dot cl |
Activity reports
- Final report on second phase (2016-2018) and Presentation
- Final report on first phase (2013-2015) and Presentation
Participants
- Inria: David Coudert, Guillaume Ducoffe (former Ph.D. student, defended December 2016), Frédéric Giroire, Fionn McInerney (Ph.D. student, since Oct. 2016), Fatima Zahra Moataz (former Ph.D. student, defended Oct. 2015), Nicolas Nisse, Stéphane Pérennes, Bi Li (former Ph.D. student, defended Nov. 2014), Ronan Pardo Soares (former Ph.D. student, defended Nov. 2013)
- Adolfo Ibáñez: Marcos Goycoolea, Eduardo Moreno, Esteban Roman (former Ph.D. student), Karol Suchan, José Merino (former student)
- Associated members at DIM, Univ. de Chile: Marcos Kiwi, Mauricio Soto (former member); CMM, Univ. de Chile: Juan-Carlos Maureira and UCF, Fortaleza, Brazil: Julio Araujo.
Documents
- Proposal (2013-2015) and Proposal (2016-2018)
- Joint Publications (2013-2018)
Visits in 2018
- Chile to France
- Karol Suchan: September 10th to 21th, 2018.
- France to Chile
- David Coudert: December 1st-15th, 2018.
- Nicolas Nisse: December 1st-15th, 2018.
Publications of the Project
International journals
-
Julio Araujo, Guillaume Ducoffe, Nicolas Nisse, and Karol Suchan. On interval number in cycle convexity.
Discrete Maths. and Theoretical Computer Science (DMTCS), Volume 20(1), 2018. -
David Coudert, Guillaume Ducoffe, Nicolas Nisse, and Mauricio Soto. Distance-preserving orderings in graphs.
Discrete Applied Maths., Volume 243, pages 140-153, 2018. -
Bi Li, Fatima Zahra Moataz, Nicolas Nisse and Karol Suchan, Minimum Size Tree-Decompositions.
Discrete Applied Maths, Volume 245, pages 109-127, 2018. -
Frédéric Giroire and Juan-Carlos Maureira. Analysis of the Failure Tolerance of Linear Access Networks.
IEEE Transactions on Intelligent Transportation Systems, Volume 19(4), pages 1166-1175 (2018) -
Sahel Sahhaf, Wouter Tavernier, Dimitri Papadimitriou, Davide Careglio, Alok Kumar, Christian Glacet, David Coudert, Nicolas Nisse, Lluis Fàbrega, Pere Vilà, Miguel Camelo, Pieter Audenaert, Didier Colle, Piet Demeester. Routing at Large Scale: Advances and Challenges for Complex Networks.
IEEE Network, Institute of Electrical and Electronics Engineers, 2017, pp.12 – 22. - Lélia Blin, Janna Burman and Nicolas Nisse. Exclusive Graph Searching. Algorithmica, Volume 77(3), pages 942-969, 2017.
- Euripides Markou, Nicolas Nisse and Stéphane Pérennes. Exclusive Graph Searching vs. Pathwidth. Information and Computation, Volume 252, pages 243-260, 2017
- Gianlorenzo D’Angelo, Alfredo Navarra and Nicolas Nisse. Gathering and Exclusive Searching on Rings under Minimal Assumptions. Distributed Computing, Volume 30(1), pages 17-48, 2017.
- Nathann Cohen, David Coudert, Guillaume Ducoffe, and Aurélien Lancin. Applying clique-decomposition for computing Gromov hyperbolicity. Theoretical Computer Science, Elsevier, 2017, 690, pp.114-139
- Nicolas Nisse, Ronan Pardo Soares: On the monotonicity of process number.
Discrete Applied Mathematics 210: 103-111 (2016) -
David Coudert, Dorian Mazauric, Nicolas Nisse: Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth.
ACM Journal of Experimental Algorithmics 21(1): 1.3:1-1.3:23 (2016) -
David Coudert, Guillaume Ducoffe, Nicolas Nisse: To Approximate Treewidth, Use Treelength!
SIAM J. Discrete Math. 30(3): 1424-1436 (2016) -
Gianlorenzo D’Angelo, Gabriele Di Stefano, Alfredo Navarra, Nicolas Nisse and Karol Suchan.
Computing on rings by oblivious robots: a unified approach for different tasks.
Algorithmica, Volume 72(4), pages 1055-1096, 2015. -
Florent Becker, Adrian Kosowski, Martin Matamala, Nicolas Nisse, Ivan Rapaport, Karol Suchan, and Ioan Todinca.
Allowing each node to communicate only once in a distributed system: shared whiteboard models.
Distributed Computing, Volume 28(3), pages 189-200, 2015. -
Adrian Kosowski, Bi Li, Nicolas Nisse and Karol Suchan. k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth.
Algorithmica, Volume 72(3), pages 758-777, 2015. -
Serge Gaspers, Mathieu Liedloff, Maya Stein and Karol Suchan. Complexity of Splits Reconstruction for Low-Degree Trees.
Discrete Applied Mathematics, Volume 180, pages 89-100 (2015) -
Julio Araujo, Nicolas Nisse and Stéphane Pérennes. Weighted Coloring in Trees.
SIAM J. Discrete Math. 28(4): 2029-2041 (2014) - David Coudert, Guillaume Ducoffe. On the recognition of \(C_4\)-free and \(1/2\)-hyperbolic graphs.
SIAM J. Discrete Math. 28(3): 1601-1617 (2014)
International conferences
- Julien Bensmail, Dorian Mazauric, Fionn McInerney, Nicolas Nisse, Stéphane Pérennes, Sequential Metric Dimension, 16th Workshop on Approximation and Online Algorithms (WAOA). 2018
- David Coudert, James Luedtke, Eduardo Moreno and Konstantinos Priftis. Computing and maximizing the exact reliability of wireless backhaul networks. In proceedings of International Network Optimization Conference (INOC), https://hal.inria.fr/hal-01394593, 2017.
- David Coudert and Guillaume Ducoffe. A simple approach for lower-bounding the distortion in any Hyperbolic embedding. European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB’17), Electronic Notes in Discrete Mathematics, 61, pp.293 – 299, 2017.
- Nathann Cohen, Fionn McInerney, Nicolas Nisse and Stéphane Pérennes. Study of a combinatorial game in graphs through Linear Programming. To appear in Proceedings of 28th International Symposium on Algorithms and Computation (ISAAC), 2017.
-
Guillaume Ducoffe, Sylvain Legay, Nicolas Nisse: On the Complexity of Computing Treebreadth.
In 27th International Workshop on Combinatorial Algorithms (IWOCA 2016): LNCS 9843, Springer, 3-15, 2016. -
Frédéric Giroire and Juan-Carlos Maureira. Analysis of the Failure Tolerance of Linear Access Networks.
IEEE Global Communications Conference (GLOBECOM), 2016 -
Mamadou M. Kante, Fatima Zahra Moataz, Benjamin Momège and Nicolas Nisse, Finding Paths in Grids with Forbidden Transitions.
In 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG), LNCS, Springer, 2015. -
Bi Li, Fatima Zahra Moataz, Nicolas Nisse and Karol Suchan, Minimum Size Tree-Decompositions.
In 8th Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS), 2015. -
David Coudert, Dorian Mazauric and Nicolas Nisse. Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth.
In 13rd Symposium on Experimental Algorithms (SEA), LNCS, Springer, pages 46-58, 2014. -
Julio Araujo, Nicolas Nisse and Stéphane Pérennes. Weighted Coloring in Trees.
31st Symposium on Theoretical Aspects of Computer Science (STACS), Schloss Dagstuhl, pages 75-86, 2014. -
Bi Li, Fatima Zahra Moataz, Nicolas Nisse and Karol Suchan, Minimum Size Tree-Decompositions.
Extended abstract in 9th International colloquium on graph theory and combinatorics (ICGT), 2014 (no Proceedings). [Research Report], 2014, pp. 23. hal-01074177 - 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, pages 149-164, 2014.
- 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.
Research Reports
- Fionn McInerney, Nicolas Nisse, Stéphane Pérennes, Eternal Domination in Grids, [Research Report] Inria & Univ. Nice Sophia Antipolis, CNRS, I3S, Sophia Antipolis, France. 2018
- David Coudert, Marcos Kiwi, and Dieter Mitsche. On the hyperbolicity of random hyperbolic graphs. In preparation.
- Patricio Rodríguez, Ricardo Truffello, Karol Suchan, Francisca Varela, Manuel Matas, Javier Mondaca, Javiera Céspedes, Luis Valenzuela, Juan Pablo Valenzuela and Claudio Allende, Apoyando la formulación de políticas públicas y toma de decisiones en educación utilizando técnicas de análisis de datos masivos : el caso de Chile,
- Patricio Rodríguez, Juan Pablo Valenzuela, Karol Suchan, Ricardo Truffello and Nicol Norel, Determinando el acceso real de los estudiantes a establecimientos educacionales efectivos para generar políticas públicas que mejoren la provisión de educación de calidad.
Theses
- Marko Oleksiyenko, Bicycle-oriented itinerary computation for smart cities. Master thesis, Univ. Nice Sophia Antipolis, March-August, 2017.
- Guillaume Ducoffe. Propriétés métriques des grands graphes. Ph.D. thesis, Univ. Nice Sophia Antipolis, December 9th, 2016.
- Vladislav Zaika, Optimizing the transport network of a large metropolitan area to improve citizen accessibility. Master thesis, Univ. Nice Sophia Antipolis, March-August, 2016.
- Fatima Zahra Moataz. Towards Efficient and Fault-Tolerant Optical Networks: Complexity and Algorithms. Ph.D. thesis, Univ. Nice Sophia Antipolis, October 30th, 2015.
- Nicolas Nisse, Algorithmic complexity: Between Structure and Knowledge How Pursuit-evasion Games help. HDR, Univ. Nice Sophia Antipolis, May 26th, 2014.
- Bi Li, Tree Decompositions and Routing Problems. Ph.D. thesis, Univ. Nice Sophia Antipolis, November 12th, 2014.
- Esteban Roman Catafau, Analysis of a Branch and Bound algorithm for pathwidth, internship report, May-July 2014.
- Klaus Jaschan, Implementing a Vertex Separation algorithm for trees in Sagemath, internship report, Dec. 2013- Feb. 2014.
- Ronan Soares, Pursuit-evasion, decompositions and convexity on graphs. Ph.D. thesis, Univ. Nice Sophia Antipolis, November 8th, 2013.
Related Links
- Apoyando la formulación de políticas públicas y toma de decisiones en educación
- Investigadores INRIA y UAI trabajarán en conjunto
Scientific programme and objectives
Context: Current evolution of telecommunication networks leads to new algorithmic challenges. Indeed, both the size of networks as well as the amount of traffic in such networks grow drastically. In this context, numerous problems become challenging to solve even if there exist algorithms that are suitable for smaller networks (in general n-node graphs, algorithms of running time \(O(n^4)\) are not scalable to networks of size \(n=10^4\); at \(n=10^5\) even \(O(n^3)\) is impractical). Therefore, solutions proposed so far do not scale up and new alternatives must be provided. On the one hand, recent results have proposed to design algorithms that take advantage of special structural properties often found in large-scale networks to achieve better performances. Indeed, it is well known that many telecommunication, social, and biological networks share structural properties such as logarithmic diameter, power-law degree distribution and high clustering coefficient. These properties can be exploited for algorithmic purposes (e.g., for routing). On the other hand, centralized solutions proposed so far do not allow to efficiently face the dynamicity of these networks (variations of both topology and state of connections). Moreover, another important aspect of some of the new networks is that they are not defined in a global way (but, e.g., social networks are defined through local interactions). Hence, it is interesting to propose distributed or even localized solutions, i.e., algorithms based on information that can be retrieved locally and in a distributed way. Many recent works study the tradeoffs between the power of communication and the kind of structural properties that can be computed.
Objectives: The main goal of this Associate Team is to study the structure of networks (modeled by graphs) to design both efficient distributed algorithms and reliable network topologies suitable to applications. We are interested both in large-scale (Facebook, Internet, etc.) and in smaller networks (e.g., WDM) that handle heavy traffic. More precisely, we aim at designing new techniques of distributed and localized computing to test structural properties of networks and to compute structures (e.g., decompositions) to be used in applications. Concerning the applications, we will first focus on routing and subgraph packing problems.
There are two main objectives:
- Find efficient localized algorithms to test certain graph properties or to prove that no such algorithms exist. We will formalize several distributed computing models and analyze which properties can and which cannot be tested in them.
- Define graph properties – computable or approximable in distributed systems – such as structures/decompositions/representations. The driving idea is to combine several well studied graph properties in order to obtain more specific structures that we hope to be computable more easily.
To verify the practical efficiency of our results, the designed algorithms will be implemented and compared to existing ones. For this purpose, a particular effort will be put to design and implement algorithms to generate graphs that satisfy properties of interest, in order to use them to test the algorithms.
The originality of the proposal is to combine powerful tools of graphs theory (e.g., FPT complexity) and of combinatorial optimization (Mixed Integer Programming) with distributed computing. One challenge here is to balance between the degree of locality of desired algorithms and the relevance of properties that may be computed.
Work-program
Last decade have shown promising advances in exploiting the structure of the underlying graph to solve hard problems efficiently. We propose to study structural properties of graphs with two main guidelines: to focus on specific graph classes and to keep in mind the algorithmic applications of the considered properties. We expect to find structures that could be computed easily (by greedy or localized algorithms) and that would allow to design efficient algorithms for important problems like routing or graph packing.
For this purpose, we want to first extend the classical centralized approaches to have a better understanding of graph structures:
- To continue the study of graphs decompositions: in particular, it is important to design simple algorithms to compute (or approximate) decompositions in particular graphs classes: for instance, graphs with small treewidth (generic algorithms of Bodlaender and Kloks being inefficient even in such graphs classes), subclasses of planar graphs (the complexity of computing treewidth of planar graphs is still open).
An approach that we will follow during the first year is the computation of such decompositions via integer programming, branch and bound and separation algorithms. Very few works have considered this direction. - To generalize this study to directed graphs: currently several groups of researchers (e.g., [Ganian et al. 2010]) aim at designing “good” decompositions for directed graphs, i.e., having the same algorithmic performances as tree-decompositions in the undirected case.
Most of the graph characteristics used to improve the performances of algorithms are centralized and global structures. We aim at deriving simpler structures and graph characterizations that could be locally computable. In particular, we want to focus on information localized at vertices (or close neighborhoods) that suffices to compute structural properties that support efficient algorithms for applications, therefore:
- To focus on characterizations that may be efficiently computed and used in a distributed setting. For instance, in the case of tree-decompositions, the size of the “pieces” of the decomposition is important to obtain efficient generic algorithms using dynamic programming. However, when we are interested in specific problems, it would be more relevant to consider the structure of the pieces instead of their size. For instance, preliminary results show that graphs with bounded chordality admit tree-decompositions where each bag has a short dominating path. Moreover, such a decomposition can be computed by a greedy algorithm and has interesting applications for compact routing.
- To propose new characterizations for graphs satisfying a combination of classical properties. It will be crucial to design algorithms to check whether a graph satisfies these combinations, and to generate families of graphs satisfying them. A particular attention will be paid to properties and structures of real-world networks.