Abstract
Let G be a graph with n vertices and m edges and let its maximum degree be Δ. It is shown that a valid edge coloring of G using at most 2Δ - 1 colors can be computed in O(log n log Δ) time using O(m + n) processors on a CREW PRAM. Based on this, for any constant c > 1, a valid edge coloring for G using at most max([cΔ], Δ + 1) colors can be computed in O(log2 n) time, using O(m + n) processors. Employing different techniques, we show that it is possible to compute a Δ2 coloring in O(log* n) time, with O(m+n) processors. Also, a maximal matching of G can be computed in O(log2 n log Δ) time using O(m + n) processors on a CREW PRAM.
Original language | English (US) |
---|---|
Pages (from-to) | 321-329 |
Number of pages | 9 |
Journal | Parallel Processing Letters |
Volume | 6 |
Issue number | 3 |
DOIs | |
State | Published - 1996 |
All Science Journal Classification (ASJC) codes
- Software
- Theoretical Computer Science
- Hardware and Architecture