Passer au contenu

/ La recherche

Je donne

Rechercher

Natural Sciences and Engineering; Applied Sciences

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, room 3351

514 343-6806

gena.hahn@umontreal.ca

Secondary number: 514 343-5834 (Télécopieur)

Media

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

Profile

Research expertise

My main interest is graph theory and related areas, such as combinatorics, algorithms and complexity, communication in interconnection networks. I like theoretical and structural results that lead to better understanding. I do and will think about many different problems.

education

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

Affiliations and responsabilities

Research affiliations

University service and activities

Activities within organizations or entities of the institution

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

Teaching and supervision

Student supervision

Theses and dissertation supervision (Papyrus Institutional Repository)

2022

Une étude des graphes jumeaux via l'auto-abritement

Graduate : Gagnon, Alizée
Cycle : Master's
Grade : M. Sc.
2021

Le jeu de policiers-voleur sur différentes classes de graphes

Graduate : Turcotte, Jérémie
Cycle : Master's
Grade : M. Sc.
2019

Domination éternelle dans les graphes

Graduate : Virgile, Virgélot
Cycle : Master's
Grade : M. Sc.
2015

Droites sur les hypergraphes

Graduate : Bayani, Aryan
Cycle : Master's
Grade : M. Sc.
2012

Complexité des homomorphismes de graphes avec listes

Graduate : Lemaître, Adrien
Cycle : Doctoral
Grade : Ph. D.
2007

Jeu de poursuite sur graphe non réflexif

Graduate : El Ouarari, Amal
Cycle : Master's
Grade : M. Sc.
2007

Reconnaissance des graphes policier-gagnants

Graduate : Thériault, Benoit
Cycle : Master's
Grade : M. Sc.
2006

Études du jeu de poursuite dans les graphes

Graduate : Zine, Youssef
Cycle : Master's
Grade : M. Sc.
2006

Graphe et jeu de poursuite : policiers et voleurs sous contraintes

Graduate : El Harti, Sif El Islam
Cycle : Master's
Grade : M. Sc.
2006

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

Graduate : Akrout, Khaled
Cycle : Master's
Grade : M. Sc.
2005

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

Graduate : Ramanampanoharana, Tantely
Cycle : Master's
Grade : M. Sc.
2004

A survey of graph and subgraph isomorphism problems

Graduate : Lei, Yaohui
Cycle : Master's
Grade : M. Sc.
2003

Problèmes de routages dans les réseaux optiques

Graduate : Houndété, Alfred
Cycle : Master's
Grade : M. Sc.

Projects

Research projects

2022 - 2029

Centre de recherches mathématiques (CRM)

Lead researcher : Octavian Cornea
Co-researchers : Yoshua Bengio , François Lalonde , Gilles Brassard , Michel Delfour , Marlène Frigon , Véronique Hussin , Christiane Rousseau , Jacques Bélair , Paul M Gauthier , Sabin Lessard , Alain Vinet , Nadia El-Mabrouk , Gena Hahn , Christian Léger , Fahima Nekka , Iosif Polterovich , Yvan Saint Aubin , Andrew Granville , Sylvie Hamel , Manuel Morales , François Perron , Mylène Bédard , Pierre Duchesne , Matilde Lalin , Robert Gwyn Owens , Manu Paranjape , Dana Schlomiuk , Luc Vinet , Hugo Chapdelaine , Mireille Schnitzer , Karim Jerbi , Alexander Fribergh , Alejandro Murua , Maciej Augustyniak , Benoît Mâsse , Dimitrios Koukoulopoulos , Jun Li , Benjamin Seamone , William Witczak-Krempa , Egor Shelukhin , Morgan Craig , Guillaume Lajoie , Margarida Carvalho , Guy Wolf , Florian Maire , Frédéric Dupont-Dupuis , Michael C. Mackey , Frédéric Lesage , Russell Steele , Erica Moodie , Paul François , Henri Darmon , Maxime Descoteaux , Prakash Panangaden , André Dieter Bandrauk , Peter Bartello , Chantal David , Jean-Marc Lina , R Platt , Anthony Raymond Humphries , John P. Harnad , Jacques Claude Hurtubise , Pengfei Guan , John A Toth , Niky Kamran , Adrian Iovita , Eyal Goren , Dmitry Jakobson , Vojkan Jaksic , Daniel Tzvi Wise , André Garon , Éric P. Marchand , Debbie Janice Dupuis , Yogendra Chaubey , Pawel Gora , Hershy Kisilevsky , Galia Dafni , D. Korotkin , Marco Bertola , Alina Stancu , Lea Popovic , Ibrahim Assem , Tomasz Kaczynski , Shiping Liu , Vasilisa Shramchenko , Bruno L. Rémillard , Richard Fournier , Alfred Michel Grundland , David Stephens , Xiaowen Chang , Frederic Guichard , Erik P. Cook , Robert Brandenberger , Adrian Vetta , Keshav Dasgupta , Christophe Grova , Gantumur Tsogtgerel , Johanna Neslehova , Jean-Christophe Nave , Anmar Khadra , Adam M. Oberman , Michael Yves Michel Pichot , Alexander Maloney , Dana Louigi Addario-Berry , José Garrido , Alexei Kokotov , Wei Sun , Patrice Gaillardetz , Linan Chen , Piotr Przytycki , Vladimir Makarenkov , Louis-Paul Rivest , François Bergeron , Steven P. Boyer , Line Baribeau , Frédéric Gourdeau , Claude Levesque , Thomas Joseph Ransford , Jean-Marie De Koninck , Javad Mashreghi , Thierry Duchesne , Srecko Brlek , Christophe Reutenauer , Vestislav Apostolov , Steven Lu , Geneviève Lefebvre , Hélène Cossette , Étienne Marceau , José Manuel Urquiza , Michael Lau , Alexandre Girouard , Antonio Lei , Jean-François Renaud , Christophe Hohlweg , Mathieu Boudreault , FRANCO SALIOLA , Alexandre Roch , Frédéric Rochon , Alexandre Blondin-Massé , Clement Hyvrier , Denis Talbot , Alexandre Bureau , Fabrice Larribe , Aurélie Labbe , Cody Hyndman , Khader Khadraoui , Hamed Hatami , Roger Villemaire , Frédéric Godin , Marcin Sabok , Yi Yang , Anne Mackay , Jérôme Vétois , Ting-Huei Chen , Habib Benali , Taoufik Bouezmani , Christian Genest , Xiaowen Zhou , Sorana Froda , Mélina Mailhot , Alexandra Schmidt , Simon Philippe Caron-Huot , Abdoulaye Banire Diallo , Jean-Philippe Lessard , Sarah Harrison , Anne-Sophie Charest , Masoud Asgharian-Dastenael , Rustum Choksi , Abbas Khalili Mahmoudabadi , Simon Gravel , Arusharka Sen , Arthur Charpentier , Mathieu Pigeon , Benoit Larose , Thomas Brüstle , Laurent Charlin , Janosch Ortmann , Tim Hoheisel , Jean Deteix , Jessica Lin , Michael Lipnowski , Giovanni Rosso , Thomas Hugh , Jean-Philippe Burelle , Julien Keller , Félix Camirand Lemyre , Marie-Pier Côté , Damir Kinzebulatov , Duncan McCoy , Klaus Herrmann , Felix Kwok , Courtney Paquette , Anush Tserunyan , Suresh Krishna , Valentino Tosatti , Patrick Brodie Allen
Funding sources: FRQNT/Fonds de recherche du Québec - Nature et technologies (FQRNT)
Grant programs: PVXXXXXX-(RS) Programme de regroupements stratégiques
2017 - 2025

Graph searching structural properties

Lead researcher : Gena Hahn
Funding sources: CRSNG/Conseil de recherches en sciences naturelles et génie du Canada (CRSNG)
Grant programs: PVX20965-(RGP) Programme de subvention à la découverte individuelle ou de groupe
2020 - 2021

Supplément COVID-19 CRSNG_Graph searching structural properties

Lead researcher : Gena Hahn
Funding sources: CRSNG/Conseil de recherches en sciences naturelles et génie du Canada (CRSNG)
Grant programs: PVXXXXXX-Supplément à l’appui des étudiants, des stagiaires postdoctoraux et du personnel de soutien à la recherche COVID-19
2012 - 2018

GRAPH SEARCHING AND APPLICATIONS

Lead researcher : Gena Hahn
Funding sources: CRSNG/Conseil de recherches en sciences naturelles et génie du Canada (CRSNG)
Grant programs: PVX20965-(RGP) Programme de subvention à la découverte individuelle ou de groupe
2008 - 2016

CENTRE DE RECHERCHES MATHEMATIQUES (CRM)

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

Outreach

Publications and presentations

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

  • Computer Science
  • Applied Mathematics
  • Pure Mathematics

Areas of expertise

  • Graph algorithms
  • Graph coloring
  • Cayley graph
  • Infinite graphs
  • Graph homomorphism
  • Pursuit-evasion
  • Discreet Mathematics
  • Graphs Symmetry
  • Graph theory