Passer au contenu

/ Research

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)

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

Reconnaissance des graphes policier-gagnants

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

Jeu de poursuite sur graphe non réflexif

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

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

Graduate : Akrout, Khaled
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.
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

2017 - 2024

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
2015 - 2022

CENTRE DE RECHERCHES MATHEMATIQUES (CRM)

Lead researcher : Luc Vinet
Co-researchers : 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 , Maciej Augustyniak , Jun Li , William Witczak-Krempa , Gena Hahn , Mireille Schnitzer , Alexander Fribergh , Benjamin Seamone , Egor Shelukhin , Alejandro Murua , Mylène Bédard , Alain Tapp , Laurent Charlin , 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 , Alexandre Bureau , M'Hamed Lajmi Lakhal Chaieb , José Manuel Urquiza , Hugo Chapdelaine , Michael Lau , Nicolas Doyon , Alexandre Girouard , Khader Khadraoui , Antonio Lei , Pengfei Guan , Xiaowen Chang , Prakash Panangaden , R Platt , 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 , Bruce Alan Reed , Anthony Raymond Humphries , Frederic Guichard , Russell Steele , 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 , Hamed Hatami , Anmar Khadra , Adam M. Oberman , Michael Yves Michel Pichot , Frédéric Lesage , Jean-Marc Lina , Vladimir Makarenkov , Alexander Maloney , Dana Louigi Addario-Berry , André Fortin , André Garon , Dominique Pelletier , Vahid Partovi Nia , É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 , Xiaowen Zhou , Benoit Larose , Marco Bertola , Alexei Kokotov , Wei Sun , Cody Hyndman , Alina Stancu , Patrice Gaillardetz , Lea Popovic , André Dieter Bandrauk , Ibrahim Assem , Tomasz Kaczynski , Shiping Liu , Virginie Charette , Vasilisa Shramchenko , Maxime Descoteaux , Taoufik Bouezmani , Anne Bergeron , François Bergeron , Steven P. Boyer , Srecko Brlek , Sorana Froda , Christophe Reutenauer , Roger Villemaire , Jean-François Renaud , Vestislav Apostolov , Steven Lu , Pedro Peres-Neto , Christophe Hohlweg , Mathieu Boudreault , Geneviève Lefebvre , FRANCO SALIOLA , Alexandre Roch , Simon Guillotte , Frédéric Rochon , Karim Oualkacha , Mark Powell , Bruno L. Rémillard , Alexandre Blondin-Massé , Thomas Brüstle , Richard Fournier , Linan Chen , Clement Hyvrier , Payman Kassaei , Piotr Przytycki , 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 , Aurélie Labbe , Mélina Mailhot , Alexandra Schmidt , Simon Philippe Caron-Huot
Funding sources: FRQNT/Fonds de recherche du Québec - Nature et technologies (FQRNT)
Grant programs: PVXXXXXX-(RS) Programme de regroupements stratégiques
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 : 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
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