Dokumentenserver der Freien Universität Berlin

Objekt-Metadaten

Approximate max k-cut with subgraph guarantee
Kann, Viggo ;  Lagergren, Jens ;  Panconesi, Alessandro ;  Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik

HaupttitelApproximate max k-cut with subgraph guarantee
AutorKann, Viggo
AutorLagergren, Jens
AutorPanconesi, Alessandro
Institution/KörperschaftUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
Seitenzahl[8] S.
Schriftenreihe Freie Universität Berlin, Fachbereich Mathematik [und Informatik] : Ser. B, Informatik ; 96,08
DDC004 Datenverarbeitung; Informatik
ZusammenfassungWe study the following variant of the Max k-Cut problem. Given an input graph G with positively weighted edges and k colors - the number k being fixed and not dependent on the input instance - we wish to compute a subgraph H of G containing "lots" of heavy edges and a color assignment c:V ->[k] such that: (a) all edges in H are properly colored and (b) a "large fraction" of edges in G\H is properly colored. We give several definitions of "lots'' and "large fraction'' and give fast polynomial time algorithms to compute such color assignments. This problem is related to the frequency allocation problems for cellular telephone networks but could be useful in other scenarios too.
Dokumente
pdf-Datei
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
 
Fachbereich/EinrichtungFB Mathematik und Informatik
Arbeitsbereich/InstitutInstitut für Informatik
Erscheinungsjahr1996
Dokumententyp/-SammlungenKarten
SpracheEnglisch
Rechte Nutzungsbedingungen
Erstellt am19.03.2009 - 14:46:04
Letzte Änderung23.01.2014 - 16:21:18
 
Statische URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001326
Zugriffsstatistik
 

LOADING...