Approximation unabhängiger Mengen mit dem Greedy-Algorithmus
| Vortragende(r): |
| Dipl.-Inf. Matthias Baumgart |
| Inhalt: |
| Eine unabhängige Menge in einem Graphen ist eine Menge von Knoten, die paarweise nicht benachbart sind. Der MIN-Greedy-Algorithmus (es wird in jedem Schritt ein Knoten minimalen Grades gewählt) ist ein einfacher Algorithmus zur Bestimmung unabhängiger Mengen in Graphen. Es werden verschiedene Ergebnisse bezüglich der Güte des MIN-Greedy analysiert. |
| Zeiten: |
| Teil 1: Mittwoch, der 16.07.2003, 09:15 Uhr, Raum 1/368 Teil 2: Dienstag, der 09.12.2003, 15:30 Uhr, Raum 1/208A |
