Zum neuen Informatik-Forum >>
 FAQFAQ   SuchenSuchen   MitgliederlisteMitgliederliste   BenutzergruppenBenutzergruppen   RegistrierenRegistrieren   ProfilProfil   Einloggen, um private Nachrichten zu lesenEinloggen, um private Nachrichten zu lesen   LoginLogin 

4 Farbensatz, Approximationsalgorithmen

 
Dieses Forum ist gesperrt, du kannst keine Beiträge editieren, schreiben oder beantworten.   Dieses Thema ist gesperrt, du kannst keine Beiträge editieren oder beantworten.    Informatikerboard.de Foren-Übersicht -> Theoretische Informatik
Vorheriges Thema anzeigen :: Nächstes Thema anzeigen  
Autor Nachricht
Chris
Gast





BeitragVerfasst am: 25. Nov 2005 09:43    Titel: 4 Farbensatz, Approximationsalgorithmen Antworten mit Zitat

Hallo zusammen,

ich würde gerne zeigen, dass es keinen Approximationsalgorithmus für den 4 Farbensatz gibt mit Approximationsquotient <= 4/3. Ich vermute, dass man das am besten mit einer Reduktion auf ein anderes Problem machen kann, das auch in APX liegt. Kennt jemand einen Weblink zum Thema APX und Reduktionen und so? Wäre wirklich dankbar.

Viele Grüße, Christian
Nach oben
Beiträge der letzten Zeit anzeigen:   
Dieses Forum ist gesperrt, du kannst keine Beiträge editieren, schreiben oder beantworten.   Dieses Thema ist gesperrt, du kannst keine Beiträge editieren oder beantworten.    Informatikerboard.de Foren-Übersicht -> Theoretische Informatik Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
Du kannst Dateien in diesem Forum nicht posten
Du kannst Dateien in diesem Forum nicht herunterladen