Myriam PREISSMANN

Chargé de Recherche, C.N.R.S.

Département de Mathématiques Discrètes
Laboratoire Leibniz, IMAG
46 avenue Félix Viallet
38031 Grenoble Cedex, France

Aile ouest, bureau H328, 3ème étage

Téléphone : (33) 4 76 57 47 03
Télécopie : (33) 4 76 57 46 02

E-mail : Myriam.Preissmann@imag.fr

Cursus  -  Activités  -  Publications  -  Conférences  -  Ma photo (77 K)

Situation brève

- Née le 28 juillet 1954 à Zürich (Suisse)
- Chargé de recherche, CNRS
- Responsable de l'équipe Graphes


Diplômes

- Thèse de 3ème cycle, "Sur les colorations des arêtes des graphes cubiques", Université de Grenoble, Mai 1981 (sous la direction de François Jaeger).

- Thèse d'Etat, "Sur quelques problèmes théoriques et appliqués de la théorie des graphes", Université de Grenoble, Décembre 1988 (sous la direction de Jean Fonlupt).


Positions

  • 1981-1984, assistante du Professeur Dominique de Werra à l'Ecole Polytechnique Fédérale de Lausanne (Suisse).

  • 1984-1985, chercheur au Laboratoire Artémis (Grenoble), dans le cadre d'un projet européen pour la C.A.D. du V.L.S.I.

  • Depuis 1985, chargé de recherche au C.N.R.S. au Laboratoire Artémis (Grenoble, maintenant Laboratoire Leibniz).

  • Année sabbatique à RUTCOR (Rutgers University Center for Operations Research, New Jersey) en 1989.

    • Activités scientifiques actuelles
    Current Research Interests


    My work has had several orientations thanks to the different positions I had and the subjects which interested me.

    For my "first thesis" under the direction of François Jaeger I studied cubic graphs and their edge-colourings. These notions were initially studied because of their relationship with the four-colour conjecture, of which a formulation is: every cubic bridgeless planar graph has chromatic index 3. I obtained mainly two results: 1.) I disproved a theorem of Szekeres characterizing cubic graphs of chromatic index 3. There are several counterexamples to this theorem and particularly an infinite family. 2.) I defined c-minimal snarks; they form a class of cubic graphs of chromatic index 4 from which we can obtain every cubic graph of chromatic index 4 using a set of constructions. By defining new constructions, I restricted the class of snarks defined by R. Isaacs, which have the same property. Furthermore the results obtained for my thesis allowed me to prove that there are only two snarks of order 18.

    I was for one and a half year a participant of a European project for the computer-assisted design of VLSI circuits. The CASCADE language that we developed allows to describe a circuit and this description is treated to make the simulation of the circuit easier. I have developed several practical and theoretical algorithms to make this simulation faster.

    I have also worked with some physicist in statistical physics. We established the complexity of combinatorial problems associated with several physical models and designed some polynomial algorithms including a post-optimality procedure.

    After my thesis I worked at the Ecole Polytechnique Federale de Lausanne as an assistant of Professor Dominique de Werra. There my research oriented towards the field of perfect graphs. For these graphs the four important problems of Graph Theory, which are NP-complete in general, are polynomial [Grotschel, Lovasz and Schrijver]. Another interesting question about perfect graphs is Berge's famous Strong Perfect Graph Conjecture. I obtained several results concerning new classes of perfect graphs, new properties of minimal imperfect graphs, algorithmic properties, and other related questions.

    Perfect graphs are now the main subject of my research. There are many interesting and important unsolved questions. But I am also interested in any problems related to Graph Theory especially when they have practical applications.

    Conférences internationales
    Talks at international meetings


  • Colloque International sur la Theorie des graphes et la Combinatoire, Marseille-Luminy (France), June 15-19, 1981: "C-minimal snarks".

  • Congres International de Recherche Opérationnelle, EURO V, Tims XXV, Lausanne (Switzerland), July 12-14, 1982: "About the hunting of snarks".

  • 3ème Colloque International sur la Theorie des graphes et la Combinatoire, Marseille-Luminy (France), June 23-28, 1986: "On certain perfect and strongly perfect graphs".

  • Second International Conference in Graph Theory, Combinatorics, Algorithms and Applications, San Francisco, July 24-28, 1989: "A property of minimal non strongly perfect and minimal non perfectly orderable graphs".

  • Meeting on perfect graphs organized for the 65th birthday of Claude Berge, Bellairs Research Institute, Holetown, Barbados, March 3-9, 1991: "P4's and perfect graphs".

  • Fourth Franco-Japanese days on combinatorics and optimization, Grenoble, August 12-14, 1991: "Graphs with maximal number of minimum cuts".

  • Mini Symposia, Sixth SIAM Conference on Discrete Mathematics, University of British Columbia, Vancouver, Canada, June 8-11 1992: "Classes of perfectly orderable graphs that are polynomially recognizable".

  • GO-Meeting, Grimentz, Switzerland, August 23-28 1992: "The strong perfect graph conjecture for classes related to 2K2-free graphs".

  • Dimacs Workshop on Perfect Graphs, Princeton, USA, June 10-14 1993: "Problems on partitionnable graphs".

  • First DO-NET Workshop on Discrete Optimization, Trento, Italy, May 11-20 1994: "Introduction to perfect graphs. Minimal imperfect graphs".

  • 5ème Colloque International "Graphes et Combinatoire", Marseille Luminy, September 1995 : "Partitionable graphs with circular symmetry".

  • GO 3 Meeting, Loèche-les-Bains, Suisse, Août 1996: "A new class of perfect graphs".

    • Retour à la liste des membres de l'équipe