AC: Algorithmes et calcul

The Algorithm and Computation line studies graph algorithms, parameterized complexity, cellular automata, tilings, and words. It is also involved in operations research (optimization problems for networks, scheduling). Researchers in the computation field focus on high-performance computing and its validation, the exploitation of new parallel architectures, symbolic computation, computer arithmetic, cryptography and algorithmic number theory. Combinatorial, probabilistic and statistical approaches are used to tackle problems in bioinformatics such as sequence analysis, evolution study, functional annotation of genes and proteins.
The Algorithm and Computation line includes 80 researchers working in 5 research teams (Algco, Escape, Dali, Icar, Maore).


Seminars and working groups

Algorithm and Computation line's seminars

from 2013-06-27 to 2013-06-27

Orateur : Nicolas Trotignon (CNRS, Ens Lyon)
Titre : Décomposition des graphes parfaits

Résumé : La conjecture forte des graphes parfaits, énoncée dans les années 1960 par Claude Berge a été démontrée en 2002 par Chudnovsky, Robertson, Seymour et Thomas par des méthodes de décompositions de graphes. Je rappellerai très brièvement les principales notions et les idées de la preuve. J'insisterai sur le verrou qui empêche d'utiliser la preuve pour résoudre la dernière "grande question" ouverte sur les graphes parfaits, à savoir leur coloration en temps polynomial par un algorithme purement combinatoire. Ce verrou provient de décompositions "pathologiques", qui ont de bonnes propriétés pour la preuve, mais pas pour les algorithmes, par exemple les "skew partitions" inventées par Chvatal. Les skew partitions ont pour cas particulier les "star cutset", dont il sera principalement question par souci de simplification. A la fin de l'exposé, je présenterai très brièvement un résultat obtenu récemment avec Chudnovsky, Trunck et Vuskovic : un algorithme en temps polynomial qui colore les graphes parfaits sans "balanced skew partition".
from 2013-05-13 to 2013-05-13

Orateur : Dmitry Itsykson (Steklov Institute of Mathematics at St. Petersburg)
Titre : Proof systems and SAT algorithms.


Orateur : Joergen Bang-Jensen, University of Southern Denmark
Titre : flows, graphs, (arc-)disjoint paths and flows

Résumé : Flows in networks constitute probably the most important application of graph theory with litterally hundreds of practical applications. In this talk we will introduce flows and the fundamental max-flow min-cut theorem and show how this basic result has important applications as a proof techniques in graph theory.
Then we will go on to the (arc)-disjoint paths problem and discuss the complexity of this problem in both graphs and digraphs. In the last part of the talk we will introduce a common generalization of flows and disjoint paths, the (arc-)disjoint flow problem.


from 2012-04-19 at 14:00 to2012-04-17 at 15:00

Orateur : Erich Kaltofen (North Carolina State University)
Titre : The Art of Hybrid Computation

Résumé : Hybrid symbolic-numeric computation constitutes the Fifth of my "Seven Dwarfs" of Symbolic Computation, which I have listed in my SNSC talk in Hagenberg in 2008. Hybridization requires that the solution of a computational mathematical problem should utilize both a numeric and a symbolic algorithmic component.

In my talk, I will characterize the hybrid methodology by surveying some important results and the lessons I have learned from them. Those include the notion of approximate GCD and approximate sparse interpolant, and the task of the analysis of the random distributions of matrix condition numbers in randomized hybrid algorithms.

One can bypass the analysis by producing a certificate, and I will give sum-of-squares certificates in global optimization via our ArtinProver
software. Specifically, I will discuss certificates of impossibility of sum-of-squares representations based on the Farkas Lemma of semidefinite

This work is in collaboration with Matthew Comer, Feng Guo, Wen-shin Lee, Clement Pernet, Zhengfeng Yang, and Lihong Zhi.

from 2012-03-29 at 14:00 to2012-03-29 at 15:00

Orateur : Pavol Hell (Simon Fraser University)
Titre : Finite obstructions to graph partitions

Résumé : Consider graph partitions with possible restrictions on the parts, and on the connections between parts: the restrictions can be that there are no edges, or that all possible edges are present. Many partitions arising in the study of perfect graphs have this flavour. In some cases the existence of such a partition is characterized by the absence of finitely many forbidden induced subgraphs. We ask when this is the case, and give some general answers, and some answers for special graph classes, such as chordal graphs. These include joint results with T. Feder, S. Nekooei Rizi, W. Xie, O. Shklarsky, and others.
from 2012-02-02 at 15:00 to2012-02-02 at 16:00

Orateur : Dimitrios Thilikos (Department of Mathematics, National and Kapodistrian University of Athens)
Titre : Algorithmic Graph Minors: turning Combinatorics to Algorithms

Résumé : The main mathematical achievement of the Graph Minors Theory, developed by Robertson and Seymour, was the proof of Wagner's conjecture, now known as the Robertson & Seymour Theorem, stating that graphs are well quasi ordered under the minor containment relation. Besides its purely theoretical importance, GMT induced a series of powerful algorithmic results and techniques that had a deep influence in theoretical computer science. GMT offered the theoretical base for the understanding and the resolution of some of the most prominent graph-algorithmic problems in the design of parameterized algorithms. In this talk we give a brief presentation of the main results and techniques to this direction and we comment on their potential and their limitations.



Algorithmique, complexité, calculs, mathématiques discrètes, combinatoire

Last update on 07/01/2019