A set of subsets is said to have the Helly property if the condition that each pair of subsets has a non-empty intersection implies that the intersection of all subsets has a non-empty intersection. In 1966, Gallai noticed that the set of all longest paths of a connected graph is pairwise intersecting and asked if the set had the Helly property. While it is not true in general, a number of classes of graphs have been shown to have the property. In this dissertation, we show that K4-minor-free graphs, interval graphs, circular arc graphs, and the intersection graphs of spider graphs are classes that have this property. The accuracy of facial recognition algorithms on images taken in controlled conditions has improved significantly over the last two decades. As the focus is turning to more unconstrained or relaxed conditions and toward videos, there is a need to better understand what factors influence performance. If these factors were better understood, it would be easier to predict how well an algorithm will perform when new conditions are introduced. Previous studies have studied the effect of various factors on the verification rate (VR), but less attention has been paid to the false accept rate (FAR). In this dissertation, we study the effect various factors have on the FAR as well as the correlation between marginal FAR and VR. Using these relationships, we propose two models to predict marginal VR and demonstrate that the models predict better than using the previous global VR.

No description available.

Les graphes définis à partir de structures algébriques possèdent d’excellentes propriétés de symétries particulièrement intéressantes. L’exemple le plus flagrant est la notion de graphe de Cayley qui s’est révélée très riche non seulement du point de vue théorique mais aussi pratique par ses applications à de nombreux domaines incluant l’architecture des réseaux ou les machines parallèles. Néanmoins, la régularité des graphes de Cayley se révèle parfois être une limite étant donné qu’ils sont toujours sommet-transitifs et donc en particulier non pertinents pour générer des réseaux semiréguliers.Cette observation a motivé, en 2005, la définition d’une nouvelle classe de graphes définis à partir d’un groupe, appelés G-graphes. Ils possèdent aussi de nombreuses propriétés de régularité mais de manière moins restrictive.Cette thèse propose un nouveau regard sur cette classe de graphes par une approche plutôt orientée recherche opérationnelle alors que la grande majorité des études précédentes est dominée par des approches essentiellement algébriques. Nous-nous sommes alors intéressés à plusieurs questions :— La caractérisation des G-graphes : nous proposons des améliorations par rapport aux précédents résultats.— Identifier des classes de graphes comme des G-graphes grâce à des isomorphismes ou en utilisant le théorème de caractérisation.— Etudier la structure et les propriétés de ces graphes, en particulier pour de possibles applications aux réseaux : colorations semi-régulières, symétries et robustesse.— Une approche algorithmique pour la reconnaissance de cette classe avec notamment un premier exemple de cas polynomial lorsque le groupe est abélien. / Interactions between graph theory and group theory have already led to interesting results for both domains. Graphs defined from algebraic groups have highly symmetrical structure giving birth to interesting properties. The most famous example is Cayley graphs, which revealed to be particularly interesting both from a theoretical and a practical point of view due to their applications in several domains including network architecture or parallel machines. Nevertheless, the regularity of Cayley graphs is also a limit as they are always vertex-transitive and therefore not relevant to generate semi-regular networks. This observation motivated the definition, in 2005, of a new family of graphs defined from a group, called G-graphs. They also have many regular properties but are less restrictive. These graphs are in particular semi-regular k-partite, with a chromatic number k directly given in the group representation and they can be either transitive or not.This thesis proposes a new insight into this class of graphs using an approach based on operational research while most of previous studies have been so far dominated by algebraic approaches. Then, the thesis addresses different kind of questions:— Characterizing G-graphs: we propose improvements of previous results.— Identifying some classes of graphs as G-graphs through isomorphism or using the characterization theorem.— Studying the structure and properties of these graphs, in particular for possible applications to networks: semi-regular coloring, symmetries and robustness.— Algorithmic approach for recognizing this class with a first example of polynomial case when the group is abelian.