Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  An Asymptotic Approximation Scheme for Multigraph Edge Coloring

Sanders, P., & Steurer, D. (2005). An Asymptotic Approximation Scheme for Multigraph Edge Coloring. In Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05) (pp. 897-906). Philadelphia, USA: SIAM.

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Sanders, Peter1, Autor           
Steurer, David1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: The edge coloring problem asks for assigning colors from a minimum number of colors to edges of a graph such that no two edges with the same color are incident to the same node. We give polynomial time algorithms for approximate edge coloring of multigraphs, i.e., parallel edges are allowed. The best previous algorithms achieve a fixed constant approximation factor plus a small additive offset. Our algorithms achieve arbitrarily good approximation factors at the cost of slightly larger additive term. In particular, for any $\epsilon>0$ we achieve a solution quality of $(1+\epsilon)\opt+\Oh{1/\epsilon}$. The execution times of one algorithm are independent of $\epsilon$ and polynomial in the number of nodes and the \emph{logarithm} of the maximum edge multiplicity.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2006-04-202005
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: Philadelphia, USA : SIAM
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 279135
Anderer: Local-ID: C1256428004B93B8-8D31C50979686514C1256FAC004D3661-SanSte2005
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Vancouver, Canada
Start-/Enddatum: 2005-01-23

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05)
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: Philadelphia, USA : SIAM
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 897 - 906 Identifikator: ISBN: 0-89871-585-7