SticAmSud GALOP

GALOP

Graphs ALgorithms for Optimization Problems

Programme STIC-AmSud 2019-2020

  • Centre de recherche INRIA Sophia Antipolis — Méditerranée, Team project COATI, France
  • Universidade Federal do Ceara, Fortaleza, Brazil
  • Universidad Diego Portales (UDP), Santiago, Chile

International coordinator Brazilian coordinator Chilean coordinator
Name, surname Nicolas Nisse Julio Araujo Karol Suchan
Title Chargé de recherche Inria (Research officer) Associated professor Associated professor
Institution team-project COATI, common team
INRIA Sophia Antipolis – I3S (UMR 7271 of the CNRS and the University of Nice-Sophia Antipolis)
Departamento de Matemática
Universidade Federal do Ceará. ParGO Research Group, Fortaleza Brazil.
Universidad Diego Portales, 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

Universidade Federal do Ceará

Departamento de Matemática – bloco 914.

Av. Humberto Monte, s/n, Campus do Pici.

CEP 60440-900. Fortaleza, CE

Brazil.

Universidad Diego Portales,

Facultad de Ingeniería y Ciencias

Av. Ejército Libertador 441,

Santiago,

Chile

URL http://www-sop.inria.fr/members/Nicolas.Nisse/ http://www.mat.ufc.br/~julio/ http://udp.academia.edu/KarolSuchan
Phone +33 4 97 15 53 28 +55 (85) 33 66 93 13 +56 9 57 76 57 79
email name dot surname arobase inria dot fr name arobase mat dot ufc dot br name dot surname arobase mail dot udp dot cl

Activity reports

Participants

Documents

Visits in 2019

  • To Inria
    • R. Lopez, 1 month, July 2019
    • F. Benevides, invited Professor, 11 months, September 2019- July 2020
    • J. Araujo, 2 weeks, December 4-20th 2019
      He gave a seminar on “Weighted proper orientations of trees and graphs of bounded treewidth”, Dec. 10th, 2019.
    • A. K. Maia, 2 weeks, December 4-20th 2019
    • C. Linhares Sales, 2 weeks, December 4-20th 2019
    • J. Costa, PhD thesis “sandwich”, 1 year, December 2019- November 2020
    • K. Suchan, 2 weeks, December 8-21th 2019
      He gave a seminar on “Fault Tolerant Complete Matchings in Bipartite Graphs and Related Problems”, Dec. 17th, 2019.
  • To UFC
    • J. Bensmail, 2 weeks, May 4-18 2019
      He gave a seminar on « 1-2-3 conjecture », May 6th 2019.
    • N. Nisse, 2 weeks, May 4-18 2019
      He gave a seminar on «Recovery of disrupted airline operations andconstrained matchings», May 10th 2019.
    • K. Suchan, 1.5 weeks, August 10-19 2019
      He gave a seminar on “Vertex-Fault Tolerant Complete Matching in Bipartite graphs: the Biregular Case” (August 13th 2019) during the Workhop organized for the 20 years of the team Pargo,
  • To UDP
    • F. Havet, 2 weeks, October 30th-10th November 2019
      Invited speaker at French-latin American conference on new trends in Applied Mathematics (Flacam)(canceled due to strikes in Chile)

Publications of (or related to) the Project

International journals

International conferences

  • Julien Bensmail, Foivos Fioravantes, Fionn Mc Inerney, and N. Nisse. The Largest Connected Subgraph Game.
    In Proceedings of 47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), to appear, 2021.
  • Thomas Dissaux, Guillaume Ducoffe, Nicolas Nisse, Simon Nivelle. Treelength of Series-parallel graphs.
    To appear in Proceedings of 11th Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS), 2021.
  • Cláudio Carvalho, Jonas Costa, Cláudia Sales, Raul Lopes, Ana Karolinna Maia de Oliveira, Nicolas Nisse. On the characterization of networks with multiple arc-disjoint branching flows. In Anais do Encontro de Teoria da Computacao (ETC), Brazil, 2020.
  • J. Bensmail, F. Mc Inerney, N. Nisse. Metric Dimension: from Graphs to Oriented Graphs. In Proceedings of the 10th Latin & American Algorithms, Graphs and Optimization Symposium (LAGOS 2019). Belo Horizonte, Brazil, 2019.

Research Reports

Theses

  • Hernán Lespay. Consistent Vehicle Routing. Ph.D. thesis, Universidad Adolfo Ibáñez, Chile, January 22nd, 2021.
  • Fionn McInerney. Domination and Identification Games in Graphs. Ph.D. thesis, Univ. Côte d’Azur, July 8th, 2019.
  • Camila Sena Araújo. Colorações backbone em grafos com galáxias backbone. Master’s in Mathematics – Universidade Federal do Ceará. 2021.
  • Pedro Santos Mota e Arraes. Números de envoltória e geodético em classes de grafos orientados. Master’s in Mathematics – Universidade Federal do Ceará. 2020.
  • Thomas Dissaux. Graph Decompositions and treelength. M2 internship (March-August 2020), Univ. Côte d’Azur.
  • Pedro Paulo de Medeiros. Coloração Acíclica. Master’s in Mathematics – Universidade Federal do Ceará, 2019.

Related Links

Workhop organized for the 20 years of the team Pargo: http://dc.ufc.br/~pargo_20_50/


Scientific programme and objectives

Our goal is to study the Computational Complexity of several important problems arising in
networks. In particular, we will focus on the computation of metric or structural properties and
parameters of large networks. We plan to design efficient exact algorithms for solving these
problems or to theoretically prove that such algorithms cannot exist. In the latter case, we will then
design approximation algorithms, or prove that none exists. In all cases, we aim at implementing
our algorithms and use them on real-world instances such as large road networks or huge social
networks.


Work-program

In this project, we will mainly tackle three kinds of network problems that are naturally modeled as
graph-theoretical problems.

  • First, we will consider graph decompositions: how to efficiently compute “good”
    decompositions (e.g., tree-decompositions) and how such decompositions (e.g.,
    decompositions with clique-separators) can be used to speed-up the actual running time of
    algorithms for computing various graph metrics. As an example of application, we will
    consider road-networks for which new usages (e.g. multi-modal transportation) require
    algorithms to compute shortest paths more efficiently and in a dynamic setting.
  • Second, we will study combinatorial games in graphs because they naturally model many
    network problems in different contexts. For instance, localization games are a gametheoretic
    way to handle the detection of faults in multiprocessor networks (e.g., via
    identifying codes or metric dimension). Another example is the surveillance game that is a
    nice theoretical model for data prefetching.
  • Last but not least, we will obtain new results in two graph optimization problems: graph
    colorings that naturally model various allocation problems (e.g., resource assignment, like
    channel assignment in radio networks, personnel assignment, etc.), and graph convexity that
    may be seen as a model of diffusion in a network (e.g., spreading opinions/innovations,
    propagating diseases/faults, logical inference, etc.). An objective of particular interest is to
    study propagation of information in real social networks.

Since all these problems are complex, we will start by considering simpler models or hypothesis
(for instance, consider a problem on a more restricted graph class) and then obtain results in a more
refined setting. For instance, we will first focus on the case of undirected graphs, which is generally
easier than that of directed graphs. After getting some understanding of the undirected case, we will
then consider the directed one.

Comments are closed.