MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

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
Conference URL::
http://www.siam.org/meetings/da05/index.htm
Downloading URL:
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
Name*:
SIAM
URL:
Address*:
Philadelphia, USA
Type:
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:
Note, Abstract, ©
(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},
ADDRESS = {Vancouver, Canada},
MONTH = {January},
ISBN = {0-89871-585-7},
}


Entry last modified by Christine Kiesel, 04/20/2006
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Peter Sanders
Created
02/18/2005 03:03:21 PM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
20.04.2006 20:54:01
25.04.2005 18:33:39
25.04.2005 17:16:33
19.04.2005 15:05:08
02/18/2005 03:03:21 PM