Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section