Campus Event Calendar
Event Entry
What and Who
Edge-coloring bipartite multigraphs in O(E log D) time
Stefan Schirra
Max-Planck-Institut für Informatik - AG 1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 4
MPI Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 26 June 2000
13:30
45 Minutes
46
024
Saarbrücken
Abstract
Let V, E, and D denote the cardinality of the vertex set, the edge
set, and the maximum degree of a bipartite multigraph G. We show that
a minimum edge-coloring of G can be computed in O(E log D) time. This
result is based on an O(E) time algorithm to compute a matching in
a regular bipartite graph.
Contact
Stefan Schirra
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Graph Algorithms; Edge-Coloring; Matching; Efficient Algorithms