Approximation unabhängiger Mengen mit dem Greedy-Algorithmus
| Talking persons: |
| Dipl.-Inf. Matthias Baumgart |
| Abstract: |
| 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. |
| Times: |
| part 1: Wednesday 16th July 2003, 9.15 am, room 1/368 part 2: Tuesday 9th December 2003, 3.30 pm, room 1/208A |
