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

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          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:Sanders, Peter; Steurer, David
Language:English
Publisher:SIAM
Place of Publication:Philadelphia, USA
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
Place of Conference/Meeting:Vancouver, Canada
(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:MPI für Informatik/Algorithms and Complexity Group
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.