Please note that eDoc will be permanently shut down in the first quarter of 2021! Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

 Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents

ID: 279135.0, MPI für Informatik / Algorithms and Complexity Group
An Asymptotic Approximation Scheme for Multigraph Edge Coloring
Authors:
Language:English
Publisher:SIAM
Date of Publication (YYYY-MM-DD):2005
Title of Proceedings:Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05)
Start Page:897
End Page:906
(Start) Date of Conference/Meeting
(YYYY-MM-DD):
2005-01-23
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
Last Change of the Resource (YYYY-MM-DD):2006-04-20
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:
Identifiers:LOCALID:C1256428004B93B8-8D31C50979686514C1256FAC004D3661-...
ISBN:0-89871-585-7
 The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.