Stefan Szeider, Österreichische Akademie der Wissenschaften
Ein Durchgang in einem Graphen ist ein Paar inzidenter Kanten. Wir betrachten Graphen zu denen eine Menge ``erlaubter'' Durchgänge vorgegeben ist. Ein Weg in (bzw. ein 2-Faktor von ) heißt kompatibel, falls alle Paare inzidenter Kanten von (bzw. von ) erlaubte Durchgänge bilden. In [1] wurde die algorithmische Komplexität des Auffindens kompatiber 2-Faktoren von Graphen untersucht. Wir untersuchen das Problem, ob zwischen zwei gegeben Knoten eines Graphen ein kompatibler Weg existiert. Wir bestimmen lokale Eigenschaften erlaubter Durchgänge, die eine Lösung des Problems in polynomieller Zeit ermöglichen, und zeigen, daß jede Abschwächung dieser Eigenschaften zu -vollständigen Problemen führt.
[1] | J. Kratochvíl, S. Poljak. Compatible 2-factors; Discrete Applied Mathematics 36, 253-266, 1992. |
E-Mail: | stefan.szeider@oeaw.ac.at |
Homepage: | goedel.dismat.oeaw.ac.at/ |