English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  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

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-259E-2 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-259F-F
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Sanders, Peter1, Author           
Steurer, David1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: 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

show
hide
Language(s): eng - English
 Dates: 2006-04-202005
 Publication Status: Issued
 Pages: -
 Publishing info: Philadelphia, USA : SIAM
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 279135
Other: Local-ID: C1256428004B93B8-8D31C50979686514C1256FAC004D3661-SanSte2005
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Vancouver, Canada
Start-/End Date: 2005-01-23

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05)
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Philadelphia, USA : SIAM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 897 - 906 Identifier: ISBN: 0-89871-585-7