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 (intern) |
|
|
Zuordnung
Organisationseinheit | ||||
---|---|---|---|---|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
Kategorisierung
Projekttyp | laufender Arbeitsschwerpunkt |
Förderungstyp | Kein Förderungstyp ausgewählt |
Forschungstyp | Kein Forschungstyp ausgewählt |
Sachgebiete | |
Forschungscluster | Kein Forschungscluster ausgewählt |
Genderrelevanz | 0% |
Projektfokus |
Klassifikationsraster der zugeordneten Organisationseinheiten:
|
Arbeitsgruppen | Keine Arbeitsgruppe ausgewählt |
Finanzierung
Kooperationen
Organisation | Adresse | ||
---|---|---|---|
Serguei Norine (PhD student)
|
NZ
|
||
Charles H.C. Little (Associate Professor)
|
NZ
|
Forschungsaktivitäten
(Achtung: Externe Aktivitäten werden im Suchergebnis nicht mitangezeigt)
Projekte | Keine verknüpften Projekte vorhanden |
Publikationen |
|
Veranstaltungen | Keine verknüpften Veranstaltung vorhanden |
Vorträge | Keine verknüpften Vorträge vorhanden |