Using Euler Partitions to Edge Color Bipartite Multigraphs ; CU-CS-082-75

摘要

An algorithm for coloring the edges of a bipartite multigraph using as few colors as possible is presented. The algorithm uses 0(V1/2E logV+V) time and 0(E+V) space. It is based on a divide-and-conquer strategy, using euler partitions to divide the graph. A modification of the algorithm for matching is described. This algorithm finds a maximum matching on a regular bipartite graph with all degrees 2^n, for some n, in 0(E+V) time and 0(E+V) space.