Projekt: Pfaffian graphs

Stammdaten
Pfaffian graphs
Beschreibung: The enumeration of perfect matchings in a vertex-edge graph is known to be an NP-hard problem. In the middle of the 20th century the Physicist Kasteleyn has developed an elegant method for the enumeration of perfect matchings in planar graphs which (roughly) reduces the problem to the computation of a determinant. However, his method can be extended to certain non-planar graphs. The aim of our project is a characterisation of the graphs to which Kasteleyn`s method can be extended.
Schlagworte: Matchings, Graph theory
Pfaffsche Graphen
Beschreibung: An sich ist das Abzählen von perfekten Matchings (auch Paarungen genannt) in einem Knoten-Kanten-Graphen ein NP-schweres Problem. Mitte des 20. Jahrhunderts hat der Physiker Kasteleyn eine elegante Methode angegeben, die das Abzählen der perfekten Matchings zumindest für planare Graphen im Wesentlichen auf die Berechnung einer Determinante reduziert. Seine Methode lässt sich aber auch auf bestimmte nicht-planare Graphen anwenden, bisher ist eine Charakterisierung dieser Graphen (Pfaffsche Graphen) aber noch offen. Ziel des Projektes ist es daher eine solche Charakterisierung im Sinne von verbotenen Teilgraphen zu finden.
Schlagworte: Graphentheorie, Matchings
Kurztitel: n.a.
Zeitraum: 01.01.2001 - 01.02.2004
Kontakt-Email: -
Homepage: -

MitarbeiterInnen
MitarbeiterInnen Funktion Zeitraum
Ilse Fischer
Forschungsaktivitäten
zur Visitenkarte
(intern)
  • wiss. Mitarbeiter/in
  • 01.01.2001 - 01.02.2004

Zuordnung
Organisationseinheit
Fakultät für Technische Wissenschaften
  Institut für Mathematik
Universitätsstraße 65-67
9020 Klagenfurt am Wörthersee
Österreich
   math@aau.at
https://www.aau.at/mathematik
zur Organisation

Kategorisierung
Projekttyp laufender Arbeitsschwerpunkt
Förderungstyp Kein Förderungstyp ausgewählt
Forschungstyp Kein Forschungstyp ausgewählt
Sachgebiete
  • 1115 - Technische Mathematik *
  • 1120 - Kombinatorik *
  • 1121 - Operations Research (5347, 5919) *
  • 11 - Mathematik, Informatik *
  • 1104 - Angewandte Mathematik *
Forschungscluster Kein Forschungscluster ausgewählt
Genderrelevanz 0%
Projektfokus
  • Science to Science (Qualitätsindikator: n.a.)
Klassifikationsraster der zugeordneten Organisationseinheiten:
Arbeitsgruppen Keine Arbeitsgruppe ausgewählt

Finanzierung
Keine Förderprogramme vorhanden

Kooperationen
Organisation Adresse
Serguei Norine (PhD student)
Neuseeland
NZ  
Charles H.C. Little (Associate Professor)
Neuseeland
NZ