Edmonds Algorithm - Frage zum Expandieren

Moderator: Effiziente Graphenalgorithmen

Gallontzke
Erstie
Erstie
Beiträge: 22
Registriert: 22. Mär 2010 21:22

Edmonds Algorithm - Frage zum Expandieren

Beitrag von Gallontzke »

Hallo z'samm,

Bei Edmonds Algorithmus habe ich eine Schwierigkeit bei der Rekursion.
Das "shrinking" läuft problemlos, ich bekomme leider das Expandieren nicht hin. Kann mir da jemand erklären, wie das zu machen ist? Ich habe ja gegeben quasi die Edges aus "unteren Leveln" der Rekursion und expandiere die Zykel dann. Welche Kanten muss ich dann zusätzlich auswählen? Ich finde leider in den Folien auch die richtige Stelle nicht, ist da Korollar 18 (Chapter3, Folie 51)
der richtige Ansatz?

Vielen Dank.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Edmonds Algorithm - Frage zum Expandieren

Beitrag von Prof. Karsten Weihe »

Gallontzke hat geschrieben: Bei Edmonds Algorithmus habe ich eine Schwierigkeit bei der Rekursion.
Das "shrinking" läuft problemlos, ich bekomme leider das Expandieren nicht hin. Kann mir da jemand erklären, wie das zu machen ist? Ich habe ja gegeben quasi die Edges aus "unteren Leveln" der Rekursion und expandiere die Zykel dann. Welche Kanten muss ich dann zusätzlich auswählen? Ich finde leider in den Folien auch die richtige Stelle nicht, ist da Korollar 18 (Chapter3, Folie 51)
der richtige Ansatz?
Da ich Ihr Problem nicht ganz verstehe: Kommen Sie am Besten persönlich auf mich zu.

KW

Antworten

Zurück zu „Effiziente Graphenalgorithmen“