Reports
Using Euler Partitions to Edge Color Bipartite Multigraphs ; CU-CS-082-75 Public Deposited
https://scholar.colorado.edu/concern/reports/mw22v620x
- Abstract
- 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.
- Creator
- Date Issued
- 1975-09-01
- Academic Affiliation
- Last Modified
- 2019-12-21
- Resource Type
- Rights Statement
- Language
Relationships
Items
| Thumbnail | Title | Date Uploaded | Visibility | Actions |
|---|---|---|---|---|
|
|
usingEulerPartitionsToEdgeColorBipartiteMultigraphsCuC.pdf | 2019-12-21 | Public | Download |