Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2020) | last year (2019) | two years ago (2018) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Sanders, Peter Steurer, David dblp dblp
 Editor(s):
 BibTeX cite key*: SanSte2005

 Title, Booktitle
 Title*: An Asymptotic Approximation Scheme for Multigraph Edge Coloring Booktitle*: Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05)

 Event, URLs
 URL of the conference: http://www.siam.org/meetings/da05/index.htm URL for downloading the paper: Event Address*: Vancouver, Canada Language: English Event Date* (no longer used): Organization: Event Start Date: 23 January 2005 Event End Date: 25 January 2005

 Publisher

 Vol, No, Year, pp.
 Series:
 Volume: Number: Month: January Pages: 897-906 Year*: 2005 VG Wort Pages: 35 ISBN/ISSN: 0-89871-585-7 Sequence Number: DOI:

 (LaTeX) 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. Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{SanSte2005,
AUTHOR = {Sanders, Peter and Steurer, David},
TITLE = {An Asymptotic Approximation Scheme for Multigraph Edge Coloring},
BOOKTITLE = {Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05)},
PUBLISHER = {SIAM},
YEAR = {2005},
PAGES = {897--906},
MONTH = {January},
ISBN = {0-89871-585-7},
}