15. ÖMG-Kongress
Jahrestagung der Deutschen Mathematikervereinigung

16. bis 22. September 2001 in Wien

Sektion 3 - Diskrete Mathematik, Algorithmen
Dienstag, 18. September 2001, 16.00, Hörsaal 23

 

Die Komplexität des Auffindens kompatibler Wege in Graphen

Stefan Szeider, Österreichische Akademie der Wissenschaften

 

Ein Durchgang in einem Graphen ist ein Paar inzidenter Kanten. Wir betrachten Graphen $G$ zu denen eine Menge $T_G$ ``erlaubter'' Durchgänge vorgegeben ist. Ein Weg $W$ in $G$ (bzw. ein 2-Faktor $F$ von $G$) heißt kompatibel, falls alle Paare inzidenter Kanten von $W$ (bzw. von $F$) 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 $\mathcal{NP}$-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/

Zeitplan der Sektion   Tagesübersicht   Liste der Vortragenden