MATCOLORINGGREEDY

Greedy-with-conflict correction based matrix coloring for distance 1 and 2 [BozdaugCG+05]

Notes

These algorithms proceed in two phases – local coloring and conflict resolution. The local coloring tentatively colors all vertices at the distance required given what’s known of the global coloring. Then, the updated colors are transferred to different processors at distance one. In the distance one case, each vertex with nonlocal neighbors is then checked to see if it conforms, with the vertex being marked for recoloring if its lower weight than its same colored neighbor. In the distance two case, each boundary vertex’s immediate star is checked for validity of the coloring. Lower-weight conflict vertices are marked, and then the conflicts are gathered back on owning processors. In both cases this is done until each column has received a valid color.

Supports both distance one and distance two colorings.

References

BozdaugCG+05

Doruk Bozdağ, Umit Catalyurek, Assefaw H Gebremedhin, Fredrik Manne, Erik G Boman, and Füsun Özgüner. A parallel distance-2 graph coloring algorithm for distributed memory computers. In International conference on high performance computing and communications, 796–806. Springer, 2005.

See Also

MatColoringType, MatColoringCreate(), MatColoring, MatColoringSetType(), MatColoringType

Level

beginner

Location

src/mat/graphops/color/impls/greedy/greedy.c

---

Index of all MatGraphOperations routines
Table of Contents for all manual pages
Index of all manual pages