Passer au contenu

/ La recherche

Rechercher

Sciences naturelles et génie; Sciences appliquées

Gena Hahn

Graphes : existence, propriétés, applications

Professeur titulaire

Faculté des arts et des sciences - Département d'informatique et de recherche opérationnelle

André-Aisenstadt, local 3351

514 343-6806

gena.hahn@umontreal.ca

Autre numéro : 514 343-5834 (Télécopieur)

Médias

Gena Hahn (University of Montreal) / Cops, robbers, infinite graphs and related problems

Portrait

Expertise de recherche

Mon intérêt principal est la théorie des graphes et les domaines annexes tels combinatoire, algorithmique et complexité, communication dans des réseaux d'interconnexion, etc. J'aime des résultats théoriques et structurels qui mènent à une meilleure compréhension et je considère des problèmes assez variés. Les graphes infinis sont très intéressants et je travaille également sur des jeux de policiers et voleurs sur des graphes (les deux sujets se rencontrent parfois).

Formation

  • 1986 — Doctorat d'état — InformatiqueUniversité de Paris-Sud
  • 1981 — Ph.D. — Mathématiques fondamentalesUniversité McMaster

Affiliations et responsabilités

Affiliations de recherche

Unités de recherche

Membre

Contribution au fonctionnement de l’institution

Activités au sein d’organismes ou d’entités de l’institution

  • Membre du Laboratoire d'informatique théorique et quantique

Enseignement et encadrement

Encadrement

Thèses et mémoires dirigés (dépôt institutionnel Papyrus)

2019

Domination éternelle dans les graphes

Diplômé(e) : Virgile, Virgélot
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
2015

Droites sur les hypergraphes

Diplômé(e) : Bayani, Aryan
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
2012

Complexité des homomorphismes de graphes avec listes

Diplômé(e) : Lemaître, Adrien
Cycle : Doctorat
Diplôme obtenu : Ph. D.
2007

Reconnaissance des graphes policier-gagnants

Diplômé(e) : Thériault, Benoit
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
2007

Jeu de poursuite sur graphe non réflexif

Diplômé(e) : El Ouarari, Amal
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
2006

Contribution à la conjecture d'Erdos-Farber-Lovász

Diplômé(e) : Akrout, Khaled
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
2006

Études du jeu de poursuite dans les graphes

Diplômé(e) : Zine, Youssef
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
2006

Graphe et jeu de poursuite : policiers et voleurs sous contraintes

Diplômé(e) : El Harti, Sif El Islam
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
2005

Jeu de poursuite sur des modèles du web et généralisation

Diplômé(e) : Ramanampanoharana, Tantely
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
2004

A survey of graph and subgraph isomorphism problems

Diplômé(e) : Lei, Yaohui
Cycle : Maîtrise
Diplôme obtenu : M. Sc.
2003

Problèmes de routages dans les réseaux optiques

Diplômé(e) : Houndété, Alfred
Cycle : Maîtrise
Diplôme obtenu : M. Sc.

Projets

Projets de recherche

2017 - 2024

Graph searching structural properties

Chercheur principal : Gena Hahn
Sources de financement : CRSNG/Conseil de recherches en sciences naturelles et génie du Canada (CRSNG)
Programmes de subvention : PVX20965-(RGP) Programme de subvention à la découverte individuelle ou de groupe
2015 - 2022

CENTRE DE RECHERCHES MATHEMATIQUES (CRM)

Chercheur principal : Luc Vinet
Co-chercheurs : Pavel Winternitz , Alfred Michel Grundland , Christiane Rousseau , Sabin Lessard , François Perron , Sylvie Hamel , Marlène Frigon , Karim Jerbi , Jacques Bélair , François Lalonde , Robert Gwyn Owens , Gilles Brassard , Alain Vinet , Michel Delfour , Yvan Saint Aubin , Manuel Morales , Paul M Gauthier , Manu Paranjape , Véronique Hussin , Fahima Nekka , Yoshua Bengio , Pierre Duchesne , Jiri Patera , Nadia El-Mabrouk , Louis-Pierre Arguin , Andrew Granville , Iosif Polterovich , Octavian Cornea , Matilde Lalin , Dimitrios Koukoulopoulos , Hélène Cossette , Christian Genest , Frédéric Gourdeau , Claude Levesque , Étienne Marceau , Pierre Mathieu , Thomas Joseph Ransford , Louis-Paul Rivest , Jean-Marie De Koninck , Javad Mashreghi , Thierry Duchesne , José Manuel Urquiza , Hugo Chapdelaine , Michael Lau , Alexandre Girouard , Antonio Lei , Pengfei Guan , Xiaowen Chang , Michael C. Mackey , John A Toth , Henri Darmon , Karl Peter Russell , Niky Kamran , Jacques Claude Hurtubise , Adrian Iovita , Peter Bartello , Eyal Goren , Dmitry Jakobson , Vojkan Jaksic , Daniel Tzvi Wise , Anthony Raymond Humphries , Frederic Guichard , Erik P. Cook , Robert Brandenberger , Adrian Vetta , Erica Moodie , Keshav Dasgupta , Christophe Grova , Bruce Shepherd , David Stephens , Gantumur Tsogtgerel , Johanna Neslehova , Jean-Christophe Nave , Johannes Walcher , Paul François , Anmar Khadra , Adam M. Oberman , Michael Yves Michel Pichot , Frédéric Lesage , Jean-Marc Lina , Alexander Maloney , Dana Louigi Addario-Berry , André Fortin , André Garon , Dominique Pelletier , Éric P. Marchand , Debbie Janice Dupuis , Syed Ali , Yogendra Chaubey , Christopher Cummins , Chantal David , Eusebius Jacobus Doedel , José Garrido , Pawel Gora , Richard Hall , John P. Harnad , Hershy Kisilevsky , Galia Dafni , D. Korotkin , Benoit Larose , Marco Bertola , Alexei Kokotov , Wei Sun , Alina Stancu , Patrice Gaillardetz , Lea Popovic , André Dieter Bandrauk , Ibrahim Assem , Tomasz Kaczynski , Shiping Liu , Virginie Charette , Vasilisa Shramchenko , Maxime Descoteaux , Anne Bergeron , François Bergeron , Steven P. Boyer , Srecko Brlek , Christophe Reutenauer , Jean-François Renaud , Vestislav Apostolov , Steven Lu , Pedro Peres-Neto , Christophe Hohlweg , Mathieu Boudreault , FRANCO SALIOLA , Alexandre Roch , Frédéric Rochon , Mark Powell , Bruno L. Rémillard , Alexandre Blondin-Massé , Thomas Brüstle , Richard Fournier , Linan Chen , Jal Choksi , Clement Hyvrier , Payman Kassaei , Piotr Przytycki , Hélène Cossette , Christian Genest , Frédéric Gourdeau , Claude Levesque , Étienne Marceau , Pierre Mathieu , Thomas Joseph Ransford , Louis-Paul Rivest , Jean-Marie De Koninck , Javad Mashreghi , Thierry Duchesne , José Manuel Urquiza , Hugo Chapdelaine , Michael Lau , Alexandre Girouard , Antonio Lei , André Fortin , Anne Bergeron , François Bergeron , Steven P. Boyer , Srecko Brlek , Christophe Reutenauer , Jean-François Renaud , Vestislav Apostolov , Steven Lu , Pedro Peres-Neto , Christophe Hohlweg , Mathieu Boudreault , FRANCO SALIOLA , Alexandre Roch , Frédéric Rochon , Mark Powell , Alexandre Blondin-Massé , Clement Hyvrier , Maciej Augustyniak , Jun Li , William Witczak-Krempa , M'Hamed Lajmi Lakhal Chaieb , Khader Khadraoui , Prakash Panangaden , Hamed Hatami , Roger Villemaire , Geneviève Lefebvre , Karim Oualkacha , Denis Talbot , Jean-François Coeurjolly , Frédéric Godin , Marcin Sabok , Yi Yang , Anne Mackay , Paramita Saha Chaudhuri , Jérôme Vétois , Ting-Huei Chen , Gena Hahn , Mireille Schnitzer , Alexander Fribergh , Benjamin Seamone , Egor Shelukhin , Alejandro Murua , Mylène Bédard , Alain Tapp , Laurent Charlin , Christian Genest , Alexandre Bureau , Nicolas Doyon , R Platt , Bruce Alan Reed , Russell Steele , Vladimir Makarenkov , Vahid Partovi Nia , Xiaowen Zhou , Cody Hyndman , Taoufik Bouezmani , Sorana Froda , Simon Guillotte , Aurélie Labbe , Mélina Mailhot , Alexandra Schmidt , Simon Philippe Caron-Huot
Sources de financement : FRQNT/Fonds de recherche du Québec - Nature et technologies (FQRNT)
Programmes de subvention : PVXXXXXX-(RS) Programme de regroupements stratégiques
2012 - 2018

GRAPH SEARCHING AND APPLICATIONS

Chercheur principal : Gena Hahn
Sources de financement : CRSNG/Conseil de recherches en sciences naturelles et génie du Canada (CRSNG)
Programmes de subvention : PVX20965-(RGP) Programme de subvention à la découverte individuelle ou de groupe
2008 - 2016

CENTRE DE RECHERCHES MATHEMATIQUES (CRM)

Chercheur principal : Luc Vinet
Co-chercheurs : Pavel Winternitz , Christiane Rousseau , Sabin Lessard , François Perron , Sylvie Hamel , Gena Hahn , Marlène Frigon , Jacques Bélair , François Lalonde , Robert Gwyn Owens , Gilles Brassard , Michel Delfour , Yvan Saint Aubin , Manuel Morales , Jonathan Taylor , Paul M Gauthier , Manu Paranjape , Véronique Hussin , Fahima Nekka , Christian Léger , Jean-François Angers , Yoshua Bengio , Pierre Duchesne , Anne Bourlioux , Abraham Broer , Jiri Patera , Nadia El-Mabrouk , Andrew Granville , Iosif Polterovich , Octavian Cornea , Line Baribeau , Christian Genest , Frédéric Gourdeau , Robert Guénette , Claude Levesque , Pierre Mathieu , Thomas Joseph Ransford , Louis-Paul Rivest , Jean-Marie De Koninck , Javad Mashreghi , Thierry Duchesne , Pengfei Guan , David Avis , Michael C. Mackey , James Owen Ramsay , John A Toth , Sherwin A Maslowe , Henri Darmon , David B Wolfson , Karl Peter Russell , Olga Kharlampovich , Niky Kamran , Jacques Claude Hurtubise , Adrian Iovita , Peter Bartello , Eyal Goren , Dmitry Jakobson , Alain C. Vandal , Vojkan Jaksic , Daniel Tzvi Wise , Anthony Raymond Humphries , Alexei Miasnikov , Erica Moodie , Thomas Wihler , Robert Seiringer , Johannes Walcher , Frédéric Lesage , Jean-Marc Lina , André Fortin , André Garon , John Mullins , Éric P. Marchand , Debbie Janice Dupuis , Syed Ali , Yogendra Chaubey , Christopher Cummins , Chantal David , Pawel Gora , John P. Harnad , Hershy Kisilevsky , John McKay , Galia Dafni , D. Korotkin , Benoit Larose , Marco Bertola , Vasek Chvatal , Alexander Shnirelman , Alina Stancu , Lea Popovic , André Dieter Bandrauk , Ibrahim Assem , Tomasz Kaczynski , Shiping Liu , Virginie Charette , Vasilisa Shramchenko , Maxime Descoteaux , François Bergeron , Steven P. Boyer , Srecko Brlek , André Joyal , Brenda MacGibbon , Christophe Reutenauer , Vestislav Apostolov , Olivier Collin , Steven Lu , Bruno L. Rémillard , Elisa Shahbazia Ohannessian , Yinannis Petridis , David Sankoff , Thomas Brüstle , Habib Benali , Nantel Bergeron , Simon Chauve , Francis Clarke , Richard Fournier , Martin Jakob Gander , Nadia Ghazzali , Alfred Michel Grundland , Line Baribeau , Christian Genest , Frédéric Gourdeau , Robert Guénette , Claude Levesque , Pierre Mathieu , Thomas Joseph Ransford , Louis-Paul Rivest , Jean-Marie De Koninck , Javad Mashreghi , Thierry Duchesne , André Fortin , François Bergeron , Steven P. Boyer , Srecko Brlek , André Joyal , Brenda MacGibbon , Christophe Reutenauer , Vestislav Apostolov , Olivier Collin , Steven Lu , Elisa Shahbazia Ohannessian
Sources de financement : FRQNT/Fonds de recherche du Québec - Nature et technologies (FQRNT)
Programmes de subvention : PVXXXXXX-(RS) Programme de regroupements stratégiques

Rayonnement

Publications et communications

Publications

B. Bagheri, G. Hahn, A note on the circuit double cover of infinite graphs, Journal of Combinatorics, accepted 2016

A. Bonato, G. Hahn, C. Tardif, « Large classes of infinite k-cop-win graphs », Journal of Graph Theory 65 (2010), 334 - 342

G. Hahn, G. MacGillivray, « A characterisation of k-cop-win graphs and digraphs »,  Discrete Mathematics 306 (2006), 2492 - 2497

G. Hahn, F. Laviolette, N. Sauer, R.E. Woodrow, «On cop-win graphs», Discrete Mathematics 258 (2002), pp. 27 - 41

G. Hahn, J. Siran, D. Sotteau, «On the injective chromatic number of graphs », Discrete Mathematics 256 (2002), pp. 179 - 192

G. Hahn, C. Tardif, «Graph homomorphisms: structure and symmetry», in Graph symmetry, ASI ser C, Kluwer, 1997, pp. 107 -- 166

G. Hahn, P. Hell, S. Poljak, «On the ultimate independence ratio», European Journal of Combinatorics 16 (1995), pp. 253 - 261

G. Hahn, E. Milner, R.E. Woodrow, «Infinite Friendship Graphs with Infinite Parameters», Journal of Combinatorial Theory (B) 52 (1991) pp. 30 - 41

M. Farber, G. Hahn, P. Hell, D. Miller, «Concerning the achromatic number of graphs», Journal of Combinatorial Theory (B) 40 (1986) pp. 21 - 39

Disciplines

  • Informatique
  • Mathématiques appliquées
  • Mathématiques fondamentales

Champ d’expertise

  • Algorithmes de graphes
  • Algorithmes de routage
  • Colorations des graphes
  • Graphe de Cayley
  • Graphes infinis
  • Homomorphismes de graphes
  • Jeux poursuite évasion
  • Mathématiques discrètes
  • Symétries des graphes
  • Théorie des graphes